FOM: Wolfram?

[Robert M. Solovay]

On Wed, 5 Jun 2002, Neil Tennant wrote:

>
> On Wed, 5 Jun 2002 JoeShipman at aol.com wrote:
>
> >I don't know about this 2-state 5-symbol periodic-background UTM -- what
> >is the record for (states*symbols) in a UTM with ordinary finite
> >background?
>
> I once saw Conway give a proof that there is a UTM with 8 states, whose
> symbols are 0,1 and Halt. That was over twenty years ago, and I don't know
> what the state of the art would be now.
>
> Neil Tennant

	Martin Davis alerted me to the work of Yuri Rogozhin. He proves
that there is a UTM with m states and n symbols for the following values
of (m,n):

(22,2) ; (10, 3) ; (7,4); (5,5); (4,6); (3, 10); and (2;18). He cites a
result of Pavlotskaya that the combinations (3,2) and (2,3) do not permit
universal macines.

	Most of the Rogozhin work appears in an article in Theoretical
Computer Science, vol. 168(2), 1996, 215-240.

	I haven't checked the work in detail; it extends the techniques of
Minsky. {One uses the TM's to simulate Tag systems which had previously
been proved universal.}

	The Pavlotskaya work almost contradicts a conjecture of Wolfram
that a specific 2 symbol 3 state TM is universal. However, as I remarked
in a previous posting, Wolfram uses "universal" slightly differently than
Rogozhin.