## Thursday, October 25, 2007

### Wolfram Prize won!- There IS a (2,3)-UTM

Recall that the Wolfram Prize which I blogged about here, was given to anyone who can determine if a certain Turing Machine was universal. It is now known that YES that machine IS universal.

Congrads to Stuart Kurtz, Lance Fortnow, and Kathryn Cramer, Jon Katz, and Katrina LaCurts- NOT for winning the prize but for being the first ones to tell me who won the prize so I could post it. For that they win... a mention in this blog.

Here are some websites about it, most of them emailed to me by Kathryn Cramer.

BACK TO BILL:

How important is the result? Alex Smith got $25,000 for it. The market has spoken, the result is important. #### 8 comments: 1. The market has spoken, the result is important. You are confused. Money is a measure of utility, not of importance, scientific relevance, beauty, happiness, moral value or intelligence. 2. Yes, the millennium problems are worth$1,000,000 because of the immediate utility that their solutions would provide.

Its nice that in the Nature article, they interviewed both Scott Aaronson and Lenore Blum.

3. Given the rather negative reviews that Wolfram's NKS book received, can someone explain why there are so many citations to it?

4. "Given the rather negative reviews that Wolfram's NKS book received, can someone explain why there are so many citations to it?"

5. NKS is a good coffee table book. It does a good job of introducing the concept of a universal computing machine and how simple they can be. The thing I liked most from the book was the description of Matiyasevich's work on solving Hilbert's 10th problem. Using Diophantine equations as the target for a compiler is a cool idea. Has anybody ever actually implemented one?

...Using Diophantine equations as the target for a compiler is a cool idea. Has anybody ever actually implemented one?

Yes, compiling to a diophantine equation solving machine is a -totally- cool idea. Sorry, a virtual machine, because frankly I don't know of any hardware implementations for solving integer equations of that kind.

For that matter, I'm sure there are all sorts of compilers to Turing machines but I don't see them being used.

I have a feeling that maybe LISP/Scheme is compiled to ...um...LISP, and that Haskell is compiled to combinatory (SKI) logic, but that's as far as theoretical machines connect with real ones that I can think of.

7. Another link, discussion from the FOM mailing list, apparently some people think the proof is invalid