Wolfram's 2,3 Turing Machine Is Universal!

http://www.wolframscience.com/prizes/tm23/solution_news.html

News Release
Wolfram's 2,3 Turing Machine Is Universal!

October 24, 2007--Wolfram Research and Stephen Wolfram today announced
that 20-year-old Alex Smith of Birmingham, UK has won the US $25,000
Wolfram 2,3 Turing Machine Research Prize.

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 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," said
Stephen Wolfram. "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.

"I saw the prize problem primarily as a puzzle," said Alex Smith. "At
first, I didn't think the Turing machine would be universal. But then
I found a way to show that it is."

Smith is an undergraduate studying electronic and computer engineering
at the University of Birmingham, UK. He grew up in Birmingham, and was
an alternate for the UK International Mathematical Olympiad team.

Smith's proof will be published in the journal Complex Systems.

An official prize ceremony is being planned for November at Bletchley
Park, UK, the site of Alan Turing's wartime work.

The prize was 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 information, see the original media release announcing
the prize, or the prize website.

For Stephen Wolfram's personal reaction to the prize, see his blog
post.

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 and
the Wolfram Science Conference.

.

Relevant Pages