This article was published in Scientific American’s former blog network and reflects the views of the author, not necessarily those of Scientific American
On supporting science journalism
If you're enjoying this article, consider supporting our award-winning journalism by subscribing. By purchasing a subscription you are helping to ensure the future of impactful stories about the discoveries and ideas shaping our world today.
Wolfram Research 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.
