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.

Comments

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

[Anonymous Coward]

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.

Re:The Filter

[jnana]

Indeed. A prior email in that thread -- by the same author, Pratt -- makes it very clear by giving the example of 2 pushdown automata (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

[Anonymous Coward]

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.

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

[EveLibertine]

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

Re:The Filter

[Anonymous Coward]

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

Hey Michael, long time no post.

Re:The Filter

[HeadlessNotAHorseman]

Wolfram's 2,3 Turing Machine Not Universal
HOLLYWOOD - In a shock move, MGM has undercut Universal in its bid for the movie rights to Wolfram's 2,3 Turing Machine. Insiders had predicted that Universal would make the deal to build on the phenomenal success of Wolfram's 2,2 Turing Machine, but it has since become apparent that Universal failed to include an option for all sequels in the original contract. The exact figure offered by MGM is unknown, but is believed to be approximately x + y, and we can confirm that y is a finite number. More details will follow.

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

[ais523]

This argument and Pratt's argument that the universality proof are incorrect both share the same flaw; see the response linked in the update of the original story for more details. Yes, a system consisting of two push-down automata that can communicate back and forth is universal. However, the proof of the universality of the 2,3 Turing machine in question doesn't set up a system where two systems can communicate back and forth; instead, the output of one is used as the input of the other, and there is no communication in the other direction. If one PDA is used as an encoder for another, the resulting system is not universal. The definition of universality in the original prize that was agreed on by the judges basically said that in the case of obviously simple encoders, if an encoder+system together are universal than the system itself is. The encoder used in the proof is not obviously simple (as it takes up several pages in the proof) but is clearly not doing any sort of universal calculation itself or engaging in part of such a calculation.

The real problem here is that with other definitions of 'universal', the system might indeed not be universal; the definitions are important in such cases. (For instance, a definition that restricted the initial condition to be finite and surrounded by nothing but yellow on the tape would result in the system being non-universal, but this definition is too restrictive to be useful.) Changing the definition of 'universal' is likely to result in changes to what is universal and what isn't, although it seems likely that the 2,3 Turing machine in question is well on the universal side of that edge (although not as far as some other systems). Even systems such as rule 110 that are generally accepted to be universal would be non-universal if a non-repeating finite initial condition was mandated by a definition of universality.

So in short, nothing has been disproven, the machine is still universal, and the headline is wrong.

Re:The Filter

[jnana]

I didn't understand Pratt to be arguing that the 2-PDA system is directly analogous to the proof system in the way that you state. What I understood Pratt's point to be was that the proof does not prove that the 2,3 machine must be universal, since it is entirely possible that while the encoding mechanism itself is not universal, it nevertheless could be sufficiently complex that universality does not (and perhaps cannot) exist without it.

The author of the proof states on page 26 (counting the first PDF page as 0) the following:

Therefore, this algorithm for determining an initial condition, whilst somewhat complicated, is definitely not itself universal, and so the universality discovered above is a property of system 0, and not of the algorithm used to find its initial condition.

I took Pratt to be arguing that this is not a valid inference, that one can't just say that because the encoding and creation of initial condition mechanism is not universal, while the system as a whole is universal, that the 2,3 machine is therefore universal.

I'm looking forward to learning more over the next few days, but that is what I meant by earlier post. I may have completely misinterpreted Prof. Pratt's criticism, but that's my take on it.

P.s. Prof. Davis stated on the FOM list that the committee has not actually ruled that the paper is acceptable yet. Apparently, people within Wolfram's organization were the ones who made the determination. Given that, I'm not sure that it's correct for you to state that "the machine is still universal", since the paper hasn't been peer-reviewed by even the expert peers on the committee, let alone the wider community, and so its universality is still far from established.

Re:The Filter

[ais523]

Whether this is a valid inference depends on the definition of 'universal'; the problem here is that Pratt appears to be using a different definition from the one that the prize committee and the proof adopt. The inference may be incorrect with certain definitions of 'universal'; however, it is correct with other definitions. My point is that the counterexamples that Pratt gives to the inference are incorrect; that does not, of course, mean that the inference itself is correct, but it means that looking into where the problems with the counterexample came from is worth doing, and it appears to be a misconception between systems interacting backwards and forwards, and preprocessors. It seems to me that most general definitions of 'universal' will cause the inference in question to be correct (there is at least one definition which includes the inference as part of the definition itself, that is 'A system is universal if it can emulate any Turing machine if given an appropriate initial condition encoded using a non-universal system', although there is some circular reasoning involved in that definition).

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

[mightybaldking]

You are perfectly correct given the layman's imprecise use of mathematical language. That is, you understand the concept quite well, but are using the language imprecisely. x + y = infinity is not a valid statement. Nor is x = infinity. infinity is not a number. Infinite is an adjective that can be used to describe a number that you might think of a infinity. In other words, infinity has no value, and can't be "equaled" You would be more correct to say (X + Y) is infinite, or produces a non-finite result. Anybody doing number theory will use set theory and cardinality (look up a few posts) to be completely precise. Even in calculus, where infinity is used more frequently, we really mean "The value of X approaches the infinite"

Ouch

[JoeShmoe950]

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

Is not universal?

[MarsDefenseMinister]

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

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

Bad Headline

[EvanED]

Wolfram's 2,3 Turing Machine Not Universal

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.

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

[ZorbaTHut]

Yeah, speaking of that . . .

"Wolfram's 2,3 Turing Machine Not Universal". What? Where'd you get that? This issue doesn't prove anything of the sort - it merely shows that this proof is invalid. It may be universal, it may not, but we still don't know.

So, ironically - whoa, not so fast there big editor.

Bad romantic consequence

[Hao Wu]

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.

Peer Review Rules

[tjstork]

This sort of thing is science when it works at its best. Someone throws something out there, and another scientist checks it, and bam, we learn something.

Re:Peer Review Rules

[ispeters]

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

Well, to paraphrase someone famous (perhaps Edison?), we've learned another way that doesn't work. It sounds like the author of the proof has used a faulty syllogism. Perhaps the syllogism can be patched up such that the rest of the proof plus the patched syllogism equals a correct proof.

Ian

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

[rbarreira]

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.

Do you mean factor numbers? Even though it would be impressive to have an algorithm which factors numbers quickly, it wouldn't prove anything about the P=NP? problem. Factoring numbers is not known to be an NP-complete problem, so solving it in polynomial time doesn't automatically imply that P=NP.

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

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

Re:Peer Review Rules

[hansraj]

A problem L is NP-hard if any polynomial algorithm for L can be used to solve all problems in *NP* with only a polynomial slowdown. That is the definition of NP-hard. NP-complete problems are NP-hard and have extra property that they are in NP as well.

So, solving any NP-hard (and hence any NP-complete problem) in polynomial time is as good as solving *all* problems in NP in polynomial time. P is just the class of problems solvable in polynomial time.

Hence, polynomial algorithm for *any* NP-complete problem => (P=NP)

Where are my meds?

[synthespian]

Jesus Christ, is Wolfram out of Lithium again?

Re:duh

[schon]

the universality of Turing machines is... gosh, what the heck does this mean? It means you need to study more for your CS exams.

Re:Proven?

[Anonymous Coward]

Apparently some Slashdot editors have still to defeat the gargantuan misteries of propositional calculus...

Ah academics...

[SilverJets]

I love the arrogance.

Had I pushed my luck my second question would have been, who has verified this proof that has taught an automata theory course at a suitably accredited institution?

Re:Ah academics...

[mrpeebles]

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

Title Proven To Be Misleading

[yerdaddie]

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.

No, just not proven

[billstewart]

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

Can I get a refund

[stinkfish]

for the Wolfram's 2,3 Turing Machine I bought from amazon?

Re:Can I get a refund

[rubycodez]

only if the infinite tape is mostly unused

Re:Can I get a refund

[Anonymous Coward]

Just cut out the used part, and tape the two ends together. No one will ever know the difference.

Re:Proven?

[EvanED]

Apparently some Slashdot editors have still to defeat the gargantuan misteries of propositional calculus...

Or, you know, English.

Back to the drawing board

[tepples]

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

Re:duh

[ispeters]

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

Anyway, a regular Turing Machine only computes one function--it's a single-purpose machine. A Universal Turing Machine 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

Wolfram chimes in

[snark23]

Wolfram's lengthy response:

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

I rate this proof

[MillionthMonkey]

(Score: 2,3 Possibly Informative)

Re:I rate this proof

[Alsee]

(Score: 2,3 Possibly Universal)

-

Elmentary Mistake in Title

[Cyberllama]

This doesn't mean it's not universal, just that it's not PROVEN that it is. Not at all the same thing.

The prize stands -

[Anonymous Coward]

he was just using a new kind of proof.

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.

Re:Vaughn Pratt is confused

[Ed Pegg]

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

Re:Vaughn Pratt is confused

[Anonymous Coward]

Since you are posting from the heart of the Wolfram Hype Machine (TM), perhaps you could comment on why the prize was announced by Wolfram Himself as being successfully awarded, when Martin Davis on the FOM list states that the committee members were not polled.

This appears to be a flagrant violation of the rules for the prize, which state that "For the purposes of this prize, the treatment of universality in any particular submission must be considered acceptable by the Prize Committee."

To make my question crystal clear: how is it possible that the committee deemed the proof (or its treatment of universality) acceptable when at least some of them were not polled as to whether they thought the proof was acceptable?

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

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 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:Vaughn Pratt is confused

[evgalois]

Well, that's a good start: you accepting you are not an expert in the field but pretending to judge something that of course experts reviewed. It is nice that people like you think on this problem and possible flaws, though. Of course nobody is changing the well stablished definition of a Turing machine. But it is accepted even by the experts that there is no clear definition on universality. You should follow all the FOM posts and not only those that you think are better to critic others. The definition of universality has been modify several times, the first to make a generalization exactly as the used by Alex Smith was Watanabe as early as in the 60's. Alex Smith contribution is a generalization of the same sort. If you want some references feel free to check these and then reply again: [1] Manfred Kudlek. Small deterministic Turing machines. Theoretical Computer Science, 168(2):241-255, November 1996. [2] Manfred Kudlek and Yurii Rogozhin. A universal Turing machine with 3 states and 9 symbols. In Werner Kuich, Grzegorz Rozenberg, and Arto Salomaa, editors, Developments in Language Theory (DLT) 2001, vol. 2295 of LNCS, pp. 311-318, Vienna, May 2002. Springer. [3] Maurice Margenstern and Liudmila Pavlotskaya. On the optimal number of instructions for universality of Turing machines connected with a finite automaton. International Journal of Algebra and Computation, 13(2):133-202, April 2003. [4] Claudio Baiocchi. Three small universal Turing machines. In Maurice Margenstern and Yurii Rogozhin, editors, Machines, Computations, and Universality (MCU), volume 2055 of LNCS, pp. 1-10, Chisinau Moldavia, May 2001. Springer. [5] Turlough Neary and Damien Woods. Four small universal Turing machines. Machines, Computations, and Universality (MCU), volume 4664 of LNCS, pp. 242-254, Orleans, France, September 2007. Springer. [6] Yurii Rogozhin. Small universal Turing machines. Theoretical Computer Science, 168(2):215-240, November 1996. [7] Shigeru Watanabe. 5-symbol 8-state and 5-symbol 6-state universal Turing machines. Journal of the ACM, 8(4):476-483, October 1961. [8] Shigeru Watanabe. 4-symbol 5-state universal Turing machines. Journal of Information Processing Society of Japan, 13(9):588-592, 1972. That is why many serious authors as Vaughn Pratt can be confused. Because they are not updated on the subtles of the field. 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.

Re:Vaughn Pratt is confused

[evgalois]

From the FOM list where most of you jumped to conclusions without even waiting to an official answer from Wolfram Research: 1. Concerning the prize committee, we did not expect them to go through the details of the proof but to support the reviewers on technical issues related to their fields of expertise. We would have been delighted to have had them spend more time on the proof but that wasn't our expectation. We did talk to people about how to set the prize up. Basically we needed judgement about their areas and we were very careful to cover those that could come up in a universality proof. We are grateful to the committee for covering those areas and we are happy that they were more active than many such committees. In the review process, committee members agreed with the Wolfram Science internal reviewers, while others asked for additional clarifications (such as fulfilling universality basic requirements for non-halting machines). All committee members had Alex Smith's proof in hand for a couple of months. But it was Wolfram staff who did the hard work to achieve a satisfactory level of verification (between revisions and revision requests), and we thought that by waiting any longer we would not have learned more. It helped that a lot of the proof was submitted in the form of programs that could be run and analyzed in a systematic way. Smith's proof is available to everybody, anyone can point out anything, and it is nice to get the sense that there are people out there who would be interested in verifying proofs. This is great news, and if we do other prizes we would definitely like to take advantage of that. We would be also delighted to hear opinions on how to set up next prizes. 2. 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 (see detailed references below), 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. One could fairly argue that two non-universal coupled automata can reach universality, but it would require the couple to interact at every step, as in Margenstern's nice example [1], but that's very different from a non-universal second automaton intervening only once at the first step. 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. Accepting that you are not experts in the field but pretending to judge something that of course experts reviewed is a good start. It is nice that people like you think on this problem and possible flaws, though. Of course nobody is changing the well stablished definition of a Turing machine. But it is accepted even by the experts that there is no clear definition on universality. You should follow all the FOM posts and not only those that you think are better to criticise others. The definition of universality has been modify several times (if one can say so, since there is no original or first accepted definition), the first to make a generalization exactly as the used by Alex Smith was Watanabe as early as in the 60's. Alex Sm

Wrong, that is NOT Wolfram's response

[Weyoun]

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

Serious authority

[Emnar]

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

[Bob Hearn]

... is this:

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

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

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.

glass houses

[m2943]

Pratt asks: "How did an argument containing such an elementary fallacy get through
the filter?"

Proofs containing elementary errors are published all the time. Peer review is, and always has been, only a way of weeding out some percentage of bad submissions. Peer review that is strict enough to ensure that only correct papers get published would also result in the rejection of many good papers. In fact, some good papers that have advanced science have contained elementary errors.

And people who sit in glass houses shouldn't throw stones. Looking through Pratt's publication list, the first two papers I came across on a topic that I know a lot about should never have passed peer review.

Everybody who publishes makes elementary mistakes and makes a fool of himself sometimes; one should respond kindly and gracefully.

Comment removed

[account_deleted]

Comment removed based on user account deletion

Comment removed

[account_deleted]

Comment removed based on user account deletion

Re:wolfram inc. sinking deeper and deeper

[tlord]

Yes, exploited. It's a professional embarrasment at the start of his career. I'm not sure $25K is a fair price.

It's a basic logic problem. The original challenge problem could be restated: "Prove either that there exists a non-universal machine which emulates the 2-3 machine OR that the 2-3 machine can only be emulated by a universal machine." The proof does neither. Wolfram Inc. reps have come back with "Well, perhaps we should change the definition of universality!" Only, they aren't very concrete in offering an alternative with any rigor and the vague suggestions they are making don't add up (e.g., don't answer Vaughn Pratt's counter-example of paired push-down automata).

What the student proved here may turn out to be an interesting and useful result (not the universality of 2-3 but the universality of this interesting combination of machines). Students should be encouraged to work on such problems. Students should be encouraged to write as well as this student is learning to do -- it's a nicely presented paper (trivial formatting bugs aside). But students shouldn't be encouraged to go in those directions on false premises.

At least two interesting questions come from the students work. To Wolfram Inc.'s credit, they are pointing in the general direction of these new questions (even while not yet acknowledging their mistake). The new questions: Do there exist simple machines whose universality is undecidable (and might 2-3 be an example)? If 2-3's universality is either false or undecidable (and especially in the latter case) can we find any useful structure to what combinations of it with other machines clearly are universal?

I'll leave it as an exercise to figure out how raising those questions relate to the "Priciple of Computational Equivalence" in NKS but, meanwhile, leave the student out of it!

We'll see. With an additional step that "finitizes" the student's construction the proof is rescued and raised to the status of an important lemma -- but if that step isn't very quickly forthcoming, the prize -- in no small part an advertising vehicle -- was administered in a pedagogically misleading way.

-t

Re:Wow...

[jpop32]

Jeez, Can someone please give me the short version explanation about why everyone is bagging on Wolfram?

Well, the very short version is that he is not a very nice person. And, basically, he said 'fuck you' to the traditional scientific community and went his separate way, turning from a prodigy to an outlaw. Which the traditional scientific community didn't appreciate much. And now they are, more or less, openly out to get him.

Which is, IMHO, unfortunate, because his scientific ideas should be judged on their merits alone.