A proof made public today illustrates thatStephen Wolfram's 2,3 Turing machine number 596440 is a universal Turing machine, and ithas netted a University of Birmingham undergraduate $25,000. In 1936, mathematician Alan Turing proposed a machine that was the original idealized computer. A small subset of these Turing machines are known as Universal Turing machines; they are capable of solving any computational problem known. In May, mathematician Stephen Wolfram put forth the challenge to amateur and professional mathematicians alike to determine if one of the Turing machines listed in his book, "A New Kind of Science," was indeed universal.
Turing machines aresimple logic devices that can be made to simulate the logic of any standard computer that could be constructed. They consist of an infinite number of cells on a tape (the memory) and an active cell that is referred to as the "head." Each cell can be one of a set number of colors, and the head can have a fixed number of states. A set of rules determine how the combination of cell color and head state dictates what color should be written to the tape, what state the head should be placed in, and what direction it should move (left or right).
2,3 Turing Machine, number 596440
in Wolfram's numbering scheme
On the fifth anniversary of the publication of "A New Kind of Science," Wolfram issued a challenge, namely, "how simple can the rules for a universal Turing machine be?" In order to spur interest in this, he offered up a $25,000 prize for anyone who could prove, or disprove, that the 2-state, 3-color Turing machine illustrated at right is universal. Finding small universal Turing machines is not a major problem in modern computer science or mathematics. According to MIT computer scientist Scott Aaronson, "Most theoretical computer scientists don't particularly care about finding the smallest universal Turing machines. They see it as a recreational pursuit that interested people in the 60s and 70s but is now sort of 'retro.'" However, people on Wolfram's prize committee hoped this would spur new work.
While not the $1,000,000prize attached to the Clay Millennium problems, it spurred interest in at least one person. 20-year-old Alex Smith, an electronic and computer engineering student at the University of Birmingham in the UK, has solved the problem and will receive the award money.
Smith said he first heard about the problem in an Internet chat room, decided the problem was interesting, and attempted to tackle it. His proof was not direct; he demonstrated that the 2,3 Turing machine was computationally equivalent to a tag machine—something that is already known to be universal. In addition to his proof—available for free (PDF)—he developed a "compiler" that would generate 2,3 Turing machine code that is capable of solving any computational problem. According to Smith, he has no big plans for the prize money. "I'm just going to put it in the bank," he said.