Controversial Turing Machine Proof

November 2, 2007

Alex Smith, a 20-year-old undergraduate in computer science at the University of Birmingham in England recently won $25,000 for apparently proving that a particularly simple mathematical system can function as a "universal computing machine." In other words, it can perform any computation that can be done by any computer.

This achievement came just months after Stephen Wolfram of Wolfram Research offered the award to anyone who could prove or disprove the conjecture that a particular 2-state, 3-color Turing machine is universal. If true, that would make it the simplest universal Turing machine — and perhaps the simplest possible universal computational system.

Wolfram admitted that he had no idea how long it would take for the prize to be claimed. When Smith's proof arrived last June, however, it was not the quick solution that surprised Wolfram but rather the age and expertise of the winner. He also noted that the result is not just of theoretical interest. Turing machines are models for molecular automata — simple computing devices built from DNA and other biological molecules. Showing that even a very simple machine is capable of being a universal computer suggests that molecular versions could one day form the basis of new kinds of computing.

"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," Wolfram wrote on his blog.

In a subsequent development, Vaughan Pratt of Stanford University posted a message to the Foundations of Mathematics mailing list arguing that Smith's proof is flawed: It does not meet the standard criteria for proving universality. Todd Rowland of Wolfram Research countered that argument by pointing out in a message that Smith's approach does meet the necessary criteria when restrictions on a Turing machine's initial condition are relaxed.

"Smith's use of non-repetitive infinite initial conditions is controversial, but is a natural extension of current definitions which allow infinite repetitive initial conditions," Rowland noted. "We hope that the ensuing discussion will enrich debate in the scientific community concerning the nature of computational universality."

Whether Wolfram's 2-state, 3-color Turing machine is universal in the original sense of the word remains an open question.

Source: Wolfram Institute, Oct. 24, 2007; New Scientist, Oct. 24, 2007; Slashdot, Oct. 29, 2007.