Wolfram's 2-state 3-symbol Turing machine - MathOverflow

Wolfram's 2-state 3-symbol Turing machine

2010-07-26T07:48:12Z

A few years ago it was announced that a 2-state symbol Turing machine was proven to be universal. However, Vaughn Pratt disputed the proof, and I gather he still disputes it. Wolfram's prize committee seems to be satisfied.

Is there anyone not on team Wolfram who believes the proof is correct?

Answer by Kaveh for Wolfram's 2-state 3-symbol Turing machine

2010-07-26T13:04:02Z

See the discussion on FOM mailing list. As far as I remember, according to some members of the prize committee, Wolfram announced it without proper contact with them. There was also discussion about what was Pratt's objection to the proof. See this:

http://cs.nyu.edu/pipermail/fom/2007-October/012132.html

and the other posts in that thread.

Answer by Juan Bermejo Vega for Wolfram's 2-state 3-symbol Turing machine

2011-06-15T16:28:00Z

There is a quite interesting post in Shtetl-Optimized about this topic. Here you can get an idea of many researcher's opinion about after the announcement of the discovery (it does not seem to have changed much since then); if you are looking for the opinion of the community, this is definitely want you should read.

Link: http://www.scottaaronson.com/blog/?p=284

What I get from the discussion: people seem to agree that these Turing Machine are universal (in some interesting but not so trivial sense), and maybe the simplest Turing machine we can hope to find. Yet nobody has found this simple machine very useful for theoretical computer science.

Still it's obviously a cool Turing Machine ;)

Answer by Anon for Wolfram's 2-state 3-symbol Turing machine

2012-02-14T10:04:59Z

According to a paper published in Complex Systems in 2010 [1], Smith's paper is still forthcomming. Here is the reference given there to Smith's paper:

[6] A. Smith, “Wolfram’s 2,3 Turing Machine Is Universal,” Complex Systems, to appear. (Aug 12, 2010)

http://www.complex-systems.com/pdf/19-1-2.pdf