Slashdot Mirror
Wolfram's 2,3 Turing Machine Not Universal
Fishbat writes "In a cutting message to the Foundations of Mathematics mailing list, Stanford's Vaughan Pratt has pointed out an elementary mistake in the recently announced proof that Wolfram's (2,3) machine is universal." Update: 10/30 04:18 GMT by KD : Ed Pegg Jr. from Wolfram Research points to this response to Dr. Pratt's note, which has been submitted to the FoM mailing list but has not yet appeared there due to moderation.
Wolfram's 2,3 Turing Machine Not Universal
That's not, from my reading, what is true. What is true is that the proof is wrong, which means that it may not be universal, but reverts back to the unknown state.
You misread the post. He said that if x + y = infinity and y is finite, then x must be infinity. This is TRUE for numbers. You cannot apply this by analogy to automata and think it is still true. It is not.
You sound like a troll since you're so belligerent, but, in case anyone else here is legitimately wondering what it means for a Turing machine to be universal, I'll try to answer.
Basically, a Turing Machine is an abstract "computer"--it's a tape (a skinny piece of paper) that has a start but no end (it's infinitely long, but it has a start), and a read/write head that can zip up and down the tape writing, reading, and erasing symbols on the tape. The Church-Turing Thesis postulates that a computable algorithm is any algorithm that can be computed in a finite number of steps by a Turing Machine. There are some things that look like algorithms and seem like they should be computable but are in fact impossible. The classic example is the Halting Problem.
Anyway, a regular Turing Machine only computes one function--it's a single-purpose machine. A Universal Turing Machine is a Turing Machine that can simulate any other Turing Machine by interpreting a codified description of the other machine. Since every computable function is isomorphic to some Turing Machine and every Turing Machine can be simulated by a Universal Turing Machine, every computable function can be computed by a Universal Turing Machine. The computer you're using to read this is an approximation to a Universal Turing Machine (the RAM would have to be infinite in size to be a proper Turing Machine), and the codified descriptions that it interprets are the binary executables that you run on it.
Hope that helps,
Ian
Indeed. A prior email in that thread -- by the same author, Pratt -- makes it very clear by giving the example of 2 pushdown automata (PDA). A single PDA by itself is not universal, but the system comprised of 2 PDAs is universal, since each stack can represent one side of the Turing machine tape.
As Pratt states, the fallacy is of the following form: a system comprised of 2 PDAs, PDA A and PDA B, is universal. PDA A alone is not universal. Therefore, PDA B must be universal (because the system as a whole is universal). QED.
Of course, in the actual proof, it was not 2 PDAs, but a 2,3 machine and an encoder (i.e.,"PDA A" == "encoder" and "PDA B" == "2,3 machine").
I'm posting from Wolfram Research. Basically, a message from Vaughan Pratt was posted to the correct spot, the FOM list. Dr. Pratt likely didn't expect his message to get a late night SlashDot level exposure. A response to his message has already been sent to the FOM list, but it is a moderated list, and the response is not visible yet. Here is a copy of the FOM posting from Todd Rowland, from the Wolfram prize committee. http://forum.wolframscience.com/showthread.php?s=&threadid=1472 This is how math is done ... trying to poke holes in proofs.