May 14, 2007–Wolfram Research and Stephen Wolfram today announced the establishment of a US $25,000 prize for the first person or group to prove (or disprove) that a particular very simple Turing machine can act as a universal computer.
The prize is being announced on the fifth anniversary of the publication of Stephen Wolfram’s influential book A New Kind of Science, and is intended to help stimulate one of the lines of research opened up by the book.
Today’s computers have CPUs with millions of components. But it is known in theory that much simpler systems are also capable of “universal computation,” which means that with appropriate programming, they can perform arbitrary computational tasks. The aim of the Wolfram 2,3 Turing Machine Research Prize announced today is to determine the edge of where universal computation is possible.
Invented by British mathematician Alan Turing in 1936, Turing machines were the first abstract models of today’s computers. Alan Turing’s primary achievement was to construct–on paper–a single “universal Turing machine” that could be made to emulate any other Turing machine, or in effect to perform any computation.
Alan Turing’s insight–which in effect showed that software is possible–is what eventually launched the computer revolution, and led to much of the dramatic growth of technology in the late twentieth century.
In the 1950s and 1960s some research was done into finding the simplest universal Turing machine. By the early 1960s, American artificial intelligence pioneer Marvin Minsky had shown that a particular machine with 28 possible operations (7 states and 4 colors) could be universal. But with little connection being seen to other problems, this result remained largely a curiosity.
The situation changed, however, with Stephen Wolfram’s work, beginning in the early 1980s, on the general science of simple programs and their connection to natural systems.
Wolfram’s work, which culminated in the publication of A New Kind of Science, showed how programs and systems with extremely simple rules can be capable of highly complex behavior–and of sophisticated computation.
Armed with new computer experimentation methodology made possible by his widely used Mathematica software system, Wolfram was able to begin the broad exploration of what he calls the “computational universe.”
Wolfram’s work has led to new insights about many long-standing problems in the physical, biological, mathematical, and social sciences, and showed how the study of simple programs can be connected to many important foundational issues.
“For three hundred years, the exact sciences have been dominated by the idea of using mathematical equations to describe the world,” says Wolfram. “Now, with programs, we have something new, and much more general. And the first step is to explore the basic science of what the simplest possible programs can do.”
Wolfram likens the study of the universe of possible programs to many classic explorations in science–including the exploration of possible chemicals and of possible biological species.
For his 2002 book, Wolfram found many striking examples of programs with extremely simple rules that give rise to highly complex behavior, and he proposed his general Principle of Computational Equivalence to characterize this phenomenon.
One consequence of this principle is that it suggests that universal computation should be common even among systems with very simple rules.
This has several important implications, both conceptual and practical. At a conceptual level it implies a certain fundamental “irreducibility” to many processes in nature, and explains why these processes have been difficult to understand except by simulation. It also has implications for the foundations of mathematics, notably suggesting that mathematics has artificially limited itself to study only areas that avoid the effects of Gödel’s Theorem and formal undecidability.
Wolfram’s concept that universal computation should be ubiquitous–even among systems with simple rules–also has practical implications, notably suggesting that it should be possible to make computational devices out of many new classes of physical systems, especially at the molecular scale.
“Finding the very simplest universal computers is an important way to nail down the Principle of Computational Equivalence,” says Wolfram. “And Turing machines are the classic examples of computational systems.”
In A New Kind of Science, Wolfram showed that a particular Turing machine with just 2 states and 5 colors is universal, substantially improving on Minsky’s previous result. Wolfram systematically studied millions of simple Turing machines, and on the basis of his investigations, identified a candidate for the very simplest possible universal Turing machine–with just 2 states and 3 colors.
It is this Turing machine that is the subject of the prize announced today.
“We want to find the absolute boundary of computation universality in Turing machines,” says Wolfram. “This is an example of important basic research on the computational universe.”
The prize is open to all entrants, both amateur and professional. It has no closing date.
The prize is being adjudicated by a distinguished committee consisting of Lenore Blum, Greg Chaitin, Martin Davis, Ron Graham, Yuri Matiyasevich, Marvin Minsky, Dana Scott, and Stephen Wolfram.
For additional details, see the prize website.
The prize is part of Wolfram Research’s ongoing commitment to the support of scientific research and education. In addition to its acclaimed Mathematica software system, Wolfram Research is also responsible for MathWorld, the world’s #1 mathematics information website, as well as the new Wolfram Demonstrations Project. Wolfram Research also sponsors the prestigious annual NKS Summer School, as well as the Wolfram Science Conference.
For more information see:
http://www.wolframprize.org — the prize announced today
http://www.wolframscience.com — the Wolfram Science (NKS) initiative
http://www.wolfram.com — the Wolfram Research main site
http://www.stephenwolfram.com — the Stephen Wolfram site