[FOM] Simplest universal Turing machine

John McCarthy jmc at cs.Stanford.EDU
Fri Oct 26 16:33:15 EDT 2007


In the 1950s I thought that the smallest possible (symbol-state
product) universal Turing machine would tell something about the
nature of computation.  Unfortunately, it didn't.  Instead as simpler
universal machines were discovered, the proofs that they were
universal became more elaborate, and do did the encodings of
information.

The proof that Wolfram's 3x2 is universal is reported to be 44 pages,
and go via Minsky's? tag systems.


More information about the FOM mailing list