Matthew Cook
Encyclopedia
Matthew Cook is a mathematician and computer scientist who proved Stephen Wolfram
's conjecture that the Rule 110 cellular automaton
is Turing-complete. Rule 110 is arguably the simplest Turing-complete system currently known.
and grew up in Evanston, Illinois
. His undergraduate studies were at the University of Illinois
and the Budapest Semesters in Mathematics program. In the 1980s Cook qualified as a member of the six-person US team to the International Mathematical Olympiad
. In 1990, Cook went to work for Wolfram Research, makers of the computer algebra system Mathematica
. He did his doctoral work in Computation and Neural Systems at Caltech from 1999 to 2005.
, assisting with work on Wolfram's book, A New Kind of Science
. Among other things, he developed a proof showing that the Rule 110 cellular automaton is Turing-complete. Cook's proof of this fact was first declared obviously impossible by Wolfram in 1985.
Cook presented his proof at the Santa Fe Institute
conference CA98 before the publishing of Wolfram's book — an action that led Wolfram Research to accuse Cook of violating his NDA
and resulted in the blocking of the publication of the proof in the conference proceedings.
A New Kind of Science
was released in 2002 with an outline of the proof. In 2004, Cook published his proof in Wolfram's journal Complex Systems
.
Stephen Wolfram
Stephen Wolfram is a British scientist and the chief designer of the Mathematica software application and the Wolfram Alpha computational knowledge engine.- Biography :...
's conjecture that the Rule 110 cellular automaton
Rule 110 cellular automaton
The Rule 110 cellular automaton is an elementary cellular automaton with the following rule table:In the table above, when the sequence of 1s and 0s corresponding to the new states is regarded as a binary number, the decimal equivalent is 110; hence the name of the rule.-History:Around 2000,...
is Turing-complete. Rule 110 is arguably the simplest Turing-complete system currently known.
Biography
Cook was born in Morgantown, West VirginiaMorgantown, West Virginia
Morgantown is a city in Monongalia County, West Virginia. It is the county seat of Monongalia County. Placed along the banks of the Monongahela River, Morgantown is the largest city in North-Central West Virginia, and the base of the Morgantown metropolitan area...
and grew up in Evanston, Illinois
Evanston, Illinois
Evanston is a suburban municipality in Cook County, Illinois 12 miles north of downtown Chicago, bordering Chicago to the south, Skokie to the west, and Wilmette to the north, with an estimated population of 74,360 as of 2003. It is one of the North Shore communities that adjoin Lake Michigan...
. His undergraduate studies were at the University of Illinois
University of Illinois at Urbana-Champaign
The University of Illinois at Urbana–Champaign is a large public research-intensive university in the state of Illinois, United States. It is the flagship campus of the University of Illinois system...
and the Budapest Semesters in Mathematics program. In the 1980s Cook qualified as a member of the six-person US team to the International Mathematical Olympiad
International Mathematical Olympiad
The International Mathematical Olympiad is an annual six-problem, 42-point mathematical olympiad for pre-collegiate students and is the oldest of the International Science Olympiads. The first IMO was held in Romania in 1959. It has since been held annually, except in 1980...
. In 1990, Cook went to work for Wolfram Research, makers of the computer algebra system Mathematica
Mathematica
Mathematica is a computational software program used in scientific, engineering, and mathematical fields and other areas of technical computing...
. He did his doctoral work in Computation and Neural Systems at Caltech from 1999 to 2005.
Work with Stephen Wolfram
In the 1990s Cook worked as a research assistant to Stephen WolframStephen Wolfram
Stephen Wolfram is a British scientist and the chief designer of the Mathematica software application and the Wolfram Alpha computational knowledge engine.- Biography :...
, assisting with work on Wolfram's book, A New Kind of Science
A New Kind of Science
A New Kind of Science is a book by Stephen Wolfram, published in 2002. It contains an empirical and systematic study of computational systems such as cellular automata...
. Among other things, he developed a proof showing that the Rule 110 cellular automaton is Turing-complete. Cook's proof of this fact was first declared obviously impossible by Wolfram in 1985.
Cook presented his proof at the Santa Fe Institute
Santa Fe Institute
The Santa Fe Institute is an independent, nonprofit theoretical research institute located in Santa Fe and dedicated to the multidisciplinary study of the fundamental principles of complex adaptive systems, including physical, computational, biological, and social systems.The Institute houses a...
conference CA98 before the publishing of Wolfram's book — an action that led Wolfram Research to accuse Cook of violating his NDA
Non-disclosure agreement
A non-disclosure agreement , also known as a confidentiality agreement , confidential disclosure agreement , proprietary information agreement , or secrecy agreement, is a legal contract between at least two parties that outlines confidential material, knowledge, or information that the parties...
and resulted in the blocking of the publication of the proof in the conference proceedings.
A New Kind of Science
A New Kind of Science
A New Kind of Science is a book by Stephen Wolfram, published in 2002. It contains an empirical and systematic study of computational systems such as cellular automata...
was released in 2002 with an outline of the proof. In 2004, Cook published his proof in Wolfram's journal Complex Systems
Complex Systems (journal)
Complex Systems is an interdisciplinary scientific journal. Its subject matter of complex systems ranges across a number of more narrow scientific and engineering fields....
.