Hey, remember that $25,000 prize awarded by software company Wolfram Research last week
for identifying the simplest "universal" theoretical computer, or Turing machine? There's now a slight catch: It might be wrong
On a mathematics mailing list this week, Stanford University computer scientist Vaughan Pratt said there are technical problems
with the nearly 50-page proof
A Turing machine is a dinky theoretical gadget that moves back and forth on a long string of numbers--its program, basically--scanning them one at a time and switching their values according to a few simple rules. The requirement of the proof was to show that nearly the simplest conceivable Turing machine is universal, or capable of simulating all other Turing machines, which in their various forms could in principle simulate the climate, shuffle your iPod playlist, etc.
For more on why this prize came about and what it means, check out my story
The new wrinkle, according to computer scientist Martin Davis (who I quoted in the story and spoke to again today, and who co-manages the mailing list), is whether the universality comes from the simple actions the machine performs or from the program, which can get pretty complicated, as in the prize-winning proof submitted by 20-year-old Alex Smith of Birmingham, England (pictured above).
From talking to Smith, I can report that he was aware of this potential pitfall. Ditto for Davis, who saw a first draft of the proof, and Stephen Wolfram. Pratt is saying that Smith (and the proof checkers--mainly three people paid by Wolfram Research) nonetheless overlooked a subtle technical thing that people new to this line of work tend to overlook.
Pratt's exact words were, in part, "How did an argument containing such an elementary fallacy get through the filter?" Wolfram
and his employees
chimed in (Wolfram even said he's thinking of setting up more prizes), and now Smith and Pratt are politely hashing it out
For the record, quantum computation theorist Scott Aaronson states truly on his blog
that he did alert me to the fact that he considered the prize description
fuzzily worded, opening up a gray area that is currently being charted.