In his 2002 book "A New Kind of Science," Stephen Wolfram hypothesized that a particular abstract Turing machine might be the simplest system of its type capable of acting as a universal computer.

In May 2007, the Wolfram 2,3 Turing Machine Research Prize was established to be awarded to the first person or group to prove either that Wolfram's Turing machine is universal or that it is not. Alex Smith, 20, of the United Kingdom, was able to demonstrate with a 40-page proof that Wolfram's Turing machine is, in fact, universal.

This result ends a half-century quest to find the simplest universal Turing machine. It demonstrates that a remarkably simple system can perform any computation that can be done by any computer. It also provides important further evidence for Wolfram's general Principle of Computational Equivalence — a central hypothesis developed in "A New Kind of Science."

"I had no idea how long it would take for the prize to be won," Stephen Wolfram says. "It could have taken a year, a decade or a century. I'm thrilled it was so quick. It's an impressive piece of work."

The immediate implications of the result are primarily scientific, but potential future implications include the possibility of using Wolfram's 2,3 Turing machine to construct a computer operating at a molecular scale.

Smith is an undergraduate studying electronic and computer engineering at the University of Birmingham, U.K. He grew up in Birmingham, and was an alternate for the U.K. International Mathematical Olympiad team. His proof will be published in the journal Complex Systems.






OR/MS Today copyright © 2007 by the Institute for Operations Research and the Management Sciences.
All rights reserved.


Lionheart Publishing, Inc.
506 Roswell Road, Suite 220, Marietta, GA USA
Phone: 770-431-0867 | Fax: 770-432-6969
E-mail: lpi@lionhrtpub.com
Web URL: www.lionhrtpub.com


Web Site © Copyright 2007 by Lionheart Publishing, Inc.
All rights reserved.