🚀 go-pugleaf

In article <1993Jan27.123943.2699@odin.diku.dk> 
torbenm@diku.dk (Torben AEgidius Mogensen) writes: 
>
>von Neumann constructed a TM with only 6 states that can
>simulate any other TM by coding it's "program" on the tape together
>with it's initial input. Such a TM can can indeed be called
>"universal". In this sense: yes, someone has indeed constructed a
>universal Turing machine.

Minsky has constructed of universal TM's with various small values 
of the pair (number of states, size of alphabet).  See his book 
"Computation: Finite and Infinite Machines".  Some of the values
were surprisingly small, with both numbers being less than 10.
Minsky's book is pretty old, and the state of the art may have advanced
since it was published.

>von Neumanns universal TM has incidentially been used to prove that 1
>dimensional cellular automata are universal: someone (I don't recall
>who) has constructed a 1D CA that simulates von Neumanns universal TM.

I think it was Alvy Ray Smith's PhD thesis sometime in the
1970's. This was mentioned in an old Martin Gardner column 
on the game of Life (which is itself a universal 2DCA) .  
If memory serves, Smith's universal 1DCA  had an  alphabet 
of 239 symbols.   Does anyone have more references on this
subject?

Tal   kubo@math.harvard.edu