Simplest Turing Machine
One of the cellular automata that were made famous by Stephen Wolfram in his fascinating book “A New Kind of Science” (or NKS for its worshipers) has proven to be a universal Turing machine. It’s the 2,3 machine (named 2,3 because it has 2 states and 3 colors for each state.)
Apparently, it had been proven before that no universal Turing machines with 2 states and 2 colors or less existed (it should not be difficult, because the number of all such machines is really limited.) Now, after a $25’000 prize was announced a few months back, an undergraduate student has proven that the said automaton is indeed universal and can perform any computation that the original Turing machine was capable of.
Two notes: First, I’m not a fan of NKS and Wolfram. He really over-estimates himself and his book. On the other hand, he is a genius and NKS is interesting and a mind-opener. Besides, people wanted to burn Galileo at stake in his own time! Who am I to decide who is right and who is wrong?!
Second, whenever I hear/read/write “Wolfram”, I can’t not think of “Wolfram & Hart” (in Angel TV series) and therefore Buffyverse! Joss Whedon rulz!
UPDATE 2007-10-30: It seems that I was in too much hurry in announcing this. The proof has come under scrutiny and now it seems that it has flaws. Read more on Slashdot.
