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:

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
[reply]

      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.
[reply]
[reply]

Back to Perl News