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.

The Filter

[eldavojohn]

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

[tjstork]

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

[samweber]

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.

Vaughn Pratt is confused

[evgalois]

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.

The really damning thing from the FOM list...

[Bob Hearn]

... is this:

http://www.wolframscience.com/prizes/tm23/technicaldetails.html [wolframscience.com]

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

followed by:

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

Let's see Wolfram explain that.

Re:On a slightly related note...

[chgros]

No, not at all, for a Turing machine to be universal means that it can simulate any other Turing machine.
Gödel's incompleteness theorem (although I don't remember it so well) is more akin to the impossibility of the halting problem.

math the religion

[slew]

Sadly, it seems to be the case that there is only a small fraction of the math and science worshiper that have fallen from the "purer" faith and dare question the high priestess of truth promulgated by the science and math establishment.

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 the way as people discovered them.

Like many religions, math has beatified some of it's saints, and no more famous than Saint Fermat. Now days, the conventional wisdom is that Fermat's famous margin proof was likely to be invalid, but for many years, true believers refused to knock down his alleged proof even as the evidence to the contrary mounted. Sadly as with many artifacts for religion, the elaboration of the proof doesn't exist, we only have the gospals of the proof and the interpreter of the gospal to tell us the story of this feat.

The four-color map theorem was another prophecy that has a storied history. The chancellor of the Dioces of London (mathmetician sir alfred kempe), published a proof the the four-color map theorem that went unchallenged for 11 years when the reformation of Percy Heawood showed the proof to be incorrect. The current standing proof of the four-color map theorem is a computer proof. That fact alone might ring some alarm bells with you.

No doubt that as the understanding of math advances, more proofs will be reconsidered and more often than not open up new avenues for new discoveries. There will still be those of the "pure" faith (the fanbois) that cling to the proclamation of the establishment and say everything is "settled" and attempt to silence the heretics, but the doubters that are testing the old "proofs" may be the ones that actual people praticing "real" faith. Time will tell.

Give Wolfram some credit

[Starky]

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.

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:The Filter

[Workaphobia]

Am I correct in thinking that the issue is that the given proof proves that the wrong system is universal? I read part of the proof but I'm unfamiliar with some of their terminology and models. From what I can tell, the question was whether a particular Turing machine was universal, and the answer was "yes, with some minor modifications", and the prize panel decided that this adaptation fit within the definition of the problem.

Re:Vaughn Pratt is confused

[ortholattice]

From the post [wolframscience.com] you mention:

Smith's use of non-repetitive infinite initial conditions is controversial, but is a natural extension of current definitions which allow infinite repetitive initial conditions. We hope that the ensuing discussion will enrich debate in the scientific community concerning the nature of computational universality.

Whenever a generalization of the definition of a universal Turing machine is put forward, that the status of some machines will necessarily change from 'non-universal' to 'universal'. It is a challenge to explicitly construct a machine with initial conditions similar in spirit to Smith's, that is obviously too simple to be considered universal, and which is performing a universal computation with those infinite initial conditions.

"The status of some machines will necessarily change from 'non-universal' to 'universal'"??? This sounds like a cop-out to justify the error in the proof: re-define the problem so the proof fits it.

Let's generalize the definition of FLT (Fermat's Last Theorem) to include n=2. It seems to me this is a "natural extension" of its current definition. Guess what, I have a truly marvelous proof that FLT in a generalized sense is false, which the margin of this post is not too narrow to contain: 3^2+4^2=5^2.

Seriously, once you have fixed the statement of a problem in mathematics, there is no "controversy" as to whether it is true, false, or undecidable, and a correct proof will show which one of these three is be the case. Someone else can't come along and show that another of these three is the case, unless one of the proofs is flawed (or unless the foundations of math are inconsistent, which would be a major discovery in itself). In this case it appears that Smith's proof is flawed and simply does not prove the stated problem. It sounds like Wolfram Research is twisting the definition of the problem to save face, rather than just admitting the proof is flawed and moving on.

Earlier in that post,

Alex Smith did not only show that the encoding of the initial condition is non-universal. He showed that the encoding is very computationally weak and then concludes that the Turing machine is universal in a generalized sense.

Well, allow me to generalize even more. I'll define anything that can perform the computing done by an AND gate as universal in a super-generalized sense. I conclude that a Turing machine is universal in a super-generalized sense. Let me sell you my line of AND gate computers. If you complain that they can't do much, I'll merely point to my proof that they are universal in a super-generalized sense, just like Turing machines.

Re:Vaughn Pratt is confused

[evgalois]

Here is the explanation about the suposed "flaw", which of course it is not: http://forum.wolframscience.com/showthread.php?s=&threadid=1472 [wolframscience.com] And my comments on the guy that thinks that the universality definition was changed for the prize benefit (I am surprised about how many people write about this without knowing a bit of the subject and trying to sound technical talking about "AND gates" completely nonsense): Concerning the definition of universality, a halting state or halting instruction wasn't a requirement. This is a common usage nowadays in the field of small universal Turing machines, which is a generalization of previous definitions. If there is no clear definition is because there is no clear-cut, established procedure to determine when an initial condition is computationally simple enough to be acceptable. Some would wish universal computation stick to a finite initial condition with an unbounded tape filled with "blanks", because that's the only case where the theory is entirely clear. However, others accept generalizations such as periodic "blank" words as long as they remain computationally simple enough (possibly generated in the same fashion as an unbounded "blank" tape). So Alex Smith's use of a non-periodic but still sufficiently computationally simple background is a natural generalization of this sort. The key point is that the background can be set up without doing universal computation, so the 2,3 machine itself actually carries out the computation. 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. We particularly hope that his methods can be extended to other similar proofs.

Re:The Filter

[JohnsonJohnson]

"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

The charge against Wolfram is that he did not give credit to one of his assistants who proved that a particular 2 state 1 dimensional finite automaton with a neighborhood of 1 was universal. The assistant had also signed a contract that effectively prevented him from releasing the proof on the assistant's own.

& that he didn't actually know what he was talking about in his book. This is some corroborating evidence, in my opinion.

Wolfram's A New Kind of Science makes claims about facts in a wide variety of areas of science especially chaos theory (or nonlinear dynamics or whatever it's called this week) and biology which were either known, discovered by someone unaffiliated with Wolfram, or known to be false (the last being Wolfram's doomed program of a TOE based on network automata). Most of these problems arise from the tone of the book which does not make clear what's original about Wolfram's work (aside from exhaustive study of 1D automata and some simply axiom systems not much) and what is a review of other work. That doesn't mean Wolfram doesn't know what he's talking about, he knows quite a bit, but it's hard to parse that from what is conjecture and as in any major work of such length there are errors.

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.

Wolfram's reputation as a genius rests on his precociousness as a youth (Wolfram was educated at Eton, Oxford, and Caltech. He published his first scientific paper at the age of 15, and had received his Ph.D. in theoretical physics from Caltech by the age of 20. [stephenwolfram.com]) and some rather esoteric contributions to the field of particle physics. He also did some early and significant (although perhaps not as significant to other practitioners as to Wolfram himself) work on cellular automata and other discrete systems. A New Kind of Science was Wolfram's attempt to leap from being a bright but unknown outside of his field physicist/mathematician (eg. Ed Witten although since Wolfram didn't publish anything between the early 80's and 2004 or so the comparison is probably unfair to Witten) to Newton, Einstein, or at least Gauss or Euler levels of fame. He failed, but that doesn't mean there is no value in the book, it can serve as a launching point into various not otherwise popular fields of study. I recommend keeping the criticism of the book by area experts close at hand but the book itself can provoke questions and interest in non-experts although it's probably of little value to experts (as compared to the length of the tome).

Re:Peer Review Rules

[tjstork]

Factoring numbers is not known to be an NP-complete problem, so solving it in polynomial time doesn't automatically imply that P=NP

I thought FACTOR was NP-complete... if not, I think you could probably show it to be at least NP-complete 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 were by recursively defining every integer as the addition of two fractions just to see if I could tease out some relationship. What I got was a remarkably inefficient way to create prime numbers.

I just do this for a hobby. I wonder if the problem is, really, that actually generating a prime number is NP-Complete?

Re:Peer Review Rules

[rbarreira]

How can generating a prime number be NP-complete? Do you mean testing if a number is prime or not? That problem is in P:

http://en.wikipedia.org/wiki/AKS_primality_test [wikipedia.org]

Regarding whether FACTOR is NP-complete or not, most computer scientists don't think so.

Comment removed

[account_deleted]

Comment removed based on user account deletion