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?

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ This is an interesting twist: "Believing in a proof"... $\endgroup$
    – vonjd
    Commented 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
    Commented 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
    Commented Jul 27, 2010 at 0:50

3 Answers 3

Reset to default
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.

Improve this answer
$\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
    Commented 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
    Commented 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 ;)

Improve this answer
$\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
Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .