The simplest Turing machine
November 14th, 2007
Stephen Wolfram is a famous theoretical physicist, mathematician, and computer scientist. He is the inventor of Mathematica. His ground-breaking book, A New Kind of Science, presents a new way, other than traditional mathematics, to model and understand the complexity of nature. I will write about this book in a future post. Today I would like to talk about the simplest Turing machine.
For a long time computer scientists are puzzled with the question, “Can we simplify the structure of a computer as much as possible and still retain all the computing power of a computer?” In another words, “What is the simplest theoretical computer, or Turing machine?” Turing machine is a theoretical computational model. Although it can do all the computing tasks a modern computer does, it will take a much longer time to do it. In reality people will never build and use a Turing machine.
Wolfram is interested in finding the simplest Turing machine. On May 14, 2007, Wolfram announced a $25,000 prize for a proof of whether a 2-state, 3-color Turing machine is the simplest Turing machine. Amazingly, the prize was won only five months later by Alex Smith–a 20-year-old undergraduate from Birmingham, UK. I guess sometimes it just takes courage and a reasonable math training to solve an open problem posted by one of the world’s most well-known scientists.
Read detailed stories from Nature, Scientific American, and Wolfram’s blog.
