[FOM] Simple Turing machines, Universality, Encodings, etc.
d.woods at cs.ucc.ie
Tue Oct 30 16:01:36 EDT 2007
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
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  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.
More information about the FOM