Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and learn more about it. Thanks for reading, and for making the site better!

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 author of this e-mail, which is incredibly insightful and articulate asked:

How did an argument containing such an elementary fallacy get through
the filter?

To be fair, I don't consider this that elementary a fallacy but when you break it down to if x + y = infinity then both x & y are infinity it does sound like a rather obvious pitfall. And, in response to his comment on catching it, it had not yet been through "the filter" as the original story stated:

Smith's proof will be published in the journal Complex Systems.

Meaning it had not yet been peer reviewed. But I agree with the author however abrasive he came off (although this is far higher than an elementary mistake) when he said:

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?

I can forgive an undergrad prof for missing this, his response was probably just to look at it and encourage the kid to submit it. Afterall, what motive would a professor have to read it?

But what should really be noted is what Wolfram himself is quoted as saying from the initial publishing of this proof:

"I had no idea how long it would take for the prize to be won," said Stephen Wolfram. "It could have taken a year, a decade, or a century. I'm thrilled it was so quick. It's an impressive piece of work."

Alright, that last sentence there is pretty damning. I have heard time and time again on Slashdot that Wolfram just took other people's work, that he had people working underneath him & that he didn't actually know what he was talking about in his book. This is some corroborating evidence, in my opinion.

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 Alex--too 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 (5, Informative)

Anonymous Coward | more than 6 years ago | (#21165481)

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.

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 (4, Informative)

Anonymous Coward | more than 6 years ago | (#21165869)

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 (4, Funny)

Anonymous Coward | more than 6 years ago | (#21166023)

"p.s. I have no connection to the book or the author. I'm just a very happy customer."

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

Re:The Filter (0)

Anonymous Coward | more than 6 years ago | (#21166059)

if x + y = infinity and y is finite, then x must be infinity

That should read "if x + y is infinite and y is finite, then x must be infinite"

Re:The Filter (0)

Anonymous Coward | more than 6 years ago | (#21166171)

More precisely, this is true for some definition of numbers in some particular theory. In constructive theories it is not necessarily true since it relies upon the law of the excluded middle to deduce that x must be finite, i.e., either x is finite or x is infinite (where infinite = not finite), and since x finite leads to a contradiction, then not x finite, thus x infinite.

Re:The Filter (0)

Anonymous Coward | more than 6 years ago | (#21165569)

It's frustrating that Wolfram and his "new kind of science" get so much coverage on media outlets like Slashdot. The mathematical community isn't impressed with how many copies of Mathematica one sells, nor how smart one demands one is. We are impressed by results. We don't see any. Can we please get over this megalomaniac?

Re:The Filter (0)

Anonymous Coward | more than 6 years ago | (#21165711)

Wolfram's 2,3 Machinedoesn't solve the language a^n*b^(n^2)*c^(n^3) of alphabet { a, b, c } for all n = 1, 2, 3,....

Dr. Pizarro

Re:The Filter (0)

Anonymous Coward | more than 6 years ago | (#21165955)

If one cannot demonstrate extraordinary ability, or superiority, then one can simply claim to possess such attributes. Somebody will be uninformed enough to believe you.

Alex Smith is the next Slava Pestov? (0)

Anonymous Coward | more than 6 years ago | (#21165571)

When his proof was first made available, the first thing I thought of was that Alex Smith was going to quickly become the next Slava Pestov or Hal Porter: a mathematically well-endowed young man of great stature, who makes a rapid succession of great discoveries, quickly making a name for himself as a genius and master.

I still think that Alex Smith has the skills and know-how to have his name become as well known as that of Slava Pestov. Even if he was bested this time, there will be other times, and he will prevail. I don't doubt that at all!

Re:Alex Smith is the next Slava Pestov? (0)

Anonymous Coward | more than 6 years ago | (#21165813)

I still think that Alex Smith has the skills and know-how to have his name become as well known as that of Slava Pestov.

Why do you think that? Shouldn't you wait for actual evidence first before you believe something?

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 peer-reviewed.

One doesn't use such positive language prior to peer-review. 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.)

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 peer-reviewed.

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:The Filter (1, Informative)

Anonymous Coward | more than 6 years ago | (#21166533)

Prior to being accepted for publication, a paper is sent to (presumably) experts in the field to review the paper to make sure the research is worthy of publication. That's what is meant by "peer-reviewed" journals.

Re:The Filter (0)

Anonymous Coward | more than 6 years ago | (#21166629)

Thanks. That clears that up for me. (Posted anonymously to avoid clutter for those browsing at higher levels)

When you submit a paper for publication in a journal, it gets sent away for peer review. If the peer reviewers like it and say it should be published, there will customarily be a delay between when you're notified and when it is actually published, sometimes a very substantial delay. You can then, generally, put the paper in your CV as "accepted for publication" in whatever journal it is, or, if necessary, cite it as such.

This paper sounds like it had reached the "accepted for publication" stage, which means it had indeed undergone, and passed, peer review. It's a bit embarrassing to have a paper make it through peer review with a serious mistake, caught soon after, but it does happen (if I recall correctly, it happened to Donald Knuth once).

I'd hate to be involved in either the submission or the review of that proof. I was rather intriuged when the proof was first posted, but I must say, this is something of an embarrassment

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.

As others [slashdot.org] have pointed out [slashdot.org] , no, it doesn't mean anybody's proven that it's not universal, it just means that this alleged proof of universality was incorrect.

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)

It appears to mean the proof has a defect in the same way that message passing in Windows has a defect [wikipedia.org] . As far as I can tell based on the article, Vaughan Pratt alleges that so much of the proof relies on the defect that the proof would need a complete rewrite.

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.

"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.

hey there kdawson (0, Offtopic)

Anonymous Coward | more than 6 years ago | (#21165419)

i hear that they need a new clown at mcdonalds. why don't you apply since your worthless as anything else.

Re:hey there kdawson (0)

Anonymous Coward | more than 6 years ago | (#21165781)

Hey, lay off the insults! Clowns have feelings too you insensitive clod!

I hope that this young man's girlfriend stands by him. So many women would be driven away from an otherwise suitable boyfriend who is skilled at the maths.

Re:Bad romantic consequence (-1, Troll)

Anonymous Coward | more than 6 years ago | (#21165583)

It was previously determined that in fact the "young man" is a fag. No "girlfriend" in the usual sense.

Then he'd be following rather closely in Turing's footsteps, wouldn't he? Now that it has been determined that "fags" have you beat in every walk of life, don't you think this is the time for you to stop using that derogatory term?

Or, the young man is a cigarette, in which case I withdraw my objection.

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.

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.

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

Re:Peer Review Rules (1, Insightful)

Anonymous Coward | more than 6 years ago | (#21165533)

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.

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.

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.

Quite. Failed approaches are a dime a dozen. There's no value in 99% of failed approaches to solving a mathematical problem, because those failures are due to eitherpersonal misconceptions or failure of rigor. If you pick an independent expert, then that expert won't have the same misconceptions (he'll have others) and won't make the same mistakes of calculation (but might make others), so he'll detect those kinds of errors.

The _useful_ failures are the ones which at first pass the peer review process,
and are found to be flawed years later. _Those_ are failures worth learning from, because they represent the kind of errors and misconceptions that most people in the field would make routinely, as evidenced by the fact that several independent experts did not catch the mistake during review.

Yep. We learn that "never hold the press conference until after peer review and acceptance of publication".

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 that, is just a detail, except that it blows my whole vision and I'm back to square one. And the thing is, when that happens, I never felt like I've wasted my time, because, even though the thing I made did not accomplish its goal, I still made something that satisfied a curiosity, and was able to see the outcome, and learn something, and in a space that I know that not a lot of people are in. It's not like fixing a database bug, that a million other programmers have fixed... it's a different land, about the roots of things, and that's really, very interesting in and of itself.

An optimist would say that this sort of thing is science when it is working fairly well, it would be sort of disappointing to find out that it wasn't ever going to get any better.

A universal Turing machine is one which can simulate any other Turing machine. There are very many non-universal Turing machines, such as one which just writes an infinite sequence of '1's.

Re:Peer Review Rules (0)

Anonymous Coward | more than 6 years ago | (#21166135)

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.

Yeah, but does the second scientist have to be such a prat about it?

Re:Peer Review Rules (0)

Anonymous Coward | more than 6 years ago | (#21166271)

But is learning that you learned nothing any more valuable than not learning anything to begin with?

Re:Peer Review Rules (0)

Anonymous Coward | more than 6 years ago | (#21166413)

As Chomsky showed half a century ago, linear bounded automata are not
universal Turing machines.

Well, hello-o? This is absolutely obvious! How could they not realize this? I mean, the universality of Turing machines is... gosh, what the heck does this mean?

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 Church-Turing 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 function--it's a single-purpose 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:duh (0)

Anonymous Coward | more than 6 years ago | (#21165933)

I wish I had more than one mod point to give you. Great explanation.

Am I misinterpreting things when I think that the combination of a universal Turing machine and Gõdel's undecidability theorem ends up proving that for every UTM there exists another Turing Machine (possibly itself, but irrelevant) that can't be simulated on it?

Re:duh (0)

Anonymous Coward | more than 6 years ago | (#21165777)

As Chomsky showed in January 2000, the non-universality of Turing machine 2,3 is entirely Bush's fault.

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?

this is how it's supposed to be. someone "has" to be the expert and it's probably an academic. although stephen wolfram was once an academic, he is no longer. he hasn't published a "real" peer reviewed paper in years. in fact, he has no business claiming to do science, "new" or otherwise.
wolfram is a software company, and stephen wolfram is a business man and charlatan scientist. by trying to pretend otherwise, he has gotten what he deserved: public humiliation. way to go! p.s. v6.0 mathematica is a bloated sac! thanx for making it worse.
btw/ i'm an arrogant academic.

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.

Not so fast... (0)

Anonymous Coward | more than 6 years ago | (#21165621)

The previous comment should have been read first:

"On the question of the paper itself, the table of contents, which is essential to following the dozens of cross-references in the paper, is useless. First the pages print without page numbers. Second the TOC gradually drifts out of sync with the physical pages, which are up to page 55 at the point where the TOC is indicating to look at page 44. I can't imagine anyone trying to actually read this without throwing up their hands after half an hour's struggling with it and sending it back for proper numbering.

The best I've been able to make of this paper under these trying conditions is that it first proves that two machines working together, the subject 2,3 machine and an encoder, constitute a universal team. It is then shown that the encoder is not universal, from which it is inferred that the 2,3 machine must be universal.

Evidently I've misunderstood something, since two PDA's working together constitute a universal team (use the two stacks to simulate the two halves of the tape on either side of the head), but the fact that one of them is not universal does not entail the universality of the other. No amount of fiddling with "weaker" definitions of universality along the lines I indicated above can change that fact, since both PDA's are equally non-universal in an entirely unambiguous way."

In other words, it's not clear that those criticizing the proof actually understand the proof. I'm not defending Smith's work, nor am I defending NKS, however, it is possible, although unlikely, that the respondents are missing something in Smith's work.

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.

That proof ain't a simple logic tree that you can follow in your head and nod. I for sure could not have found the error (though my degree isn't in math, and it's been a while...). Sure, those people are closer to the core of top level math, but still... I mean, don't you make mistakes when you program? Despite being a top level coder?

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)?

Re:That opens another question (0)

Anonymous Coward | more than 6 years ago | (#21165793)

It means even the math is an empirical discipline. Hehe.

Re:That opens another question (0)

Anonymous Coward | more than 6 years ago | (#21166079)

Not really.

You just witnessed peer review in action. Because it was portrayed as Ultimate Truth you are just inclined to think so, in fact it was just premature fanfares and fireworks of Wolfram itself and none else (perhaps his committee). And this seems to falsify that.

I'd see this as quiet opposite as you do, as proof that peer review works. It was just released as peer reviewed and falsified. Note: Wolfram's committee was not peer review!

Re:That opens another question (0)

Anonymous Coward | more than 6 years ago | (#21166579)

Actually, if the committee had reviewed it, I would consider that peer review (assuming they were not paid by Wolfram Media) -- insofar as a candidate journal article passing the review of anonymous referees is peer review -- since the committee contains heavyweights like Dana Scott [wikipedia.org] , Martin Davis [wikipedia.org] , Yuri Matiyasevich [wikipedia.org] , etc.

Any work that was reviewed by and deemed correct by all the members of that committee [wolframscience.com] would have passed a far more stringent peer review process than just about any Journal paper. Withstanding extended peer review after publication is another matter though.

Having said that, it looks like the committee did not actually review the paper in this case, but were merely "kept informed" (whatever that means), as Martin Davis states here [nyu.edu] .

So, an undergrad makes a relatively silly mistake in a proof, and the mistake is found before his paper even gets through the referee process. What's the big deal that keeps nagging at you?

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 both extremely talented and in love with the subject. So, any new result in a field is going to be looked at carefully -- for fun if nothing else.

Re:That opens another question (1, Insightful)

Anonymous Coward | more than 6 years ago | (#21166131)

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).

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)?

There is no point in doing that. If you can build a large self-consistent mathematical structure on a basis of some results, especially a structure that is useful, it is a positive result. If a foundational theorem was wrong, you would not have been able to build anything on top of it -- soon you would run into an inconsistency, an absurdity, and you would see that something is wrong. If an assumption does not result in an absurdity, then it's perfectly valid to build mathematical structures on top of it; in fact, that is how many areas of mathematics got created. People either found that a certain axiom could be removed, or that additional assumptions opened up interesting and nontrivial possibilities.

So much talk, so little value. Holy shit, I miss the days of Feynman and Einstein and Max Born. What is happening to the world? Must everyone defend to the death every silly mistake they make? If you're wrong, you're wrong; we don't want to hear about your philosophy in life and your contributions to mankind and your plans for the future, just apologize and get on with science. Jeezus.

It doesn't directly address Pratt's point, but it addresses some of the things raised in the discussion that followed Pratt's post regarding universality.

Wrong, that is NOT Wolfram's response (2, Informative)

Incorrect - that is not Wolfram's response to Pratt's message, it is a response to an earlier message. Compare the dates.

MOD PARENT DOWN. IRRELEVANT LINK, KARMA WHORE (0)

Anonymous Coward | more than 6 years ago | (#21166615)

Er, WTF? This should be modded -1, offtopic, not 5, informative.

The link you posted has ABSOLUTELY NOTHING to do with the refutation of the proof. It's just Wolfram talking about the whole 2,3 Turing machine, not his response (as you would mislead others to believe) to the refutation---heck, look at the date. I didn't know Wolfram invented a time machine yet.

...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.

Um, no, the problem is there were no proof reviewers. This was just Wolfram being overly eager for a chance to once again assert his superiority over the scientific community.

"As far as I know, no member of the committee has passed on the
validity of this 40 page proof. The determination that Smith's proof
is correct seems to have been made entirely by the Wolfram
organization. My understanding is that the I/O involves complex encodings." http://cs.nyu.edu/pipermail/fom/2007-October/012132.html [nyu.edu]

The subject of this article is wrong - we do not know that Wolfram's 2,3 Turing Machine is not universal. We only know (assuming the proof really is in error) that there is no proof either way as to whether it is universal.

The prize stands - (2, Funny)

Anonymous Coward | more than 6 years ago | (#21166105)

No, Vaughn Pratt is confused. There is a post from on the FOM mailing list that explains the confusion.
There are subtle issues concerning the nature of computational universality in the presence of infinite initial conditions.
Vaughn Pratt is probably remembering work from the 1950s on computational universality, which does not address these issues.
There are different definitions that could be given for computational universality with infinite initial conditions. Alex Smith's proof was
verified with a particular, natural, definition that was chosen for the prize.
So all is well. The 2,3 Turing machine's universality has not been toppled with one email and the personal opinion of Vaughn Pratt.
What has happened, though, is that questions that have not been discussed since the 1950s are (this week) back in vogue again.

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 [wolframscience.com]
This is how math is done... trying to poke holes in proofs.

I don't understand the math behind this argument and counter-argument, but Vaughan Pratt is a CS legend [wikipedia.org] 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.

I knew Pratt's daughter in college -- nice woman. Wrote her term papers in LaTeX, on a Linux workstation, in 1996:P

The really damning thing from the FOM list... (2, Interesting)

## The Filter (5, Interesting)

## eldavojohn (898314) | more than 6 years ago | (#21165381)

thatelementary a fallacy but when you break it down to if x + y = infinity then both x & y are infinity it does sound like a rather obvious pitfall. And, in response to his comment on catching it, it had not yet been through "the filter" as the original story stated:But what should really be noted is what Wolfram

himselfis 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 Alex--too 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

thatwould be poetic justice.## Re:The Filter (5, Informative)

## Anonymous Coward | more than 6 years ago | (#21165481)

## Re:The Filter (5, Informative)

## jnana (519059) | more than 6 years ago | (#21165755)

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

isuniversal, 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

isuniversal). 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 (4, Informative)

## Anonymous Coward | more than 6 years ago | (#21165869)

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 (4, Funny)

## Anonymous Coward | more than 6 years ago | (#21166023)

Hey Michael, long time no post.

## Re:The Filter (3, Insightful)

## EveLibertine (847955) | more than 6 years ago | (#21165989)

## Re:The Filter (0)

## Anonymous Coward | more than 6 years ago | (#21166059)

if x + y = infinity and y is finite, then x must be infinityThat should read "if x + y

is infiniteand y is finite, then x must beinfinite"## Re:The Filter (0)

## Anonymous Coward | more than 6 years ago | (#21166171)

## Re:The Filter (0)

## Anonymous Coward | more than 6 years ago | (#21165569)

## Re:The Filter (0)

## Anonymous Coward | more than 6 years ago | (#21165711)

Wolfram's 2,3 Machinedoesn't solvethe languagea^n*b^(n^2)*c^(n^3)of alphabet {a,b,c} for alln = 1, 2, 3, ....Dr. Pizarro## Re:The Filter (0)

## Anonymous Coward | more than 6 years ago | (#21165955)

claimto possess such attributes. Somebody will be uninformed enough to believe you.## Alex Smith is the next Slava Pestov? (0)

## Anonymous Coward | more than 6 years ago | (#21165571)

I still think that Alex Smith has the skills and know-how to have his name become as well known as that of Slava Pestov. Even if he was bested this time, there will be other times, and he will prevail. I don't doubt that at all!

## Re:Alex Smith is the next Slava Pestov? (0)

## Anonymous Coward | more than 6 years ago | (#21165813)

## Re:The Filter (1)

## phiwum (319633) | more than 6 years ago | (#21165997)

One doesn't use such positive language prior to peer-review. 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:The Filter (1)

## wasted (94866) | more than 6 years ago | (#21166435)

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:The Filter (1, Informative)

## Anonymous Coward | more than 6 years ago | (#21166533)

## Re:The Filter (0)

## Anonymous Coward | more than 6 years ago | (#21166629)

## Paper stages (1)

## Goonie (8651) | more than 6 years ago | (#21166643)

This paper sounds like it had reached the "accepted for publication" stage, which means it had indeed undergone, and passed, peer review. It's a bit embarrassing to have a paper make it through peer review with a serious mistake, caught soon after, but it does happen (if I recall correctly, it happened to Donald Knuth once).

## Ouch (2, Informative)

## JoeShmoe950 (605274) | more than 6 years ago | (#21165391)

## Re:Ouch (1)

## STrinity (723872) | more than 6 years ago | (#21166639)

## Is not universal? (4, Insightful)

## MarsDefenseMinister (738128) | more than 6 years ago | (#21165401)

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

## No, just not proven (3, Informative)

## billstewart (78916) | more than 6 years ago | (#21165681)

notuniversal, it just means thatthisalleged proof of universality was incorrect.## Back to the drawing board (2, Informative)

## tepples (727027) | more than 6 years ago | (#21165747)

## Bad Headline (5, Informative)

## EvanED (569694) | more than 6 years ago | (#21165411)

Wolfram's 2,3 Turing Machine Not UniversalThat's not, from my reading, what is true. What is true is that the proof is wrong, which means that it

maynot be universal, but reverts back to the unknown state.## Re:Bad Headline (1)

## Nimey (114278) | more than 6 years ago | (#21165679)

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 (5, Funny)

## MillionthMonkey (240664) | more than 6 years ago | (#21165867)

## "from the whoa-not-so-fast-there-big-fella dept" (5, Funny)

## ZorbaTHut (126196) | more than 6 years ago | (#21165417)

"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.

## hey there kdawson (0, Offtopic)

## Anonymous Coward | more than 6 years ago | (#21165419)

## Re:hey there kdawson (0)

## Anonymous Coward | more than 6 years ago | (#21165781)

## Bad romantic consequence (5, Funny)

## Hao Wu (652581) | more than 6 years ago | (#21165431)

## Re:Bad romantic consequence (-1, Troll)

## Anonymous Coward | more than 6 years ago | (#21165583)

## Re:Bad romantic consequence (1)

## Torvaun (1040898) | more than 6 years ago | (#21166001)

Or, the young man is a cigarette, in which case I withdraw my objection.

## Re:Bad romantic consequence (1)

## fizzding (1171839) | more than 6 years ago | (#21166415)

## Peer Review Rules (4, Insightful)

## tjstork (137384) | more than 6 years ago | (#21165437)

## Re:Peer Review Rules (1)

## Reaperducer (871695) | more than 6 years ago | (#21165473)

## Re:Peer Review Rules (1, Insightful)

## Anonymous Coward | more than 6 years ago | (#21165533)

## Re:Peer Review Rules (1)

## Wonko the Sane (25252) | more than 6 years ago | (#21165551)

## Re:Peer Review Rules (3, Insightful)

## ispeters (621097) | more than 6 years ago | (#21165555)

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:Peer Review Rules (1)

## phiwum (319633) | more than 6 years ago | (#21166021)

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:Peer Review Rules (1)

## martin-boundary (547041) | more than 6 years ago | (#21166231)

The _useful_ failures are the ones which at first pass the peer review process, and are found to be flawed years later. _Those_ are failures worth learning from, because they represent the kind of errors and misconceptions that most people in the field would make routinely, as evidenced by the fact that several independent experts did not catch the mistake during review.

## Re:Peer Review Rules (1)

## JanneM (7445) | more than 6 years ago | (#21165593)

## Re:Peer Review Rules (2, Interesting)

## tjstork (137384) | more than 6 years ago | (#21165797)

Yep. We learn that "never hold the press conference until after peer review and acceptance of publication".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 that, is just a detail, except that it blows my whole vision and I'm back to square one. And the thing is, when that happens, I never felt like I've wasted my time, because, even though the thing I made did not accomplish its goal, I still made something that satisfied a curiosity, and was able to see the outcome, and learn something, and in a space that I know that not a lot of people are in. It's not like fixing a database bug, that a million other programmers have fixed... it's a different land, about the roots of things, and that's really, very interesting in and of itself.

## Re:Peer Review Rules (1)

## maxume (22995) | more than 6 years ago | (#21165829)

## Until its badly reported (1)

## EmbeddedJanitor (597831) | more than 6 years ago | (#21165873)

## Re:Until its badly reported (1)

## Michael Woodhams (112247) | more than 6 years ago | (#21166055)

A universal Turing machine is one which can simulate any other Turing machine. There are very many non-universal Turing machines, such as one which just writes an infinite sequence of '1's.

## Re:Peer Review Rules (0)

## Anonymous Coward | more than 6 years ago | (#21166135)

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.Yeah, but does the second scientist have to be such a prat about it?

## Re:Peer Review Rules (0)

## Anonymous Coward | more than 6 years ago | (#21166271)

## Re:Peer Review Rules (0)

## Anonymous Coward | more than 6 years ago | (#21166413)

## duh (-1, Redundant)

## zanderredux (564003) | more than 6 years ago | (#21165453)

From TFA:

Well, hello-o? This is absolutely obvious! How could they not realize this? I mean, the universality of Turing machines is... gosh, what the heck does this mean?

## Re:duh (4, Funny)

## schon (31600) | more than 6 years ago | (#21165471)

## Re:duh (5, Informative)

## ispeters (621097) | more than 6 years ago | (#21165751)

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 Church-Turing 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 function--it's a single-purpose 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:duh (0)

## Anonymous Coward | more than 6 years ago | (#21165933)

## On a slightly related note... (1)

## mdenham (747985) | more than 6 years ago | (#21166663)

## Re:duh (0)

## Anonymous Coward | more than 6 years ago | (#21165777)

## Where are my meds? (2, Funny)

## synthespian (563437) | more than 6 years ago | (#21165465)

## Re:Where are my meds? (1)

## Megane (129182) | more than 6 years ago | (#21165601)

I think he can find some here. [theodoregray.com]

## part of Wolfram's reply cracks me up (1)

## Danny Rathjens (8471) | more than 6 years ago | (#21165507)

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? (1)

## pete-classic (75983) | more than 6 years ago | (#21165529)

ProvenUniversal"?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:Proven? (3, Funny)

## Anonymous Coward | more than 6 years ago | (#21165603)

## Re:Proven? (5, Funny)

## EvanED (569694) | more than 6 years ago | (#21165743)

Apparently some Slashdot editors have still to defeat the gargantuan misteries of propositional calculus...Or, you know, English.

## Re:Proven? (1)

## pete-classic (75983) | more than 6 years ago | (#21166133)

-Peter

## Fool me Once... (1)

## AttillaTheNun (618721) | more than 6 years ago | (#21165599)

http://www.youtube.com/watch?v=RkSow7FtWmA/ [youtube.com]

## Ah academics... (2, Insightful)

## SilverJets (131916) | more than 6 years ago | (#21165607)

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... (1)

## opypod (1169579) | more than 6 years ago | (#21165821)

## Re:Ah academics... (2, Insightful)

## mrpeebles (853978) | more than 6 years ago | (#21165845)

## Not so fast... (0)

## Anonymous Coward | more than 6 years ago | (#21165621)

"On the question of the paper itself, the table of contents, which is

essential to following the dozens of cross-references in the paper, is

useless. First the pages print without page numbers. Second the TOC

gradually drifts out of sync with the physical pages, which are up to

page 55 at the point where the TOC is indicating to look at page 44. I

can't imagine anyone trying to actually read this without throwing up

their hands after half an hour's struggling with it and sending it back

for proper numbering.

The best I've been able to make of this paper under these trying

conditions is that it first proves that two machines working together,

the subject 2,3 machine and an encoder, constitute a universal team. It

is then shown that the encoder is not universal, from which it is

inferred that the 2,3 machine must be universal.

Evidently I've misunderstood something, since two PDA's working together

constitute a universal team (use the two stacks to simulate the two

halves of the tape on either side of the head), but the fact that one of

them is not universal does not entail the universality of the other. No

amount of fiddling with "weaker" definitions of universality along the

lines I indicated above can change that fact, since both PDA's are

equally non-universal in an entirely unambiguous way."

In other words, it's not clear that those criticizing the proof actually understand the proof. I'm not defending Smith's work, nor am I defending NKS, however, it is possible, although unlikely, that the respondents are missing something in Smith's work.

## Title Proven To Be Misleading (4, Informative)

## yerdaddie (313155) | more than 6 years ago | (#21165639)

## That opens another question (1)

## Opportunist (166417) | more than 6 years ago | (#21165663)

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)?

## Re:That opens another question (0)

## Anonymous Coward | more than 6 years ago | (#21165793)

## Re:That opens another question (0)

## Anonymous Coward | more than 6 years ago | (#21166079)

Not really.

You just witnessed peer review in action. Because it was portrayed as Ultimate Truth you are just inclined to think so, in fact it was just premature fanfares and fireworks of Wolfram itself and none else (perhaps his committee). And this seems to falsify that.

I'd see this as quiet opposite as you do, as proof that

peer review works. It was just released as peer reviewed and falsified.Note: Wolfram's committee was not peer review!## Re:That opens another question (0)

## Anonymous Coward | more than 6 years ago | (#21166579)

Actually, if the committee had reviewed it, I would consider that peer review (assuming they were not paid by Wolfram Media) -- insofar as a candidate journal article passing the review of anonymous referees is peer review -- since the committee contains heavyweights like Dana Scott [wikipedia.org] , Martin Davis [wikipedia.org] , Yuri Matiyasevich [wikipedia.org] , etc.

Any work that was reviewed by and deemed correct by all the members of that committee [wolframscience.com] would have passed a far more stringent peer review process than just about any Journal paper. Withstanding extended peer review after publication is another matter though.

Having said that, it looks like the committee did not actually review the paper in this case, but were merely "kept informed" (whatever that means), as Martin Davis states here [nyu.edu] .

## Re:That opens another question (2, Interesting)

## samweber (71605) | more than 6 years ago | (#21166127)

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 both extremely talented and in love with the subject. So, any new result in a field is going to be looked at carefully -- for fun if nothing else.

## Re:That opens another question (1, Insightful)

## Anonymous Coward | more than 6 years ago | (#21166131)

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:That opens another question (1)

## alienw (585907) | more than 6 years ago | (#21166555)

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)?There is no point in doing that. If you can build a large self-consistent mathematical structure on a basis of some results, especially a structure that is useful, it is a positive result. If a foundational theorem was wrong, you would not have been able to build anything on top of it -- soon you would run into an inconsistency, an absurdity, and you would see that something is wrong. If an assumption does not result in an absurdity, then it's perfectly valid to build mathematical structures on top of it; in fact, that is how many areas of mathematics got created. People either found that a certain axiom could be removed, or that additional assumptions opened up interesting and nontrivial possibilities.

## Can I get a refund (3, Funny)

## stinkfish (675397) | more than 6 years ago | (#21165717)

## Re:Can I get a refund (0)

## Anonymous Coward | more than 6 years ago | (#21165753)

## Re:Can I get a refund (1)

## MillionthMonkey (240664) | more than 6 years ago | (#21165783)

## Pay back? (1)

## PHAEDRU5 (213667) | more than 6 years ago | (#21165819)

## Re:Pay back? (2, Funny)

## ruinous (1123167) | more than 6 years ago | (#21166631)

## Wolfram chimes in (2, Informative)

## snark23 (122331) | more than 6 years ago | (#21165851)

http://cs.nyu.edu/pipermail/fom/2007-October/012149.html [nyu.edu]

## Re:Wolfram chimes in (1)

## Plutonite (999141) | more than 6 years ago | (#21166019)

## Re:Wolfram chimes in (1)

## Vickor (867233) | more than 6 years ago | (#21166041)

## Re:Wolfram chimes in (1)

## snark23 (122331) | more than 6 years ago | (#21166203)

## Wrong, that is NOT Wolfram's response (2, Informative)

## Weyoun (174697) | more than 6 years ago | (#21166371)

## MOD PARENT DOWN. IRRELEVANT LINK, KARMA WHORE (0)

## Anonymous Coward | more than 6 years ago | (#21166615)

The link you posted has ABSOLUTELY NOTHING to do with the refutation of the proof. It's just Wolfram talking about the whole 2,3 Turing machine, not his response (as you would mislead others to believe) to the refutation---heck, look at the date. I didn't know Wolfram invented a time machine yet.

## Turing machine and Linux? (1)

## Soleen (925936) | more than 6 years ago | (#21165859)

Does it run Linux?No certain anwer yet again.

## kdawson can't do math either (-1, Flamebait)

## Anonymous Coward | more than 6 years ago | (#21165875)

fuck off and die, kdawson. you're a sack of rabbit turds. a stupid dirty butthole.

## Alright, Einsteins.... (1, Insightful)

## Urusai (865560) | more than 6 years ago | (#21165881)

## Re:Alright, Einsteins.... (1)

## SimonBelmont (1089255) | more than 6 years ago | (#21166261)

"We're excited to announce that the $25,000 Wolfram 2,3 Turing Machine Research Prize has been won." http://cs.nyu.edu/pipermail/fom/2007-October/012120.html [nyu.edu]

"As far as I know, no member of the committee has passed on the validity of this 40 page proof. The determination that Smith's proof is correct seems to have been made entirely by the Wolfram organization. My understanding is that the I/O involves complex encodings." http://cs.nyu.edu/pipermail/fom/2007-October/012132.html [nyu.edu]

## Elmentary Mistake in Title (2, Informative)

## Cyberllama (113628) | more than 6 years ago | (#21165909)

## Obligatory... (0)

## Anonymous Coward | more than 6 years ago | (#21165937)

## Subject is wrong (1)

## thomasoa (759290) | more than 6 years ago | (#21165967)

## The prize stands - (2, Funny)

## Anonymous Coward | more than 6 years ago | (#21166105)

## prize money (1)

## drDugan (219551) | more than 6 years ago | (#21166191)

## Wow... (1)

## graviplana (1160181) | more than 6 years ago | (#21166235)

## Vaughn Pratt is confused (5, Interesting)

## evgalois (1181567) | more than 6 years ago | (#21166345)

## Re:Vaughn Pratt is confused (5, Informative)

## Ed Pegg (613755) | more than 6 years ago | (#21166611)

## Cut him some slack. (1)

## Dean Hougen (970749) | more than 6 years ago | (#21166473)

## Serious authority (3, Informative)

## Emnar (116467) | more than 6 years ago | (#21166525)

The Art of Computer Programmingseries by Donald Knuth. And if you don't care who Knuth is, then you probably don't care about this post at all.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... (2, Interesting)

## Bob Hearn (61879) | more than 6 years ago | (#21166677)

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