[FOM] Simple Turing machines, Universality, Encodings, etc.

[Damien Woods]

Maybe we can help clarify some things here.

 > Date: Sun, 28 Oct 2007 19:32:52 -0400
 > From: joeshipman at aol.com
 >
 > What is the smallest TM you know of which has an r.e.-complete halting
 > set of initial configurations that are nonzero in only finitely many
 > cells?

Our recent paper (see link below) contains information on the smallest such (standard) machines. In 
terms of state-symbol product the answer is the (4,6) (that is, 4-state, 6-symbol) machine by 
Rogozhin [1996] and the (6,4) machine given in our paper. In terms of number of transition rules, 
there are two relevant machines that use only 22 transition rules; Rogozhin's (4,6) and our (5,5). 
Our results were presented at MCU 07, a conference which has had quite a number of papers over the 
years on this topic:

T. Neary, D. Woods. "Four small universal Turing machines", Machines, Computations, and Universality 
(MCU) 2007, Orléans, France. Springer LNCS, vol. 4664, J. Durand-Lose, M. Margenstern (editors)

pdf available at the URL: http://www.cs.ucc.ie/~dw5/

These machines use the "standard" model, that was used by Minsky and others, and so can be directly 
compared to (say) Minsky's (7,4) machine in terms of (say) number of states and symbols. The 
universal machines that appear in M. Cook's paper, S. Wolfram's book, and some of our own papers are 
not obviously comparable in this way to the standard model, as they use a more general definition. 
There are still many state-symbol pairs which are open for the standard model. Many questions about 
the relationships between these models are also open, for instance, are the lower bounds for weak 
and standard machines equal or not?

The website mentioned above also contains a short survey paper, entitled "The complexity of small 
universal Turing machines," which lists quite a number of universal program size results for 
non-standard (and standard) Turing machines (see final 2 pages in particular). When giving a new 
result we always have to carefully state what model we are using. This survey might help to give 
some context for the discussion.

Of particular relevance is the (2,3) machine by Margenstern and Pavlotskaya. For such a small
machine the authors are (of course) using a rather general model, their Turing machine interacts
with a finite automaton. Using other generalisations, other authors have machines as small as their 
(2,3), however Margenstern and Pavlotskaya also prove a lower bound: on the one hand they prove that 
a (2,3) with 5 transition rules is universal, but on the other hand they prove that the halting 
problem is decidable for all 4 instruction machines of this form. Margenstern has shown a number of 
other nice results where upper bounds and lower bounds meet for various criteria related to program 
size and structure.



Best regards,


Turlough Neary
Damien Woods