Student snags maths prize - The Simplest Turing Machine that can compute any problem

Stephen Wolfram's $25,000 prize claimed.

Geoff Brumfiel

The state of the head (up or down droplet) and the pattern of colour (orange, yellow and white) in a given row depends upon the row above. A simple start can lead to an incredibly complex picture.Wolfram Institute

A twenty-year-old university student has answered a challenge by one of the world's most well-known mathematicians.

Alex Smith, a undergraduate electrical engineering student at the University of Birmingham in the United Kingdom, has proven that a primitive type of computer known as a 2,3 Turing machine can solve every computational problem there is. Proving the "universality" of the 2,3 Turing machine was the subject of a US$25,000 challenge from entrepreneur and mathematician Stephen Wolfram.

Wolfram, founder and chief executive of Wolfram Research in Champaign, Illinois, issued the challenge this May to satisfy his own curiosity about how complexity emerges from simple systems. The idea is that a properly applied set of basic rules can create an enormously intricate result. "It's actually a lot easier to make complexity than one might have thought," he says. "I find it particularly tantalizing."

Turing machines were imagined by the British mathematician Alan Turing in 1936, and consist of a read–write head that can be put into one of several states and a long strip of tape on which can be written a set of colours. At each step, the machine looks at the state of the head and the colours on the tape. It then uses a set of fixed rules to move the state of the head into a new position and write a new row of colours on the tape (see picture).

Intricate patterns

The machine specific to Wolfram's prize has a head with only two states and a tape that can hold three colours. It is one of the simplest kind of Turing machines, but depending on the first row on the tape, the results can be remarkably intricate, according to Smith. "Even if you know the rules, you don't necessarily know how it will behave," he says. Smaller, simpler Turing machines are possible (such as 1,2 for example) but these are not thought to be capable of universality.

Smith learned about Wolfram's challenge in an Internet chat room and almost immediately went to work fiddling with the machine. After learning its behaviour, he set about proving that it was computationally equivalent to another type of simple, conceptual computer known as a tag system.

Mathematicians have already shown that tag systems can compute any problem, so proving the two were equivalent effectively proved the power of Wolfram's machine. Smith's proof is 44 pages long.

The solution isn't hugely relevant to modern computer science, says Scott Aaronson, a computer scientist at the Massachusetts Institute of Technology (MIT) in Cambridge, Massachusetts. "Most theoretical computer scientists don't particularly care about finding the smallest universal Turing machines," he wrote in an e-mail. "They see it as a recreational pursuit that interested people in the 60s and 70s but is now sort of 'retro'."

Nevertheless, Lenore Blum, a researcher at the Carnegie Mellon University in Pittburgh, Pennylvania, who served on Wolfram's Prize committee, says the find is interesting enough on its own to warrant attention. "This could stimulate some new work," she says.

For his part, Smith, now in the third year of his electrical engineering degree, says that he has no big plans for his prize money. "I'm just going to put it in the bank," he says.

Find a gallery of more Turing machine outputs on the Wolfram prize site.