Want to read Slashdot from your mobile device? Point it at m.slashdot.org and keep reading!


Forgot your password?
Check out the new SourceForge HTML5 internet speed test! No Flash necessary and runs on all devices. Also, Slashdot's Facebook page has a chat bot now. Message it for stories and more. ×

Submission + - Wolfram awards $25,000 for flawed proof

An anonymous reader writes: Slashdot readers will have seen an announcement by Stephen Wolfram offering a $25,000 prize for a proof or a disproof that a certain 2-state, 3-color Turing machine is universal. The prize was awarded on October 24th, 2007 to Alex Smith of Birmingham, UK.

However, according to discussion in the Foundation of Mathematics e-mail list, archives of which are available here, the members of the prize committee were "informed but not polled" as to the validity of the proof. The prize committee members were Lenore Blum, Greg Chaitin, Martin Davis, Ron Graham, Yuri Matiyasevich, Marvin Minsky, Dana Scott and Stephen Wolfram. On October 26, Martin Davis wrote to the FOM list that "The determination that Smith's proof is correct seems to have been made entirely by the Wolfram organization. My understanding is that the I/O involves complex encodings."

On October 29th, Stanford computer scientist Vaughan Pratt wrote to the Foundations of Mathematics list that the universality proof of the (2,3) Turing machine was flawed, asking "How did an argument containing such an elementary fallacy get through the filter?" Pratt points out that the fallacy of the proof could be used to "prove" the erroneous statement that a linear bounded automaton is universal. The text of Pratt's email is available here.

Slashdot Top Deals

Mr. Cole's Axiom: The sum of the intelligence on the planet is a constant; the population is growing.