[FOM] Smallest universal machine

Alasdair Urquhart urquhart at cs.toronto.edu
Fri Oct 26 13:37:39 EDT 2007



> As far as I know, no member of the committee has passed on the
> validity of this 40 page proof. The determination that Smith's proof
> is correct seems to have been made entirely by the Wolfram
> organization. My understanding is that the I/O involves complex encodings.

The paper is available online at

http://www.wolframscience.com/prizes/tm23/TM23Proof.pdf

The introductory paragraph reads as follows:

"The main problem is to determine whether the following Turing
machine is universal
 	<description of machine follows>
  ... The proof I intend to give demonstrates that this Turing
machine can emulate any two-colour tag system for an infinite
number of steps. I first show that this Turing machine can
emulate any two-colour cyclic tag system for an arbitrary
finite number of steps (with the number of steps encoded in
the initial condition), and then use this result as a basis
for proving the more general result that this Turing machine
can carry on such an emulation indefinitely."


The notion of "universal" employed here seems unclear (something
that is also true of Wolfram's book "A New Kind of Science.").

Alasdair Urquhart





More information about the FOM mailing list