8
$\begingroup$

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?

$\endgroup$
3
  • 2
    $\begingroup$ This is an interesting twist: "Believing in a proof"... $\endgroup$
    – vonjd
    Jul 26, 2010 at 8:05
  • 4
    $\begingroup$ 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. $\endgroup$
    – Junkie
    Jul 26, 2010 at 8:20
  • $\begingroup$ According to wolframscience.com/prizes/tm23/solved.html, the proof was supposed to appear in Complex Systems, but that hasn't happened. $\endgroup$
    – Dan Ramras
    Jul 27, 2010 at 0:50

3 Answers 3

2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – k2forever
    Jul 26, 2010 at 21:10
  • 1
    $\begingroup$ 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.) $\endgroup$
    – Kaveh
    Jul 27, 2010 at 0:00
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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)

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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