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.
Printer-friendly version
Post a Comment