0xDE (11011110) wrote,

New record Turing machine

A while back I posted about a problem Stephen Wolfram had posed, of proving that a certain 2-state 3-symbol Turing machine is universal; if true, it would be not only the smallest known universal Turing machine known, but the smallest universal Turing machine possible. Wolfram offered a $25,000 bounty for the proof. Now, that bounty appears to have been collected, by an English undergraduate. For more, see Nature, New Scientist, or Wolfram's blog.

There's not much detail available through those sources, but there's enough to imply that, like the previous proofs of universality for cellular automaton Rule 110, the proof requires relaxing the definition of universality: allowing machines that never terminate, and that start with an infinite set of nonzeros on their tape, with some more complex condition than termination for signaling that an input is accepted or rejected. I haven't had a chance yet to look at the full proof, but it's also online.

In other news, Wolfram has a blog.

Via a comment thread on an unrelated post at Good Math, Bad Math. See also Boing Boing, Geomblog, Slashdot, Gasarch.

ETA: Vaughan Pratt finds a problem. See also /., Aa.
Tags: turing machines
  • Post a new comment


    default userpic

    Your reply will be screened

    Your IP address will be recorded