The Simplest Turing Machine Has Been Proven Universal

This spring, Stephen Wolfram offered $25,000 for the first person to prove that a very simple Turing machine has the property of being universal. A 20 year old has won the prize.

Wolfram is the Macarthur Fellow genius who wrote Mathematica and founded Wolfram Research, and who, in his mammoth book A New Kind of Science (NKS) introduced what indeed looks like an altogether new kind of science.

This latter work arose from the discovery that you can get what seems to be unbounded complexity out of systems that seem far too simple, such as a few bits of data and a program that can be described in a few words.

In NKS, Wolfram shows that many different kinds of simple systems are essentially equivalent and states his Principle of Computational Equivalence: that almost all processes that are not obviously simple can be viewed as computations of equivalent sophistication.

Which is important because... but what am I doing? I'm not going to try to explain Wolfram's theories. I'm just here to report that on October 24, the winner of this contest will be announced, and we will all see that a Turing machine with just 2 states and 3 colors is a universal computer.

Posted by Mike Swaine at 09:03 PM  Permalink