RESEARCH NEWS

$25k prize for solving computing's 'simplest' problem

17 May 2007



Wolfram Research, the creator of Mathematica, is to award a $25,000 prize to the first person or group to solve a 70-year-old puzzle at the very core of modern computing.

The prize will go to whoever can prove, or disprove that a very simple theoretical computer, stipulated by Stephen Wolfram, can act as a universal computer – in other words, emulate any other possible computer.

The problem was originally laid down in 1937 by Alan Turing, and paved the way for the computer revolution. He created the Turing machine – an abstract model of a computer – and showed that a 'universal Turing machine' could in effect perform any computation.

Since then, there has been a fight to find the simplest universal Turing machine. In the '60s the simplest found had seven states and four colours – 28 operations in total. The prize was announced on the fifth anniversary of Stephen Wolfram’s book A New Kind of Science, which proved a machine with just two states and five colours is universal.

But Wolfram wants the prizewinner to go one better and prove that a machine with only two states and three colours is a universal Turing machine, making it the simplest possible.

The prize is open to anyone, has no closing date, and will be judged by a committee with nine members, including Stephen Wolfram.

Related internet links

Wolfram Prize website