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.




Comments:

arvindn:
2007-10-25T22:08:06Z
This is definitely the most awesome thing in TCS I've seen in a while.
11011110:
2007-10-26T03:02:28Z
Although the problem and result are clearly within the boundaries of TCS, it would be kind of arrogant for the TCS community to take much credit for it, though — Wolfram's not really part of that community himself, and my recollection of the community's response when he posted the prize (for instance, in the comments here) was largely indifference.
None: SODA
2007-11-06T18:53:36Z
We speak almost simultaneously in different sessions. What a pity... Gabriel