I wrote previously about a competition Stephen Wolfram (of Mathematica fame) had to show that a particularly small Turing Machine (the “2,3 Turing Machine”) is universal. Sure enough it is, as shown by a University of Birmingham (UK) student, Alex Smith, as reported in Nature. This machine, as shown in a diagram from Wolfram’s blog on the prize has just 2 states and 3 colors. It is certainly surprising that such a simple structure can compute anything any computer can!
I had hoped that operations research might be of help in this, but that does not seem to be the case.
Smith learned about Wolfram’s challenge in an Internet chat room and almost immediately went to work fiddling with the machine. After learning its behaviour, he set about proving that it was computationally equivalent to another type of simple, conceptual computer known as a tag system.
Mathematicians have already shown that tag systems can compute any problem, so proving the two were equivalent effectively proved the power of Wolfram’s machine. Smith’s proof is 44 pages long.
My (what is the word for “person who makes me jealous”? Hmmm… I’ll make up a word: “Jealous Idol”) jidol, Scott Aaronson managed to tear himself away from supermodels to provide a quote (albeit of a “raining on a parade” type):
The solution isn’t hugely relevant to modern computer science, says Scott Aaronson, a computer scientist at the Massachusetts Institute of Technology (MIT) in Cambridge, Massachusetts. “Most theoretical computer scientists don’t particularly care about finding the smallest universal Turing machines,” he wrote in an e-mail. “They see it as a recreational pursuit that interested people in the 60s and 70s but is now sort of ‘retro’.”
Thanks to Kathryn Cramer for pointing out the result of this competition. She also has a very nice posting in her blog on visualizing the effect of the Federal Reserve rate cut, relevant to my previous posting on visualization.