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.

Is not universal?

[MarsDefenseMinister]

What does that mean? Does this mean that it hasn't been proven to be universal (which is the case if there was just a bug in the proof) or is there another proof that shows the machine is not universal?

kdawson, not proven to be universal and proven to be not universal are two different things.

Peer Review Rules

[tjstork]

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.

Re:Peer Review Rules

[Anonymous Coward]

We learned that the proof was mistaken. That's how we advance you know, can't hit homerun every time. Even then, we need to check and be able to tell if it cleared the fence or not.

Re:Peer Review Rules

[ispeters]

Did we learn something? As far as I can tell we're back where we started.

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

Ah academics...

[SilverJets]

I love the arrogance.

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:Ah academics...

[mrpeebles]

I agree he could have been more diplomatic. Still, it is pretty crappy to let a student (an undergrad if I recall) publish a now embarrassing proof with an error that is apparently pretty obvious to an expert. That is sort of how I read this comment.

Alright, Einsteins....

[Urusai]

...so there is an assertion that the putative proof is flawed. How many of you read the proof and can verify that the assertion is correct? Accusing the proof reviewers of laxity seems kind of hypocritical.

Re:The Filter

[EveLibertine]

Regardless, the guy that wrote that email is a prat.

Re:That opens another question

[Anonymous Coward]

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 research works, we rely on proven concepts to build our own research on top of it. What if our foundations are shaky? Does anyone actually test old theorems that were proven (or falsified)?

You're making a mountain out of a mole hill. In this case a student published a proof in a journal of non-peer reviewed work. When it was peer reviewed an error was found. The fact that one young mathematician made an error should hardly cause you to lose faith in the validity of every other theorem proven to date (especially the ones that other scientists actually looked at).

Re:Vaughn Pratt is confused

[Anonymous Coward]

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 question crystal clear: how is it possible that the committee deemed the proof (or its treatment of universality) acceptable when at least some of them were not polled as to whether they thought the proof was acceptable?

p.s. Please don't appeal to a "New Kind of Logic" or a "New Kind of English" in your answer.

glass houses

[m2943]

Pratt asks: "How did an argument containing such an elementary fallacy get through
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:Peer Review Rules

[darkstar949]

Actually, a polynomial algorithm for an NP-complete problem will not prove that P=NP for all cases in and of itself - the algorithm might just prove it for that family of problems, or the existence might prove that the problem was not in fact NP complete.