Follow Slashdot blog updates by subscribing to our blog RSS feed

 



Forgot your password?
typodupeerror
Math Science

Wolfram Offers Prize For (2,3) Turing Machine 164

An anonymous reader writes "Stephen Wolfram, creator of Mathematica and author of A New Kind of Science, is offering a prize of $25K to anyone who can prove or disprove his conjecture that a particular 2-state, 3-color Turing machine is universal. If true, it would be the simplest universal TM, and possibly the simplest universal computational system. The announcement comes on the 5-year anniversary of the publication of NKS, where among other things Wolfram introduced the current reigning TM champion — 'rule 110,' with 2 states and 5 colors."
This discussion has been archived. No new comments can be posted.

Wolfram Offers Prize For (2,3) Turing Machine

Comments Filter:
  • 33% solved. (Score:5, Funny)

    by Harmonious Botch ( 921977 ) on Wednesday May 16, 2007 @02:59AM (#19142083) Homepage Journal
    One of the colors must be blue so it can emulate Windows.
    • Microsoft Research Labs has 221 proofs to choose from. 85 proofs are related to Mathematics, 115 proofs are related to Alan Turing himself and 21 are mostly general proofs on anything. Also, thay have 43 proofs on those little cells that combine togather into tapestry patterns.
  • by Black Parrot ( 19622 ) on Wednesday May 16, 2007 @03:00AM (#19142087)
    ...he's given up on proving it himself.
    • Re:Sounds like... (Score:5, Interesting)

      by Anonymous Coward on Wednesday May 16, 2007 @03:08AM (#19142135)
      Wolfram has previously sued his own employees to keep them from publishing results, and there are many stories about him removing peoples' names from credits.

      Perhaps this is the only way he can now get creative people to work on problems like this.
      • by xtracto ( 837672 ) on Wednesday May 16, 2007 @05:38AM (#19142687) Journal
        And the person that made the proof of what is claimed in the summary was Matthew Cook [wikipedia.org], not Wolfram himself, Wolfram sued him because he presented his proof in another conference (can you believe what a jerk?).

        Of course the person that makes this proof will have to concede every right to Wolfram and therefore in some way the 25K are just a payment for such intellectual property.

        And the name removing has been mostly due to his book A new kind of science, where he "comes up" with several ideas that have been created by other authors. I would like to *believe* he makes the typical Master or junior PhD error of not looking hard for the current work but other people believe he just wanted to plagiarize other's people ideas.

         
        • If you buy the work, its not really plagiarizing. Its called business.
        • by john82 ( 68332 ) on Wednesday May 16, 2007 @07:15AM (#19143115)

          Of course the person that makes this proof will have to concede every right to Wolfram and therefore in some way the 25K are just a payment for such intellectual property.
          I can't speak to your characterization of the relationship between Cook and Wolfram, however your assertion regarding the disposition of any provided proof is at best uninformed if not outright FUD. From the rules [wolframscience.com]:

          Submissions remain the sole property of submitter(s), but we reserve the right to publish summaries of any winning submission and the name of the submitter(s) on our website. It is also anticipated that any winning submission will be expanded into a scholarly paper that could be published in the Complex Systems journal.

          It was far too easy to follow the link in the original post and investigate.
          • It was far too easy to follow the link in the original post and investigate.
            The use the GP's own words, he probably made "the typical Master or junior PhD error of not looking hard."
    • Sounds like... ...he's given up on proving it himself.


      Dear Slashdot, please do my homework for me.
  • by Anonymous Coward

    It'll take me some time.

    I can disprove it. It will take me some time.

    I can disprove it. It'll take me some time.

    I can disprove it. It will take me some time.

  • by Anonymous Coward on Wednesday May 16, 2007 @03:04AM (#19142117)
    Is it just me... or is this graph [wolframscience.com] not family-appropriate?
    • Funny AC's are the best kind.

      You've won this angry face as a reward! >:[
      • by Anonymous Coward on Wednesday May 16, 2007 @04:18AM (#19142393)
        Sad thing is, I posted anonymously 'cause I figured the mods would think that was a troll. And now, I'm posting anonymously because this is off topic. Just my luck, this will get modded up as "funny" again, just for the irony.
        • Re: (Score:1, Informative)

          by Anonymous Coward
          What do you care, you don't get <salivate>Karma</salivate> for Funny mods.

              - Anonymous Karma Whore
    • Re: (Score:1, Informative)

      by Anonymous Coward
      You think that's bad? Imagine this [med.mun.ca] without the labels or blood vessels. Then imagine drawing it on the chalkboard and only realizing what you'd drawn after giving a 10-minute lecture on the endocrine system with it behind you the whole time.
    • by ettlz ( 639203 )
      "Sir! There's something on the radar screen. It looks like a giant..." (OK, over to you.)
  • Cult (Score:3, Funny)

    by Anonymous Coward on Wednesday May 16, 2007 @03:04AM (#19142121)
    I was disappointed that Wolfram's book A New Kind of Science wasn't something like a Scientology cult. He would have been the awesomest cult leader!
    • Cult of NKS (Score:5, Interesting)

      by drgonzo59 ( 747139 ) on Wednesday May 16, 2007 @04:23AM (#19142419)
      Let's see what Wolfram's NKS and Scientology have in common.

      1. Both closed self-contained, self-referencial systems. ... "This is the new kind of science, old science is obsolete"

      2. Both venerate a person: Wolfram and L. Ron Hubbard.

      3. Both have this "us" versus "them" mentality.

      4. Both have their beliefs and ideas disregarded and ridiculed by the most sane individuals (this just reinforces the cult group cohesion).

      5. Both have exclusive facilities & training (NKS Summer School), special meetings and conferences for the members. I don't know...looks like a cult to me... ;-)

    • by SamSim ( 630795 )

      I was disappointed that Wolfram's book A New Kind of Science wasn't something like a Scientology cult

      You may thinking of L. Ron's 1978 book A New Kind of Scients

  • No Halting State (Score:5, Interesting)

    by sugarmotor ( 621907 ) on Wednesday May 16, 2007 @03:18AM (#19142177) Homepage
    The description states that the machine has no halting-state.

    I couldn't make out what is to be interpreted as the result of a particular computation of this machine.

    Seems like a pretty important detail.

    Anyone know?

    Stephan
    • Re: (Score:2, Funny)

      by poopdeville ( 841677 )
      Yeah, and wtf kind of notation is that? I suppose I could go to the library and dig up a copy of NKS, but $25,000 isn't worth the trouble.
      • by drgonzo59 ( 747139 ) on Wednesday May 16, 2007 @04:42AM (#19142485)
        The nonsense is free online. Wow, now millions of people can read it, waste time ...and make fun it.. hopefully.

        Crazy NKS "goodness" for your reading "pleasure": here [wolframscience.com].

        Trust me, even if it is free, after reading it, you'll want your "free" back.

        • by Anonymous Coward on Wednesday May 16, 2007 @05:17AM (#19142619)
          The nonsense is free online. Wow, now millions of people can read it, waste time ...and make fun it.. hopefully. Crazy NKS "goodness" for your reading "pleasure": here .

          Trust me, even if it is free, after reading it, you'll want your "free" back.


          You didn't actually read the damn thing, did you? I'm getting really tired of this mindless NKS bashing, no matter how fashionable it is. A book that was largely favorably reviewed in Notices of the American Mathematical Society [ams.org] cannot be 100% nonsense, can it really? I find it amusing that those who are most critical of NKS are almost never real scientists.

          There are some severe flaws with NKS. The fundamental philosophical claims are highly doubtful, the "new science" mentioned in its title does not live to its name, the egomaniacal tone, the passing off of other people's hard work as Wolfram's own, the revisionist history, etc. But that said, there is a lot to enjoy in the book. The footnotes are worth the price of a copy on their own, as they are in many ways one of the best exposés of the history of the 20th century focusing on computer science, mathematics and physics I have ever read.

          I knew a lot about CAs and discrete models before reading the book, most likely more than you know, or will ever know, and yet I really did learn a lot from it. You just have to be intelligent and well-versed enough to be able to separate the wheat from the chaff. Maybe that's your real problem with the book?
          • by drgonzo59 ( 747139 ) on Wednesday May 16, 2007 @06:01AM (#19142783)
            Yes I read it. I was one of the suckers who paid money for it before it was available online.

            There are some severe flaws with NKS.

            You bet!

            The fundamental philosophical claims are highly doubtful

            Check.

            ...the "new science" mentioned in its title does not live to its name

            Check

            the egomaniacal tone

            Also "Check"

            the passing off of other people's hard work as Wolfram's own, the revisionist history

            One more big "Check". -- This is what did it for me. I wish he made the appendix section the main part of the book. That's where he actually mentioned who did what before him and I found the examples there more interesting than Wolfram's prose + pictures. Yes, as scientist I am very sensitive and biased when it comes to passing someone's work as your own, that is very much a "no-no" in the scientific community. The only time the rest of the world hears about the scientists is when they discover something really amazing or plagiarize.

            Overall, was the reading insteresting?, -- it was alright for me. I learned some new things as well (but mostly things others did that W. re-did in Mathematica) about CA, tag systems, fractals and such. But it was anything but a "New Kind Of Science". It wasn't "New" (just re-packaged) and it wasn't a "Science" it was just prose. Apart from few examples, W.'s "proofs" consist of phrases like "I strongly believe X", "I am quite confident that Y" and "Look at the pretty picture I generated!".

            Trust me I tried to like it: I paid money for the book and spent time reading it, I didn't want o believe that I somehow 'wasted' it, but in the end I have to be honest to myself and say 'no' it isn't what it claims to be and 'yes' I wish I hadn't spent the time and money buying it.

          • by eh2o ( 471262 )
            From the article:

            "...there are at least two ways in which
            he has benefited mathematics: he has helped to
            popularize a relatively little-known mathematical
            area (CA theory), and he has unwittingly provided
            several highly instructive examples of the pitfalls
            of trying to dispense with mathematical rigor."
            (Lawrence Gray, "A Mathematician Looks at Wolfram's New Kind Of Science).

            I give credit to the author for a fair evaluation, but I wouldn't exactly call it a favorable review.

            If Wolfram wrote "A Pictoral Introducti
        • by Threni ( 635302 )
          > The nonsense is free online.

          From the FAQ:

          "We are considering a future e-book version of NKS, but it is difficult to achieve adequate quality level"

          Well, assuming you don't use PDF. I've seen books/papers etc in PDF format and they look fine to me. Whatever can he mean?

    • Re:No Halting State (Score:5, Interesting)

      by drgonzo59 ( 747139 ) on Wednesday May 16, 2007 @03:50AM (#19142271)
      If it can emulate a known tag system proven to be a UTM then it is also a UTM. But of course, if you show that it can emulate your typical basic CPU you can also claim it's a UTM. The tag system is easier... I think.



      But the larger question is "so what?". So what if it is? When he found the (2,5) system to be, I don't recall the scientific comunity awarding him a Nobel Prize. No matter how much he can run his rule 110 he will not come up with animals, humans or planets. But the whole implication is that that's how "it" happened.



      I'll admit, I was one of the suckers who bought NKS before it was put online for free. I read it all -- it reads like bedtime story book. Wolframs "proofs" are mostly just statements like I strongly believe..., I am quite convinced... and look at the pretty pattern I just made! and so on. The most interesting thing was the appendix where he lists some the results and publications of actual scientists (you know the ones that don't define their own "new science" and then by definition become "scientists"...). I whish he would have made the appendix the main part of his book and added his "beliefs" as an appendix.



      Of course, he has loads of cash to just sit around and create "cool" patterns and then have a bunch of followers cheering each other on as they play with CA -- it's like they have their own little world, their contests, conferences, classes and so on. Can you say the word "cult" ?

    • by Zukix ( 641813 )
      I expect you would be free to choose your own interpretation of the CA for your proof. The obvious example is a repeating pattern but I would be interested if some interpretations could be considered as adding a rule to system.
    • Re: (Score:3, Informative)

      The description states that the machine has no halting-state.

      I couldn't make out what is to be interpreted as the result of a particular computation of this machine.

      Seems like a pretty important detail.

      I guess it's up to you to define the result interpretation in your proof. If you can make the machine encode "Finished emulating, and the result is: TRUE" on the tape (in whatever encoding of ascii into colors), then go into an idle loop over some other part of the tape, then it's probably OK with Wolfr

    • The description states that the machine has no halting-state.

      Halting state? How about the heat death of the universe?
  • by vivaoporto ( 1064484 ) on Wednesday May 16, 2007 @03:29AM (#19142211)
    I have a truly marvellous proof of this proposition which this comment is too narrow to contain.
  • by sifi ( 170630 ) on Wednesday May 16, 2007 @03:45AM (#19142255)
    Hmmm, I wonder whether he'll sell any more books as a result of this: From the website: There is a large amount of relevant material in A New Kind of Science.
    • Not to mention software sales:

      Any tips on how to win the prize? Do experiments! Use Mathematica to do computer experiments

      I'm not too much into theoretical computing but are there any practical reasons that such a small Turing machine would be of any practical purpose? Surely when such a simple machine is fabricated in hardware the transistor count of giving it any reasoable I/O and storage would outweight by far the benefits even in small embedded systems.
    • by radtea ( 464814 )
      From the website: There is a large amount of relevant material in A New Kind of Science.

      Does it have an explanation of the colour/state pictures he's so fond of showing?

      The {state, colour} -> {state, colour, offset} description that makes sense relative to the image below it shown here http://www.wolframscience.com/prizes/tm23/technica ldetails.html [wolframscience.com] is counter-intuitive: W->0, Y->1, R->2. This means the rules shown in the image are the same, but in a totally different order than the rules as de
  • Hmm (Score:4, Funny)

    by Frogbert ( 589961 ) <frogbertNO@SPAMgmail.com> on Wednesday May 16, 2007 @03:51AM (#19142275)
    I don't understand a word of the summary.. or the article.. But I'm going away to research the topic extensively, and when I get back you can all be assured I'll have opinions on it... Loud opinions!
  • Wolfram and Hart? (Score:1, Interesting)

    by stonedcat ( 80201 )
    Upun seeing the title did anyone else think great evil? http://en.wikipedia.org/wiki/Wolfram_%26_Hart [wikipedia.org]
  • by hajus ( 990255 ) on Wednesday May 16, 2007 @04:31AM (#19142447)
    The problem I have with CA being proposed as a model of a reality is that the arrow of time in CA seems to be backwards. In our reality, we know the past, but the future is uncertain. In cellular automata, the future can be predicted perfectly, but the states which were used to get to the current state are ambiguous. Large grids of such give the illusion of life (such as behaviour of predator/prey) but only a macroscopic scale even though time goes backward. But the arrow of time becomes very visible when the cells are focussed in on. If you decide to look at it in reverse time to satisfy the microscopic view, you don't get that feeling of life at the macroscopic scale.
    • Re: (Score:2, Interesting)

      Interesting thought.

      But since CA represent perfect causal determinism, doesn't that mean we people have the time of arrow backwards ourselves when applying it to our own universe? Instead of the past causing the future, the future causes the past.

      The reason we don't know the future for sure, is for the same way that we can't tell for certain which of a number of potential preceding causal states created the "current" state in a CA.
    • by julesh ( 229690 ) on Wednesday May 16, 2007 @06:43AM (#19142993)
      Yep. California is one fucked-up place.
    • Re: (Score:2, Insightful)

      by ssorc ( 48632 )
      I don't think you understand reality (or at least the current scientific models of it) very well. In reality the future is completely fixed and the past is uncertain (just like in CAs).

      Given a complete description of a scientific system, scientific models allow us to predict what the future state of the system will be. However, there is no guarantee that each starting state will reach a unique final one. So by observing the final state we cannot always uniquely determine the starting state.

      A good example of
      • by egomaniac ( 105476 ) on Wednesday May 16, 2007 @10:32AM (#19145085) Homepage
        In reality the future is completely fixed? I'm guessing you're not a physicist. Quantum mechanics is an inherently probabilistic theory -- you can calculate the probability of given events happening, but that's it. You can smash the same two particles together five times in a row and get five different results.

        The future is absolutely not fixed, because randomness is deeply engrained into our universe.
        • by mstahl ( 701501 )

          I love the idea that the Universe is random, because I love the idea that God may, in fact, play at dice. You have to be aware of the possibility that what we're perceiving as "randomness" is really just the incompleteness of our models of the Universe. The Universe itself isn't infinite, why should its complexity be?

        • by jd ( 1658 )
          I'm not convinced that that is a valid conclusion. There are many systems (such as chaotic systems) that are entirely deterministic but also entirely non-predictable. The two states are not mutually exclusive. It is entirely possible that the result of any given collision of particles is 100% deterministic, but that because we cannot measure the initial conditions, we cannot predict what the result would be.

          An alternative view is that when you talk about a "probability" in quantum mechanics, you are reall

          • by zobier ( 585066 )
            entirely
          • by hawkfish ( 8978 )

            A third view is the "many worlds" theory.

            For a really nice overview of the views (more than 3!) have a look at this [washington.edu].

            Personally, I suspect that the future is indeterminate because it is the simplest explanation I have for the existence of the present moment. Note that this is NOT the same as saying that time has a direction or even a flow, but more that there is a point that moves along the gradient. Put another way, if I am just a set of points in 4 space, why should one point be favoured over any other?

  • by Anonymous Coward on Wednesday May 16, 2007 @04:54AM (#19142531)
    ".. a rare blend of monster raving egomania and utter
    batshit insanity"

    Cosma Rohilla Shalizi on S.Wolfram, A new kind of science

    http://cscs.umich.edu/~crshalizi/notebooks/cellula r-automata.html [umich.edu]
  • Does anyone, after reading TFA (I know, not that common on slashdot) that we NEED governmental subsidized research? I mean, I know there are those who think the private sector and the free market is the solution to everything (like a financial turingmachine that is universal), but NO private industry wanting to make a profit out of it would ever finance such academic research and work.

    This is mainly knowdledge for the sake of knowledge, and companies aren't really interested in that. They would even only *c
    • For the benefit of society we should be funding research that can best serve society. And not in the idiocracy style of penis pills and hair growth treatments [hehehehehehe].

      Point is, as nice as it's to know about the TM thingy [whatever this is], it's very far removed from anything that can help people.

      Put it this way, you can either fund a local school, health care, research into cancer treatment [or whatever], ..., or you can pay someone to solve a math puzzle that will please 0.01% of the population at
      • "For the benefit of society we should be funding research that can best serve society."

        That would imply that one would know in front what research can best serve society.

        This is rather contentious and doubtful; first of all, it is rather arbitrary as to define what is 'best' for society, and furthermore, it's impossible to know what may come from that research in terms of future possibilities - or while not useful themselves, may lead to advances (or in combination with other research) that would otherwise
        • Schools [as in for kids], uni, hospitals, and the like are ALREADY underfunded TODAY.

          Dropping money on highly esoteric reading problems like turing machines is just as bad as funneling it to Haliburton. It's inappropriate and not in the best interests of society. You're right, who knows where 3 colour TM theory may take us. However, it's more likely that funding medical research, or other applied sciences will result in benefits.

          In this case I have to agree with the others. This is just an excuse to get
          • Re: (Score:3, Insightful)

            by N3wsByt3 ( 758224 )
            The problem I have with this kind of reasoning is, that it's applicable to almost everything, and yet it denies the fact that there is no society on the planetthat does not diversify its funding.

            For instance, with the same token one can say:

            "Schools [as in for kids], uni, hospitals, and the like are ALREADY underfunded TODAY. Why waste money on space-exploration when the billions spend up there could be used to help people down here?"

            "Schools [as in for kids], uni, hospitals, and the like are ALREADY underf
            • Um, I actually agree with your comment about why fund wars. As for art, that's culture and for the most part society does benefit from it (why learn to read, when there is nothing to read about?). I know where you're going. And as I said yesterday (OMG I love repeating myself...) NOT EVERYTHING IS BLACK AND WHITE.

              I agree that some long term funding and risks are a good idea. However, many of these problems do not really come up in "the real world." So you have to balance what a few want with what many
              • "Um, I actually agree with your comment about why fund wars."

                I actually do too. But that was just to show how some things may be more 'obvious to agree on' than others. The principle remains the same though; one could argument that military strength is necessary to safekeep the country. And wars...well, *nobody* will say they are a proponent of war - but yet, people accept the state spending billions and billions on the Iraqi war. And one can't really say it's a fluke, or people are all that oposed to it, b
    • That story is the _best_ argument FOR public funding.
      Wolfram only announces this (rather small) price to get publicity for his NKS bullshit, and sell more books.
      So in fact, the whole procedure will actually create a net loss in knowledge and intelligence (people that will work on it get dumber, and dont create useful knowledge in the meantime).
      • "That story is the _best_ argument FOR public funding."

        That's what I said.

        "Wolfram only announces this (rather small) price to get publicity for his NKS bullshit, and sell more books.
        So in fact, the whole procedure will actually create a net loss in knowledge and intelligence (people that will work on it get dumber, and dont create useful knowledge in the meantime)."

        Seen the quality of your counter-arguments, you'd better hope everyone reading your post is retarded.

  • by martin-boundary ( 547041 ) on Wednesday May 16, 2007 @05:08AM (#19142595)
    Ok, my proof is by contradiction: First, I take a sheet of graph paper and put a mark on it. Here's a transcript of the experiment.

    Me: Hello Mr (2,3), how are you?

    Graph paper: no response.

    Me: Hello. Mr (2,3)? Are you there?

    Graph paper: no response.

    Me: Mr (2,3), can you hear me?

    Graph paper: no response.

    Me: HELLO! CAN-YOU-HEAR-ME? MIS-TER (2,3)? CAN-YOU-HEAR-ME?

    Graph paper: no response.

    Me: ARE-YOU-THERE? MIS-TER (2,3)? PLEASE RESPOND?

    Graph paper: no response.

    Me: MIS-TER (2,3), PLEASE RESPOND NOW! IF-YOU-DO-NOT, I-SHALL-BE-FORCED-TO-CONCLUDE-THAT-YOU-ARE-NOT-HUM AN! N-O-T H-U-M-A-N!

    Graph paper: no response.

    Obviously, based on this Turing test, the (2,3) machine is not intelligent, but all intelligent creatures can simulate universal Turing machines. Contradiction! Q.E.D.

  • If you are not a professional mathematician, I doubt they will even read your proof. For the milennium problems this is even a policy, it is a way to filter out most of the garbage.
    • Re: (Score:2, Interesting)

      by muuh-gnu ( 894733 )
      Knowing how self-congratulatory and megalomaniac Wolfram is, he will also throw out any proofs which:

      1. Arent done or simulated using Mathematica, so he cant use them to further advertise Mathematica.
      2. Don't cite his book "A New Kind Of Science" as primary and most important reference, which is itself more of an Mathematica scam, then "A Kind of Science" at all.

  • by ynotds ( 318243 ) on Wednesday May 16, 2007 @08:36AM (#19143635) Homepage Journal
    It may be interesting to those who aren't just here to bash Wolfram that this offer to provide a prize for a proof of one of his key conjectures in A New Kind of Science (NKS) comes only seven weeks after another key conjecture was disproved. [wolframscience.com] (The fact that that disproof was brought to public notice by the NKS Forum moderator might suggest that the ongoing NKS project is happy enough for results to fall whichever way they will.)

    On a visit to Champaign-Urbana in the late 1980s, still before he officially started on NKS, Wolfram took me through where he felt his cellular automata research was headed which hinted at some of the inferences he would eventually draw from his mountains of research data. That was even before the Santa Fe Institute paper which was foolishly read as retreating [meme.com.au] from the edge of chaos-border of order which had briefly been the focus of the quest for the source of emergent complexity during the 1980s.

    The resources Wolfram is bringing to the table are significant and have certainly helped put complex systems back in the spotlight after far too many of the first generation of researchers were seduced by the marginal returns they could get by applying their methods to the derivatives market, no matter whether their methods made a significant difference or not.

    The downside of continuing to focus on the simplest possible mechanisms (Wolfram calls them 'programs') as the source of a critical threshold is that all those much sought after proofs of universality, from the early one for Conway's Life on, are vast feats of engineering and thus make no useful progress towards the implicit goal of helping to explain how we/anything got here in the first place.

    So I'll keep playing with my own idiosyncratic program to explore a bit deeper in that narrow and difficult transition region between order and chaos, but might be tempted to have another look at Mathematica's increasing support for such research once it is available via CP6AN.
  • Hmmm - $25k just about pays for one license for Mathematica. Perhaps he could offer that as an option.

    sPh
  • ... if it were well defined. Instead Wolfram seems to be using a nonstandard, unclear notion of "universality". By any standard definition, no Turing machine without a halting state can be universal. Thus, coming up with a satisfactory proof of "universality" or "non-universality" would seem to serve no purpose besides promoting Wolfram's nonstandard definitions. At the least, he should not describe this gadget as a Turing machine, which definitely implies a particular notion of universality.
    • by Dster76 ( 877693 )

      ... if it were well defined. Instead Wolfram seems to be using a nonstandard, unclear notion of "universality". By any standard definition, no Turing machine without a halting state can be universal. Thus, coming up with a satisfactory proof of "universality" or "non-universality" would seem to serve no purpose besides promoting Wolfram's nonstandard definitions. At the least, he should not describe this gadget as a Turing machine, which definitely implies a particular notion of universality.

      This is a minor issue. It can be solved by showing that for halting states of the simulated machine, the correct output is on the tape, and the emulating machine is in a verifiable loop that does not alter the content of the tape.

      Again, Wolfram may be a lot of things, but he knows his computability theory.

      • Yes, that would be one approach. But my point is that this is not the normal definition of a universal Turing machine. It's misleading to use that terminology; also, the real problem he is asking for a solution for seems to be somewhat less well defined than the appropriate, corresponding question would be for an ordinary Turing machine. The decision question should be simply and formally specified. You came up with one that would seem plausible. But who decides what's plausible?

        As a result, the result, pos
        • Yes, that would be one approach. But my point is that this is not the normal definition of a universal Turing machine. It's misleading to use that terminology; also, the real problem he is asking for a solution for seems to be somewhat less well defined than the appropriate, corresponding question would be for an ordinary Turing machine. The decision question should be simply and formally specified. You came up with one that would seem plausible. But who decides what's plausible?

          Nobody decides 'plausibility' (at least not recursion theorists or researchers in computability). They investigate relative computability.

          You see, the functions computable by Turing machines whose "halting" is defined as some pre-specified infinite loop, identical for all outputs, are the same as the functions computable by regular Turing machines with a privileged halting state. That is why, from the point of computability theory, it doesn't matter that Wolfram's possible universal machine doesn't hav

          • Nobody decides 'plausibility' (at least not recursion theorists or researchers in computability). They investigate relative computability.

            It seems to me that where matters of choice of definition are concerned, questions of appropriateness (perhaps a better word than plausibility) apply.

            You see, the functions computable by Turing machines whose "halting" is defined as some pre-specified infinite loop, identical for all outputs, are the same as the functions computable by regular Turing machines with a privileged halting state. That is why, from the point of computability theory, it doesn't matter that Wolfram's possible universal machine doesn't have a privileged halting state.

            Yes, of course. In other words, what you have done, informally, is specify a Turing machine W', which, when given an arbitrary Turing machine M and input w, will simulate Wolfram's machine on an encoding of M and w, and halt if Wolfram's machine trivially loops. Presumably you would also need to specify different kinds of such loops that should represent acc

            • Then, you complain that his use of the term "smallest" is unfair.

              Which is it?

              Again -- "this would be a fun problem to tackle if it were well defined".

              It is well defined. And, it concerns whether a machine, which he has introduced, is universal, in a clear, meaningful sense.

              Your new complaint, that Wolfram's use of the term "smallest Turing machine" is self-aggrandizing, unfair, and ignores the history of computability is correct, but is nothing new, as far as criticisms of Wolfram go. I saw
              • Then, you complain that his use of the term "smallest" is unfair.

                Which is it?

                Both. His use of the term "smallest" seems unfair because it is in relation to what seems to me to a definition of universality which is at best nonstandard and at worst ill-defined.

                Again -- "this would be a fun problem to tackle if it were well defined".

                It is well defined. And, it concerns whether a machine, which he has introduced, is universal, in a clear, meaningful sense.

                Well, I must admit that the precise sense escapes me, as it seems to escape Wolfram, from my quote above. I think Wolfram would probably be satisfied with a solution along the lines you propose. But why waste my time working on that, when it is all only for the greater glory of Wolfram's world view?

                By the way, when you start to defend yourself by reminding people that you went to MIT, and had a famous advisor, you start to sound a bit like Wol.. oh, now I'm just being cruel.

                Yeah, you got me there.

                • by Dster76 ( 877693 )

                  why waste my time working on that, when it is all only for the greater glory of Wolfram's world view?
                  More or less. Except for that $25,000... too bad that's what he has to stoop to to get attention these days.
            • -- with apologies to the great Minsky.

              Perhaps because they both have to do with what a machine with a given set of resources can compute?
              No -- computability theory is concerned with what a machine with unlimited resources can compute.
              • Perhaps because they both have to do with what a machine with a given set of resources can compute?
                No -- computability theory is concerned with what a machine with unlimited resources can compute.
                An infinite tape is still a resource. Also, believe it or not, there are some models of computation which are universal even though they only use finite resources!
                • by Dster76 ( 877693 )

                  An infinite tape is still a resource.

                  This is fun and all, but you're equivocating so fast my head is spinning.

                  The meaning of "given set of resources", in complexity theory, is "growth-bounded time and/or space", neither of which are part of the "resources", now meaning "finite but unbounded time and space", of computability theory.

                  Also, believe it or not, there are some models of computation which are universal even though they only use finite resources!

                  I have no idea what you're talking about.

                  • This is fun and all, but you're equivocating so fast my head is spinning.

                    I'm not equivocating at all. I'm sorry if you don't find the term "resource" appropriate. Both computability theory and complexity theory (which together broadly constitute "theory of computation") can be thought of in terms of what functions machines of various sorts can compute, or, equivalently, what formal languages they recognize. As well as in many other equivalent terms.

                    Also, believe it or not, there are some models of computation which are universal even though they only use finite resources!

                    I have no idea what you're talking about.

                    Is the statement not clear enough, or do you simply disbelieve it? There are many notions of computation. For example, there is no

                    • by Dster76 ( 877693 )

                      Also, believe it or not, there are some models of computation which are universal even though they only use finite resources!

                      Do you understand your own thesis?

                      First you say that there are models of computation that are

                      • universal, and
                      • use finite resources.

                      A computer that uses finite resources is one, for example, that only ever uses 47 squares on a tape.

                      To give me examples, you refer to models of computation that are

                      • not universal, and
                      • use unbounded resources (although only a polynomial of the input).

The sooner all the animals are extinct, the sooner we'll find their money. - Ed Bluestone

Working...