Smallest possible universal Turing Machine found (with Perl's help)

A few months ago, Stephen Wolfram (of Mathematica and A New Kind Of Science fame) announced a $25,000 reward for proving or disproving that a certain small Turing machine was universal. The Turing machine has 2 states and uses 3 tape symbols. If universal, it would necessarily be the smallest possible universal Turing machine.

The prize has now been claimed by 20-year old Alex Smith, who proved that the machine was in fact universal. His long proof can be found here if you're interested. Perl enthusiasts will be glad to know that it appears he used a lot of Perl simulations to help decipher the behavior of this machine. His code is included in the PDF proof document.

See also:

Wolfram blog entry
Nature article
NewScientist article
some blog posts: Complexity blog, David Eppstein

blokhead

Comment on Smallest possible universal Turing Machine found (with Perl's help)

Replies are listed 'Best First'.
Re: Smallest possible universal Turing Machine found (with Perl's help) by sir_lichtkind (Friar) on Oct 30, 2007 at 12:41 UTC
Maybe not. discussion is still goin. http://science.slashdot.org/article.pl?sid=07/10/29/2212226&from=rss my kephra at http://proton-ce.sourceforge.net	[reply]
Re^2: Smallest possible universal Turing Machine found (with Perl's help) by BrowserUk (Patriarch) on Oct 30, 2007 at 19:07 UTC
Kinda supports my long held belief that the idea that mathematical proofs can be used as a substitute for, or as a way to reduce the need for, the conventional testing and analysis of computer programs, is pretty much foundationless. The problem with mathemeatical proofs is that not only do experts make mistakes when writing them, but other experts make mistakes when verifying them. And there are no methods available for proving proofs, beyond expert review. Which somewhat makes a mockery of the idea that you can achieve "provably correct programs" by compiling them directly from mathematical proof notations. Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. "Science is about questioning the status quo. Questioning authority". In the absence of evidence, opinion is indistinguishable from prejudice. "Too many [] have been sedated by an oppressive environment of political correctness and risk aversion."	[reply]
Re^2: Smallest possible universal Turing Machine found (with Perl's help) by Argel (Prior) on Nov 17, 2007 at 00:12 UTC
According to Confusion on FOM the proof stands.	[reply]


Your skill will accomplish what the force of many cannot
	PerlMonks