Prize Announced for Determining the Boundaries of Turing Machine Computation
May 14, 2007Wolfram 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 constructon papera single "universal Turing machine" that could
be made to emulate any other Turing machine, or in effect to perform any computation.
Alan Turing's insightwhich in effect showed that software is possibleis 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 behaviorand 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 longstanding 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 scienceincluding 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 ubiquitouseven among systems with simple rulesalso 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 machinewith 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
