A 20-year-old Birmingham student has won a $25,000 prize for establishing the simplest possible machine able to perform any computation.

The Turing machine, consisting of a two-state, three-colour cellular automaton, was identified five years ago as possibly the simplest possible universal computer by maverick mathematician Stephen Wolfram in his controversial book A new kind of Science.

Last March he offered $25,000 for the first person to prove or disprove the proposition - and Alex Smith, who is studying electrical and computing engineering at Birmingham, took up the challenge.

Smith's 40-page proof was accepted by a committee including Wolfram, mathemeticians Lenore Blum, Greg Chaitin, Martin Davis, Ron Graham, and Yuri Matiyasevich, and MIT artificial-intelligence lab co-founder Marvin Minsky, who discovered a seven-state, four colour universal Turing machine in the early sixties. It has been proved that a two-state two colour machine cannot be universal.

Smith, whose parents are both lecturers at Birmingham, started using computers when he was six years old and is said to be familiar with around 20 programming languages. As a schoolboy he was twice selected as a reserve to represent the UK at the International Mathematical Olympiad.

He said: "I saw the prize problem primarily as a puzzle. At first, I didn't think the Turing machine would be universal. But then I found a way to show that it is."
Computer pioneer Alan Turing took four pages of dense notation in 1936 to describe the original universal computing machine, regarded as a conceptual basis for modern computers

A New Kind of Science ( see my review Is the Universe a Computer?) views the universe as a logical rather than a physical system and seeks to show how very complex systems can derive from very simple rules.

Wolfram says in a blog today that Smith's proof is further evidence of what the book calls the Principle of Computational Equivalence, the proposition that "above a very low threshold, all systems will be exactly equivalent in their computational capabilities."

He says in the blog: "We're used to computers whose CPUs are engineered with millions of gates. It seems bizarre that we should be able to achieve universal computation with a machine as simple [as the one that is the subject of Smith's proof] that we can find just by doing a little searching in the space of possible machines. But that is the new intuition we get from A New Kind of Science ."