Sign up ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|cite|improve this question
This is an interesting twist: "Believing in a proof"... –  vonjd Jul 26 '10 at 8:05
The question was maybe ill-posed, though I am not an expert. Minsky (1967) required finite input, then repeating infinite was allowed decades later, but Pratt does not like the fact that the (2,3) "universality" allows nonrepeating infinite, though patterned. Without proper definitions, anything is valid. –  Junkie Jul 26 '10 at 8:20
According to, the proof was supposed to appear in Complex Systems, but that hasn't happened. –  Dan Ramras Jul 27 '10 at 0:50

3 Answers 3

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:

and the other posts in that thread.

share|cite|improve this answer
I've looked through that, but I still can't quite figure out what the (non-Wolfram) consensus is. As Junkie says, it seems it boils down who accepts what definition. –  k2forever Jul 26 '10 at 21:10
See Alexander Smith's posts on the FOM. I think he himself agreed at some point that his proof has a problem, don't remember if it was corrected. As far as I remember, no one said that she/he agrees with Wolfram, though I might be wrong. I consider it as a kind of consensus. (IMHO as a non-expert, the question is not completely well defined, and even if it was, it is not as important as it seems.) –  Kaveh Jul 27 '10 at 0:00

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.


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 ;)

share|cite|improve this answer

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)

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.