Woods, Damien and Neary, Turlough (2015) Yurii Rogozhin’s Contributions to the Field of Small Universal Turing Machines. Fundamenta Informaticae, 137. pp. 1-9. ISSN 0169-2968

Preview

Download (166kB) | Preview

Abstract

In the field of small universal Turing machines, Yurii Rogozhin holds a special prize: he was first to close off an infinite number of open questions by drawing a closed curve that separates the infinite set of Turing machines that are universal from a finite set of small machines for which we don’t yet know. Rogozhin did this by finding the smallest known universal Turing machines at the time, both in terms of number of states and number of symbols. This brief note summarises this and a few of Yurii’s other contributions to the field, including his work with Manfred Kudlek on small circular Post machines.

Item Type:	Article
Keywords:	Yurii Rogozhin; contribution; Small Universal Turing machines; small circular Post machines;
Academic Unit:	Faculty of Science and Engineering > Computer Science Faculty of Science and Engineering > Electronic Engineering Faculty of Science and Engineering > Experimental Physics Faculty of Science and Engineering > Mathematical Physics Faculty of Science and Engineering > Mathematics and Statistics Faculty of Science and Engineering > Psychology Faculty of Science and Engineering > Research Institutes > Callan Institute Faculty of Science and Engineering > Research Institutes > Centre for Ocean Energy Research Faculty of Science and Engineering > Research Institutes > Hamilton Institute
Item ID:	13730
Identification Number:	https://doi.org/10.3233/FI-2015-1198
Depositing User:	Damien Woods
Date Deposited:	01 Dec 2020 17:08
Journal or Publication Title:	Fundamenta Informaticae
Publisher:	IOS Press
Refereed:	Yes
URI:	http://www.iospress.nl/journal/fundament...
Use Licence:	This item is available under a Creative Commons Attribution Non Commercial Share Alike Licence (CC BY-NC-SA). Details of this licence are available here

Repository Staff Only(login required)

Item control page

Downloads

Origin of downloads