## Wolfram's 2,3 Turing Machine Not Universal 284

Posted
by
kdawson

from the whoa-not-so-fast-there-big-fella dept.

from the whoa-not-so-fast-there-big-fella 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)

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:Peer Review Rules (Score:3, Interesting)

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 (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 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 (Score:5, Interesting)

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

## Re:On a slightly related note... (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.

## 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 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 (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:The Filter (Score:3, Interesting)

## Re:Vaughn Pratt is confused (Score:2, Interesting)

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

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 (Score:4, Interesting)

## Re:The Filter (Score:2, Interesting)

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.

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'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 (Score:3, Interesting)

Factoring numbers is not known to be an NP-complete problem, so solving it in polynomial time doesn't automatically imply that P=NPI 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 (Score:3, Interesting)

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.

## Summary for Average Joe Geek (formatting fixes) (Score:3, Interesting)

Sorry about the lack of spacing. I forgot I was posting HTML. Re-do here: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 Wolfram himself then respond to this objection.

It appears that: First, the headline "...Turing Machine is NOT Universal" is false. The criticism was of the *proof* that it is universal; no claim was made nor evidence shown that this Turing Machine ("TM") is not universal. (This has been covered by other slashdotters).

Second, Wolfram & co's responses seem to have little to do with Dr. Pratt's criticism. But there is a connection, and what follows is my attempt to explain the situation. Wolfram & co. point out that essentially, "micro Turing Machines"

(my term)have a slightly different notion of "Universality" than "classic Turing Machines", the ones studied and understood by Chomsky in the 1950's, the kind studied by students in undergraduate theory of automata courses (such as the one I took in the 1990's at Georgia Tech). In the view of these "classic" TMs, its usually envisioned that a machine operates on an infinitely scratch pad, or "tape". In the case of a Universal TM, the beginning of this tape might be encoded with the specific algorithm to be computed. Otherwise, the tape isblank. This tape comprises the "initial condition".However, in relatively recent research (1960's being "recent") on Turing Machines, that tape does not necessarily start out as completely blank. However, it's also clear that in order for us to

knowthat the TM is Universal, the initial conditions may not be both infiniteandarbitrary. "Arbitrary" here means "anything anyone might possibly imagine given an infinite amount of time".BUT,theoreticians surmised that the initial conditions might be infinite and repetitive (like lots of 0's, or digitized porn videos). So what about initial conditions that are infinite, non-repetitive, but not arbitrary? There might be a class of initial conditions that can be classified and calculated in some way, such as the number PI. Perhaps a particular machine is universal given some non-arbitrary, "interesting", infinite, non-repetitive initial condition. Given such questions, which are highly relevant to understanding micro Turing Machines, the consensus among modern researchers was to "relax" the rules for classifying a machine as "universal".But if you relax the rules too much, you might end up a complete step down from a Universal TM, and in the land of "Linear-bound automata" (LBA). An LBA is like a TM, but the size of its scratch pad must be proportional (linearly) to the size of the initial condition. So what happens if the initial condition is infinitely long? Is it an LBA or a Turing Machine? Dr. Pratt seems to think Smith is reaching too far with his conclusion. If you have an initial condition and get results on par with a Universal TM, then the machine must be universal, right? Not so, says Dr. Pratt. If your initial condition is infinite, and you get results on par with a Universal TM, the machine need only be an LBA. Similarly, students of automata may recall that two "push down automata" (PDA) working in tandem may emulate a Universal TM, though neither one is. So just because you have behavior akin to a Universal TM and one of your components isn't a Universal TM does not therefore mean that the other component is.

Wolfram's team counters that Smith's proof shows that the initial condition, though infinite, is not computationally powerful enough to be utilized by an LBA. Further, the component that generates the initial condition has no further interaction with Wolfr