MathGroup Archive 2007

[Date Index] [Thread Index] [Author Index]

Search the Archive

The Wolfram 2,3 Turing Machine Research Prize - Announcement

Prize Announcement


October 24th, 2007

The Prize Is Won: The Simplest Universal Turing Machine Is Proved

It has been a long time since Alan Turing's original 1936 paper about
universal Turing machines. In 2002, Stephen Wolfram identified a
candidate for the smallest universal Turing machine, from a search of
the 2,985,984 2-state 3-color possibilities. As of today, we know that
Wolfram's 2,3 Turing machine actually is universal.

On May 14, 2007, as part of the fifth anniversary of Wolfram's book A
New Kind of Science, a $25,000 research prize was announced for
determining whether or not the Wolfram 2,3 Turing machine was in fact
universal. Only five months later, that prize has now been won, ending
a quest of more than half a century to find the very simplest
universal Turing machine.

Alex Smith, a 20-year-old undergraduate in Birmingham, UK, has given a
proof that Wolfram's 2,3 Turing machine is indeed universal. He has a
background in mathematics and esoteric programming languages.

This universality proof is also another piece of evidence for
Wolfram's general Principle of Computational  Equivalence.

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

For more information about the prize and the solution, see:

Stephen Wolfram has posted his personal reaction to the prize at:

-- The Wolfram Science Group

  • Prev by Date: Re: Selecting Rows Where All Columns Satisfy a Condition
  • Next by Date: Re: Re: (x|y) \[element] Integers in Reduce function
  • Previous by thread: Re: Tooltip does not what I expect it to do
  • Next by thread: Graphics export to BMP and JPEG