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.
The Wolfram's 2,3 Turing Machine proof of universality was found to be flawed. This does *not mean* the 2,3 Turing Machine isn't universal. It just means it has not been proven to be universal. That would require another proof. Subtle distinction, I know; but in any case, the title of this article is fallacious.
As others have pointed out, no, it doesn't mean anybody's proven that it's not universal, it just means that this alleged proof of universality was incorrect.
Bill Stewart
New Fast-Compression-only CPR http://preview.tinyurl.com/dy575ks
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").
Incidentally, for anyone who wants to learn something about automata and theory of computation and doesn't know where to start, I highly recommend the following book by Michael Sipser: Introduction to the Theory of Computation.
It's quite pricey for such a small book, but it's worth its weight in gold (i.e., the time you save by reading this little masterpiece instead of something else that's less well written). You can find the 1st edition used for much cheaper than the 2nd edition, and the differences between the two editions are pretty minor.
p.s. I have no connection to the book or the author. I'm just a very happy customer.
I don't understand the math behind this argument and counter-argument, but Vaughan Pratt is a CS legend and one of the early cofounders of Sun, to boot. You also might have run across his name in a cite or two in The Art of Computer Programming series by Donald Knuth. And if you don't care who Knuth is, then you probably don't care about this post at all.
:P
I knew Pratt's daughter in college -- nice woman. Wrote her term papers in LaTeX, on a Linux workstation, in 1996
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.
This argument and Pratt's argument that the universality proof are incorrect both share the same flaw; see the response linked in the update of the original story for more details. Yes, a system consisting of two push-down automata that can communicate back and forth is universal. However, the proof of the universality of the 2,3 Turing machine in question doesn't set up a system where two systems can communicate back and forth; instead, the output of one is used as the input of the other, and there is no communication in the other direction. If one PDA is used as an encoder for another, the resulting system is not universal. The definition of universality in the original prize that was agreed on by the judges basically said that in the case of obviously simple encoders, if an encoder+system together are universal than the system itself is. The encoder used in the proof is not obviously simple (as it takes up several pages in the proof) but is clearly not doing any sort of universal calculation itself or engaging in part of such a calculation.
The real problem here is that with other definitions of 'universal', the system might indeed not be universal; the definitions are important in such cases. (For instance, a definition that restricted the initial condition to be finite and surrounded by nothing but yellow on the tape would result in the system being non-universal, but this definition is too restrictive to be useful.) Changing the definition of 'universal' is likely to result in changes to what is universal and what isn't, although it seems likely that the 2,3 Turing machine in question is well on the universal side of that edge (although not as far as some other systems). Even systems such as rule 110 that are generally accepted to be universal would be non-universal if a non-repeating finite initial condition was mandated by a definition of universality.
So in short, nothing has been disproven, the machine is still universal, and the headline is wrong.
(1)DOCOMEFROM!2~.2'~#1WHILE:1<-"'?.1$.2'~'"':1/.1$.2'~#0"$#65535'"$"'"'&.1$.2'~'#0$#65535'"$#0'~#32767$#1"
Well, that's a good start: you accepting you are not an expert in the field but pretending to judge something that of course experts reviewed. It is nice that people like you think on this problem and possible flaws, though. Of course nobody is changing the well stablished definition of a Turing machine. But it is accepted even by the experts that there is no clear definition on universality. You should follow all the FOM posts and not only those that you think are better to critic others. The definition of universality has been modify several times, the first to make a generalization exactly as the used by Alex Smith was Watanabe as early as in the 60's. Alex Smith contribution is a generalization of the same sort. If you want some references feel free to check these and then reply again: [1] Manfred Kudlek. Small deterministic Turing machines. Theoretical Computer Science, 168(2):241-255, November 1996. [2] Manfred Kudlek and Yurii Rogozhin. A universal Turing machine with 3 states and 9 symbols. In Werner Kuich, Grzegorz Rozenberg, and Arto Salomaa, editors, Developments in Language Theory (DLT) 2001, vol. 2295 of LNCS, pp. 311-318, Vienna, May 2002. Springer. [3] Maurice Margenstern and Liudmila Pavlotskaya. On the optimal number of instructions for universality of Turing machines connected with a finite automaton. International Journal of Algebra and Computation, 13(2):133-202, April 2003. [4] Claudio Baiocchi. Three small universal Turing machines. In Maurice Margenstern and Yurii Rogozhin, editors, Machines, Computations, and Universality (MCU), volume 2055 of LNCS, pp. 1-10, Chisinau Moldavia, May 2001. Springer. [5] Turlough Neary and Damien Woods. Four small universal Turing machines. Machines, Computations, and Universality (MCU), volume 4664 of LNCS, pp. 242-254, Orleans, France, September 2007. Springer. [6] Yurii Rogozhin. Small universal Turing machines. Theoretical Computer Science, 168(2):215-240, November 1996. [7] Shigeru Watanabe. 5-symbol 8-state and 5-symbol 6-state universal Turing machines. Journal of the ACM, 8(4):476-483, October 1961. [8] Shigeru Watanabe. 4-symbol 5-state universal Turing machines. Journal of Information Processing Society of Japan, 13(9):588-592, 1972. That is why many serious authors as Vaughn Pratt can be confused. Because they are not updated on the subtles of the field. We are glad that this is making a contribution to the discussion on universality. We expect that others will further clarify what Alex Smith has done.
Yes, exploited. It's a professional embarrasment at the start of his career. I'm not sure $25K is a fair price.
It's a basic logic problem. The original challenge problem could be restated: "Prove either that there exists a non-universal machine which emulates the 2-3 machine OR that the 2-3 machine can only be emulated by a universal machine." The proof does neither. Wolfram Inc. reps have come back with "Well, perhaps we should change the definition of universality!" Only, they aren't very concrete in offering an alternative with any rigor and the vague suggestions they are making don't add up (e.g., don't answer Vaughn Pratt's counter-example of paired push-down automata).
What the student proved here may turn out to be an interesting and useful result (not the universality of 2-3 but the universality of this interesting combination of machines). Students should be encouraged to work on such problems. Students should be encouraged to write as well as this student is learning to do -- it's a nicely presented paper (trivial formatting bugs aside). But students shouldn't be encouraged to go in those directions on false premises.
At least two interesting questions come from the students work. To Wolfram Inc.'s credit, they are pointing in the general direction of these new questions (even while not yet acknowledging their mistake). The new questions: Do there exist simple machines whose universality is undecidable (and might 2-3 be an example)? If 2-3's universality is either false or undecidable (and especially in the latter case) can we find any useful structure to what combinations of it with other machines clearly are universal?
I'll leave it as an exercise to figure out how raising those questions relate to the "Priciple of Computational Equivalence" in NKS but, meanwhile, leave the student out of it!
We'll see. With an additional step that "finitizes" the student's construction the proof is rescued and raised to the status of an important lemma -- but if that step isn't very quickly forthcoming, the prize -- in no small part an advertising vehicle -- was administered in a pedagogically misleading way.
-t