Smallest universal turing machine found
Comments(0) 
A 20-year old student from Birmingham did a pretty nerdy thing. He won 25.000 USD, by proving the existence of the smallest universal turing machine. For over 40 years the smallest known turing machine had 7 states, a 4-element alphabeth and 28 rules for state-transitions. About 5 years ago, Stephen Wolfram (inventor of Mathematica and founder of Wolfram Research) presented a machine with 2 states and a 5-elemtent alphabeth and resulting 10 state-transition rules. Wolfram found a 2,3 machine, that he thought, could me the smallest one. He also had proven, that two states and a 2-element alphabeth aren’t enough for a universal turing machine. Wolfram research advertised the prize of 25.000 USD for proving the 2,3-machine to be the smallest one existing.
The student found it a challenging puzzle and solved it by trying to prove the machine isn’t universal. But the machine showed behaviours that were more complex. The trick: He built some kind of compiler that transcribes the code of a machine, known to be universal for the 2,3-machine, which proves it to be the smallest existiting universal turing machine.
His 55-pages paper can be read here .
If you want to earn even a Million USD, just prove P != NP. Or another one of the 7 millenium problems of the Clay-Institute. 
Got it from here.
