Forgot your password?
typodupeerror
Math Science

Wolfram's 2,3 Turing Machine Not Universal 284

Posted by kdawson
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.
This discussion has been archived. No new comments can be posted.

Wolfram's 2,3 Turing Machine Not Universal

Comments Filter:
  • The Filter (Score:5, Interesting)

    by eldavojohn (898314) * <eldavojohn.gmail@com> on Monday October 29, 2007 @09:30PM (#21165381) Journal
    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 (Score:5, Informative)

      by Anonymous Coward on Monday October 29, 2007 @09:41PM (#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.
      • Re:The Filter (Score:5, Informative)

        by jnana (519059) on Monday October 29, 2007 @10:11PM (#21165755) Journal

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

          by Anonymous Coward on Monday October 29, 2007 @10:23PM (#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.

          • by Anonymous Coward on Monday October 29, 2007 @10:48PM (#21166023)
            "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.
            • You jest, but it's a damn good book. I actively felt, as I was reading it for my Models of Computation class last semester, that it was the best textbook I've had up to that point. It's very precise.

              Note that I'm not anonymous.
        • I'm not conversant in the terms, but a simplification of this flawed logic seems to be this: this machine made of parts A and B exhibits a new behavior that is not exhibited by part A, therefore it must be something part B exhibits on its own as well. But when building machines, the sum can be more than the parts. After all, that's the whole point of this, to find the minimal parts that implement a universal Turing machine when put together. But as I said, this isn't my field so the error may not be this fu
        • Re: (Score:3, Interesting)

          by Workaphobia (931620)
          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: (Score:3, Informative)

          by ais523 (1172701)

          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

          • Re: (Score:2, Informative)

            by jnana (519059)

            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 p

            • Re: (Score:2, Informative)

              by ais523 (1172701)
              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 int
      • Re: (Score:3, Insightful)

        by EveLibertine (847955)
        Regardless, the guy that wrote that email is a prat.
      • His analogy is interesting but I'm not sure he is exactly right in describing the nature of the proof.

        My understanding is that the proof shows how to set up the machine so that it will execute any calculation - it will be "universal". However the question mark is that in order to do the set up, you have to prepare an infinite sequence in memory just a certain way. The question is whether that set up operation is universal itself, in which case the fact that the whole operation is universal wouldn't count -
      • > "This is TRUE for numbers."

        Eh, my instinct is to twitch when we're so callously applying the addition operator to objects that are not natural numbers (or reals, etc). Maybe there's some definition or convention I'm unaware of, but I'd restate that as:

        "If the set A union B contains an infinite number of elements, and B contains finitely many elements, then A's cardinality must be infinite."

        But even that I'm not too sure about, as I know there's a lot more than meets the eye when it comes to set theory.
    • by phiwum (319633)

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

      • by wasted (94866)

        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?

        • by djupedal (584558)
          "My understanding was that the purpose of publishing is peer review."

          And how many 20 year olds run out and buy the latest copy of 'Complex Systems'...?

          Not enough, apparently :)
        • by phiwum (319633)
          The purpose of publishing is to make the article available to peers, so you are right that there is the opportunity for review after publishing. But prior to publishing, the article will be reviewed by the editor and two or three anonymous reviewers and this process is commonly referred to as "peer review".

      • 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 m

    • by HeadlessNotAHorseman (823040) on Tuesday October 30, 2007 @01:12AM (#21167091) Homepage
      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.
    • by deepvoid (175028)
      By stating a Turing machine is universal, one is saying that the machine can handle the entire spectrum of possible inputs, something the Turing machine in the document clearly does not. By stipulating that the inputs are by some arbitrary rule finite (in the sense that the writer would want to restrict the initial conditions even a little), the universal nature of the test is eliminated and thus becomes yet another of the countless examples of failed attempts at Turing completeness.

      Sorry, good try, maybe n
    • by Starky (236203) on Tuesday October 30, 2007 @03:26AM (#21167655)

      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.

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

      Meaning it had not yet been peer reviewed.

      No, this means the opposite AFAIK. If it will be published in a peer-reviewed journal, then it has already been reviewed. Otherwise you would say it has been submitted to the journal, which would imply a review is pending.

      That is, you only say it will be published after acceptance by the journal, following peer review. It is then published some time later, depending on the queue for publication in that journal.

  • Ouch (Score:3, Informative)

    by JoeShmoe950 (605274) <CrazyNorman@gmail.com> on Monday October 29, 2007 @09:30PM (#21165391) Homepage
    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
    • by STrinity (723872)
      Wasn't Wolfram's New Kind of Science based on the idea that we don't need no steenkin' peer review?

  • Is not universal? (Score:4, Insightful)

    by MarsDefenseMinister (738128) <dallapieta80@gmail.com> on Monday October 29, 2007 @09:31PM (#21165401) Homepage Journal
    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 (Score:5, Informative)

    by EvanED (569694) <evaned&gmail,com> on Monday October 29, 2007 @09:32PM (#21165411)
    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.
  • by ZorbaTHut (126196) on Monday October 29, 2007 @09:33PM (#21165417) Homepage
    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.
  • by Hao Wu (652581) on Monday October 29, 2007 @09:35PM (#21165431) Homepage
    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 (Score:5, Insightful)

    by tjstork (137384) <todd.bandrowsky@NOSpAM.gmail.com> on Monday October 29, 2007 @09:36PM (#21165437) Homepage Journal
    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.
      • We learned one way that doesn't work to prove the hypothesis. Sometimes you have to take what you can get with science.
      • by ispeters (621097) <[ac.oolretawu.inmula] [ta] [sretepsi]> on Monday October 29, 2007 @09:50PM (#21165555)

        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

        • by phiwum (319633)

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

            • You could argue that scientist reading each others articles and commenting on (and finding fault in) them is also a peer review. Public this time.
              • True, but don't forget that this "public peer review" occurs conditionally upon the journal's peer review being successful. So the input to the "public peer review" is statistically biased in favour of papers with less trivial faults.
    • by JanneM (7445)

      Someone throws something out there, and another scientist checks it, and bam, we learn something.
      Yep. We learn that "never hold the press conference until after peer review and acceptance of publication".

      • Re: (Score:3, Interesting)

        by tjstork (137384)
        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 th
        • Re: (Score:3, Informative)

          by rbarreira (836272)

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

            by tjstork (137384)
            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
    • If it aint universal it aint a Turing machine
      • Sorry, but that is just flat wrong.

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

      I can't help thinking that we should wait for the authors response to the reviewer before we start judging the original work. Maybe the reviewer has a point, but maybe he doesn't.

  • by synthespian (563437) on Monday October 29, 2007 @09:40PM (#21165465)
    Jesus Christ, is Wolfram out of Lithium again?

  • I don't think that the details of which particular Turing machine is or is not universal are all that significant.
    http://cs.nyu.edu/pipermail/fom/2007-October/012149.html [nyu.edu]

    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. ;)
  • Shouldn't the headline be "Wolfram's 2,3 Turing Machine Not Proven Universal"?

    Was this proof the last chance to prove . . . whatever this thing is? Or has a specific attempt merely failed? (According to some email.)

    -Peter
  • Don't tell me they fell for the old 2=1 trick!
    http://www.youtube.com/watch?v=RkSow7FtWmA/ [youtube.com]
  • Ah academics... (Score:2, Insightful)

    by SilverJets (131916)
    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: (Score:3, Insightful)

      by mrpeebles (853978)
      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.
  • by yerdaddie (313155) on Monday October 29, 2007 @09:59PM (#21165639) Homepage
    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 rese
    • Re: (Score:2, Interesting)

      by samweber (71605)
      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
    • by alienw (585907)
      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 tha
    • There's been a lot of comments on whether it is a proof or not and how research works and so forth, but I'd like to make one point: If I have a "proof" that later proves to be false, but with this "proof" I develop the cure to cancer, does it really matter? Some of the greatest "features" I have seen in programs are items that the programmer thinks is a bug in the code, written by some of the best programmers I know. So what if the foundations were shaky? Nitro-glycerine was discovered by accident...
    • math the religion (Score:3, Interesting)

      by slew (2918)
      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
  • by stinkfish (675397) on Monday October 29, 2007 @10:07PM (#21165717)
    for the Wolfram's 2,3 Turing Machine I bought from amazon?
  • Will Smith have to return the $25k?
  • Wolfram chimes in (Score:2, Informative)

    by snark23 (122331)
    • by Plutonite (999141)
      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.
    • Incorrect - that is not Wolfram's response to Pratt's message, it is a response to an earlier message. Compare the dates.
  • by Urusai (865560)
    ...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.
  • by Cyberllama (113628) on Monday October 29, 2007 @10:27PM (#21165909)
    This doesn't mean it's not universal, just that it's not PROVEN that it is. Not at all the same thing.
  • by Anonymous Coward
    he was just using a new kind of proof.
  • I hope he's already cashed the check.

  • by evgalois (1181567) on Monday October 29, 2007 @11:31PM (#21166345)
    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.
    • by Ed Pegg (613755) * <ed@mathpuzzle.com> on Tuesday October 30, 2007 @12:03AM (#21166611) Homepage
      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.
      • Re: (Score:3, Insightful)

        by Anonymous Coward

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

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

        To make my ques

      • Re: (Score:2, Interesting)

        by ortholattice (175065)
        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' t

        • by evgalois (1181567) on Tuesday October 30, 2007 @07:00AM (#21168481)
          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.
  • Serious authority (Score:4, Informative)

    by Emnar (116467) on Monday October 29, 2007 @11:51PM (#21166525)
    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
  • by Bob Hearn (61879) on Tuesday October 30, 2007 @12:12AM (#21166677) Homepage
    ... 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.
  • glass houses (Score:4, Insightful)

    by m2943 (1140797) on Tuesday October 30, 2007 @04:50AM (#21167969)
    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.

Scientists will study your brain to learn more about your distant cousin, Man.

Working...