Tuesday, May 15, 2007

Turing universality prize from Wolfram

Not quite the big bucks of the Millenium prizes, but a nice $25,000 for proving that an exceedingly simple Turing machine (an abstract symbol manipulations device) discovered by Stephan Wolfram is in fact a Universal Turing machine (A Turing machine which can simulate any other Turing machine, and therefore any computer program, which generally have much more complex rules).

The contest is to show that a particular two state, three colour Turing machine is universal.

This comes from the newly created Wolfram blog. See here for details about the competition, more about Turing machines, and more about this particular, incredibly simple algorithm.

[Thanks to Blake Stacey for pointing out the typo in the above. Indeed the Universality of the 2,5 Turing machine had been proved already, by Matthew Cook]


Blake Stacey said...

The contest is actually to prove the universality of a 2,3 Turing machine, not the famous 2,5 machine known as Rule 110.

Also, the universality of the Rule 110 cellular automaton was proved by Matthew Cook, not Wolfram.

Unknown said...

Hi Blake, absolutely right, thanks for the correction and the extra information. J