Wolfram's 2,3 Turing Machine Not Universal 284
Posted
by
kdawson
from the whoanotsofasttherebigfella dept.
from the whoanotsofasttherebigfella dept.
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.
The Filter (Score:5, Interesting)
But what should really be noted is what Wolfram himself is quoted as saying from the initial publishing of this proof:
I don't know a lot about finite automata but this whole display has shown that Alex Smith is talented but not the winner of the prize, it's best to accept and seek out all criticisms from your community before publishing & Wolfram is not the genius he makes himself out to be. I don't believe I will ever read "A New Kind of Science" as I have many other books in front of that one on my list.
Sounds like just another step in the learning process for Alextoo bad about the cash but he is only 20 and from the looks of it has a bright and promising future. Quite the embarrassment for Wolfram, however.
The real kicker would be if Wolfram had asked his staff to review the proof and they knew it had an elementary mistake and had told him it was golden. Now that would be poetic justice.
Re:The Filter (Score:5, Informative)
Re:The Filter (Score:5, Informative)
Indeed. A prior email in that thread  by the same author, Pratt  makes it very clear by giving the example of 2 pushdown automata [wikipedia.org] (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").
Re:The Filter (Score:4, Informative)
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 [amazon.com].
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.
Re:The Filter (Score:4, Funny)
Hey Michael, long time no post.
Re: (Score:2)
Note that I'm not anonymous.
Re: (Score:2)
Re: (Score:3, Interesting)
Re: (Score:3, Informative)
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 pushdown 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
Re: (Score:2, Informative)
I didn't understand Pratt to be arguing that the 2PDA system is directly analogous to the proof system in the way that you state. What I understood Pratt's point to be was that the proof does not prove that the 2,3 machine must be universal, since it is entirely possible that while the encoding mechanism itself is not universal, it nevertheless could be sufficiently complex that universality does not (and perhaps cannot) exist without it.
The author of the proof states on page 26 (counting the first PDF p
Re: (Score:2, Informative)
Re: (Score:3, Insightful)
Re: (Score:2)
My understanding is that the proof shows how to set up the machine so that it will execute any calculation  it will be "universal". However the question mark is that in order to do the set up, you have to prepare an infinite sequence in memory just a certain way. The question is whether that set up operation is universal itself, in which case the fact that the whole operation is universal wouldn't count 
Re: (Score:2)
Eh, my instinct is to twitch when we're so callously applying the addition operator to objects that are not natural numbers (or reals, etc). Maybe there's some definition or convention I'm unaware of, but I'd restate that as:
"If the set A union B contains an infinite number of elements, and B contains finitely many elements, then A's cardinality must be infinite."
But even that I'm not too sure about, as I know there's a lot more than meets the eye when it comes to set theory.
Re: (Score:2)
Smith's proof will be published in the journal Complex Systems.
Meaning it had not yet been peer reviewed.
On the contrary, if a result "will be published", then there is every reason to believe that it has been peerreviewed.
One doesn't use such positive language prior to peerreview. If it hasn't been reviewed, there's very little reason to suppose that it will be published in the journal to which it has been submitted. (Indeed, as I recall, Wolfram formed a respectable group of scholars for reviewing this and other arguments for this proof and thus it had been reviewed.)
Re: (Score:2)
My understanding was that the purpose of publishing is peer review. Once published, a peer can replicate the methods and obtain the same results, (or not,) see the process, logic, and methods, and agree or disagree with the findings. Is my understanding wrong?
Re: (Score:2)
And how many 20 year olds run out and buy the latest copy of 'Complex Systems'...?
Not enough, apparently
Re: (Score:2)
Paper stages (Score:2)
This paper sounds like it had reached the "accepted for publication" stage, which m
Re:The Filter (Score:5, Funny)
HOLLYWOOD  In a shock move, MGM has undercut Universal in its bid for the movie rights to Wolfram's 2,3 Turing Machine. Insiders had predicted that Universal would make the deal to build on the phenomenal success of Wolfram's 2,2 Turing Machine, but it has since become apparent that Universal failed to include an option for all sequels in the original contract. The exact figure offered by MGM is unknown, but is believed to be approximately x + y, and we can confirm that y is a finite number. More details will follow.
Re: (Score:2)
Sorry, good try, maybe n
Give Wolfram some credit (Score:4, Interesting)
Hardly. Wolfram disappeared for a decade to produce A New Kind of Science. Was he picking his toes while his team of crack Mathematica techies were developing the ideas for the book? I find that hard to believe. In fact, the way I heard it, he did all of his own editing on the book, much to the dismay of some who found it in need of editing.
He probably did have staffers assisting in running simulations (and with his bankroll, I would certainly entertain that notion myself), but name me one prominent professor who hasn't stood on the shoulders of graduate students.
Whether you consider him a genius or a crackpot (and he certainly gives reason to entertain both opinions), Wolfram is undoubtedly brilliant and seems to be dedicated to the advancement of mathematical ideas that he considers to be important. It hardly seems that a lack of academic integrity would be consistent with his actions to date.
Whether history will ultimately judge him a genius or a crackpot, I would guess that he has done more to advance mathematics than all the posters to this article combined, myself included. So give the man some credit.
Re: (Score:2)
Smith's proof will be published in the journal Complex Systems.
Meaning it had not yet been peer reviewed.
No, this means the opposite AFAIK. If it will be published in a peerreviewed journal, then it has already been reviewed. Otherwise you would say it has been submitted to the journal, which would imply a review is pending.
That is, you only say it will be published after acceptance by the journal, following peer review. It is then published some time later, depending on the queue for publication in that journal.
Ouch (Score:3, Informative)
Re: (Score:2)
Is not universal? (Score:4, Insightful)
kdawson, not proven to be universal and proven to be not universal are two different things.
No, just not proven (Score:4, Informative)
Back to the drawing board (Score:3, Informative)
Bad Headline (Score:5, Informative)
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.
Re: (Score:2)
I don't know if this is the submitter's headline, but furrfu, that's something that wossname, the editor, should catch.
I rate this proof (Score:5, Funny)
Re: (Score:2)
Re: (Score:3, Funny)

"from the whoanotsofasttherebigfella dept" (Score:5, Funny)
"Wolfram's 2,3 Turing Machine Not Universal". What? Where'd you get that? This issue doesn't prove anything of the sort  it merely shows that this proof is invalid. It may be universal, it may not, but we still don't know.
So, ironically  whoa, not so fast there big editor.
Bad romantic consequence (Score:5, Funny)
Re: (Score:2)
Or, the young man is a cigarette, in which case I withdraw my objection.
Peer Review Rules (Score:5, Insightful)
Re: (Score:2)
Re: (Score:2)
Re:Peer Review Rules (Score:4, Insightful)
Well, to paraphrase someone famous (perhaps Edison?), we've learned another way that doesn't work. It sounds like the author of the proof has used a faulty syllogism. Perhaps the syllogism can be patched up such that the rest of the proof plus the patched syllogism equals a correct proof.
Ian
Re: (Score:2)
Well, to paraphrase someone famous (perhaps Edison?), we've learned another way that doesn't work.
That's hardly the normal effect of peer review. Normally, mistaken approaches are not made public. Rather, they are known only to the author and the reviewer who rejects the submission (even more commonly, to the author alone).
Mathematicians don't tend to share failed approaches too much. They're not usually publishable. Which may be a darn shame, though I must confess I can't imagine wading through pages and pages of failed approaches to be sure I don't duplicate a previous error.
Re: (Score:2)
The _useful_ failures are the ones which at first pass the peer review process, an
Extended Peer Review (Score:2)
Re: (Score:2)
Re: (Score:2)
Re: (Score:3, Interesting)
Well, in all likelihood, we really didn't learn that.
Every now and then I take a crack at P=NP, and sometimes, I feel like I've really got a good proof  a program idea, that, when implemented, could FACTOR fairly quickly. I'll be practicing my "move over Al Gore, here's what the Nobel Prize is really about" speech as I'm typing my breakthrough in, and there will be some implementation detail th
Re: (Score:3, Informative)
Do you mean factor numbers? Even though it would be impressive to have an algorithm which factors numbers quickly, it wouldn't prove anything about the P=NP? problem. Factoring numbers is not known to be an NPcomplete problem, so solving it in polynomial time doesn't automatically imply that P=NP.
Re: (Score:3, Interesting)
I thought FACTOR was NPcomplete... if not, I think you could probably show it to be at least NPcomplete by taking the selection of prime numbers as a sort of a napsack problem against a set of "special numbers" or, numbers that one could generate primes with.
Indeed, the one insight that I tried out but failed at was trying to see if I could arrive at what those special numbers
Re: (Score:3, Interesting)
http://en.wikipedia.org/wiki/AKS_primality_test [wikipedia.org]
Regarding whether FACTOR is NPcomplete or not, most computer scientists don't think so.
Until its badly reported (Score:2)
Re: (Score:2)
A universal Turing machine is one which can simulate any other Turing machine. There are very many nonuniversal Turing machines, such as one which just writes an infinite sequence of '1's.
Re: (Score:2)
This sort of thing is science when it works at its best. Someone throws something out there, and another scientist checks it, and bam, we learn something.
I can't help thinking that we should wait for the authors response to the reviewer before we start judging the original work. Maybe the reviewer has a point, but maybe he doesn't.
Where are my meds? (Score:3, Funny)
Re: (Score:2)
I think he can find some here. [theodoregray.com]
Re: (Score:2)
part of Wolfram's reply cracks me up (Score:2)
I must admit that NKS is a bit over my head at the moment, though. So I could be reading something into it not meant.
Proven? (Score:2)
Was this proof the last chance to prove . . . whatever this thing is? Or has a specific attempt merely failed? (According to some email.)
Peter
Re: (Score:3, Funny)
Re:Proven? (Score:5, Funny)
Or, you know, English.
Fool me Once... (Score:2)
http://www.youtube.com/watch?v=RkSow7FtWmA/ [youtube.com]
Ah academics... (Score:2, Insightful)
Had I pushed my luck my second question would have been, who has verified this proof that has taught an automata theory course at a suitably accredited institution?
Re: (Score:3, Insightful)
Title Proven To Be Misleading (Score:5, Informative)
That opens another question (Score:2)
The question that keeps nagging me now, though, is, whether this is the only incident. Or rather, what if there're more "proofs" out there that are actually none? The way rese
Re: (Score:2, Interesting)
Yes, people check proofs. The name "Vaughan Pratt" comes to mind as an example.
Mathematicians are extremely dedicated, because there is incredible competition to get a Ph.D. in mathematics, and in order to get a job doing pure math one practically has to wait for someone to die. It is something one only does if one is
Re: (Score:2)
There is no point in doing that. If you can build a large selfconsistent mathematical structure on a basis of some results, especially a structure tha
Re: (Score:2)
math the religion (Score:3, Interesting)
Euler was probably one of the people responsible for some the old theorems that are the foundations of mathematics. Euler had some famous flaws in his early proofs (most notably his polyhedra formula and radical product proofs). These proofs were fortunatly repaired along
Can I get a refund (Score:3, Funny)
Re: (Score:2)
Re:Can I get a refund (Score:5, Funny)
Re: (Score:2, Funny)
Pay back? (Score:2)
Wolfram chimes in (Score:2, Informative)
http://cs.nyu.edu/pipermail/fom/2007October/012149.html [nyu.edu]
Re: (Score:2)
Wrong, that is NOT Wolfram's response (Score:2, Informative)
Alright, Einsteins.... (Score:2, Insightful)
Elmentary Mistake in Title (Score:3, Informative)
The prize stands  (Score:2, Funny)
prize money (Score:2)
Vaughn Pratt is confused (Score:5, Interesting)
Re:Vaughn Pratt is confused (Score:5, Informative)
Re: (Score:3, Insightful)
Since you are posting from the heart of the Wolfram Hype Machine (TM), perhaps you could comment on why the prize was announced by Wolfram Himself as being successfully awarded, when Martin Davis on the FOM list states that the committee members were not polled [nyu.edu].
This appears to be a flagrant violation of the rules for the prize [wolframscience.com], which state that "For the purposes of this prize, the treatment of universality in any particular submission must be considered acceptable by the Prize Committee."
To make my ques
Re: (Score:2, Interesting)
Re:Vaughn Pratt is confused (Score:4, Interesting)
Re:Vaughn Pratt is confused (Score:4, Informative)
Yeah, but Wolfram is an asshole (Score:2)
In my mind, if he wants to be god's gift to humanity, get on with a hard problem and quick dicking around with all this peripheral stuff. Find out if P=NP. Perfect nucl
Serious authority (Score:4, Informative)
I knew Pratt's daughter in college  nice woman. Wrote her term papers in LaTeX, on a Linux workstation, in 1996
The really damning thing from the FOM list... (Score:3, Interesting)
It says there that for the prize, the notion of universality is to be judged
acceptable by the Prize Committee.
I clicked on Prize Committee:
http://www.wolframscience.com/prizes/tm23/committee.html [wolframscience.com]
And found these members:
Lenore Blum
Greg Chaitin
Martin Davis
Ron Graham
Yuri Matiyasevich
Marvin Minsky
Dana Scott
Stephen Wolfram
Since the prize was awarded, what definition of universality was used during
the deliberations?
In particular, Martin Davis, Ron Graham, and Dana Scott are subscribers to
the FOM list. What definition of universality are they using?
Harvey Friedman
But, as I said in an earlier message, although the committee was kept
informed, we were never polled.
Martin
Martin Davis
Visiting Scholar UC Berkeley
Professor Emeritus, NYU
You heard this on /. first (Score:2)
glass houses (Score:4, Insightful)
the filter?"
Proofs containing elementary errors are published all the time. Peer review is, and always has been, only a way of weeding out some percentage of bad submissions. Peer review that is strict enough to ensure that only correct papers get published would also result in the rejection of many good papers. In fact, some good papers that have advanced science have contained elementary errors.
And people who sit in glass houses shouldn't throw stones. Looking through Pratt's publication list, the first two papers I came across on a topic that I know a lot about should never have passed peer review.
Everybody who publishes makes elementary mistakes and makes a fool of himself sometimes; one should respond kindly and gracefully.
Re:duh (Score:5, Funny)
Re:duh (Score:5, Informative)
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 [wikipedia.org] 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 ChurchTuring Thesis [wikipedia.org] 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 [wikipedia.org].
Anyway, a regular Turing Machine only computes one functionit's a singlepurpose machine. A Universal Turing Machine [wikipedia.org] 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
Re: (Score:2)
Now, my take on this whole thing was that the question is: whether there exists a way to encode* any Turing machine and string as input to this particular machine, such that it accepts if and only if the original machine does. And the answer seems to be, yes, if we can modify the machine's definition so that it's no longer a standard machine but rather one with an infinite repeating pattern on the tape. Well, that's fine, so long as we recognize that it's not the
Re: (Score:3, Interesting)
Gödel's incompleteness theorem (although I don't remember it so well) is more akin to the impossibility of the halting problem.
You can simulate anything (Score:2)
The trouble in simulating itself, is that you need to encode the input of the simulated machine.
So to simulate itself running, you need an encoding of itself to take as input.
This is problematic.
Re: (Score:2)
No, a universal Turing machine (or "The" Universal Turing Machine) can run all Turing machines including itself. Godel's theorem would have more to do with the fact that the UTM is not a decider, but the problem is still Turingacceptable ("semidecidable").
However, we can talk about higherorder Turing machines that make use of oracles to decide otherwise uncomputable problems, and
Summary for Average Joe Geek (formatting fixes) (Score:3, Interesting)
After following the links, I surmised the following:
Undergraduate Alex Smith submits a proof claiming that Wolfram's 2,3 Turing Machine is Universal. Next, Wolfram's staff review the proof for several *months*. Then, an announcement is made. Next, we have a notable computer scientist, Dr. Vaughn Pratt, who by the way, received his PhD under Donald Knuth, point out an "elementary" flaw in the proof. Wolfram's researchers and Wol
Re:wolfram inc. sinking deeper and deeper (Score:4, Informative)
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 nonuniversal machine which emulates the 23 machine OR that the 23 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 counterexample of paired pushdown automata).
What the student proved here may turn out to be an interesting and useful result (not the universality of 23 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 23 be an example)? If 23'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
Re: (Score:3, Funny)
Well, the very short version is that he is not a very nice person. And, basically, he said 'fuck you' to the traditional scientific community and went his separate way, turning from a prodigy to an outlaw. Which the traditional scientific community didn't appreciate much. And now they are, more or less, openly out to get him.
Which is, IMHO, unfortunate, because his scientific ideas should be judged on the