A 20-year-old computer science undergraduate has claimed a prestigious $25,000 mathematics prize by proving that a simple mathematical calculator can be used as a “universal computing machine”.
The proof involves a kind of mathematical calculator known as a Turing machine, a concept originally studied by mathematician Alan Turing in the 1930s. Some kinds of Turing machine are “universal computers” – given enough time and memory, they can solve almost any mathematical problem.
Mathematician Stephen Wolfram discussed the simplest possible Turing machine, a cellular automaton that uses just three different symbols in its calculations, in his 2002 book A New Kind of Science.
In May 2007, Wolfram announced a $25,000 award to anyone who could prove that this Turing machine is also universal. Other simple Turing machines are already known to have this property, but in those cases the proof was supplied by professional mathematicians.
Advertisement
Molecular computing
The proof devised by Alex Smith, who is studying electronics and computing at the University of Birmingham, UK, involves showing that the machine is equivalent to another mathematical device already known to be a universal computer.
The solution will impress mathematicians, but Wolfram says it is not just of theoretical interest. Turing machines are loose models for molecular automata – simple computing devices built from DNA and other biological molecules. Showing that even the simplest possible machine is capable of being a universal computer suggests that equally simple molecular versions could one day form the basis of new kinds of computing, says Wolfram.
Smith, who cracked the problem during his holidays, says he was initially sceptical about his chances. He started work after telling his mother about the prize – she advised him to go for it because it is “the kind of thing he is good at”. That may be something of an understatement, since Smith knows 20 different programming languages, including six he describes as “esoteric”.
Wolfram admits had no idea how long it would take for the prize to be claimed and that, when an answer arrived this June, it was not the speed with which the problem had been solved that he found surprising, but the age and expertise of the winner.
“We are also at the end of a quest that has spanned more than half a century to find the very simplest universal Turing machine,” he writes on his personal blog.
