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.
Some changes have been made to LiveJournal, and we hope you enjoy them! As we continue to improve the site on a daily basis to make your experience here better and faster, we would greatly appreciate your feedback about these changes. Please let us know what we can do for you!