Computational Complexity

Thursday, October 25, 2007

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

Posted by GASARCH

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.

1. write up in nature
2. Stephen Wolfram's blog!
3. Smith's 44 page proof!
4. New Scientist Story
5. Alex Smith's Photo!
6. Geomblog scooped me here
7. Live Journal

BACK TO BILL:

How important is the result? Alex Smith got $25,000 for it. The market has spoken, the result is important.

12:23 PM # 8 comments

1.  Anonymous says:  
   
   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.
   

   1:40 PM, October 25, 2007

2.  Anonymous says:  
   
   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.
   

   1:49 PM, October 25, 2007

3.  Anonymous says:  
   
   Given the rather negative reviews that Wolfram's NKS book received, can someone explain why there are so many citations to it?
   
   http://scholar.google.ca/scholar?hl=en&lr=&cites=3139230665686742056
   

   2:11 PM, October 25, 2007

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

   2:36 PM, October 25, 2007

5.  Chad Brewbaker says:  
   
   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?
   

   12:23 PM, October 26, 2007

6.  Mitch says:  
   
   Chad Brewbaker said...
   
   ...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.
   

   2:29 PM, October 29, 2007

7.  Yaroslav says:  
   
   Another link, discussion from the FOM mailing list, apparently some people think the proof is invalid
   http://cs.nyu.edu/pipermail/fom/2007-October/thread.html#12156
   

   9:06 PM, October 31, 2007

8.  Anonymous says:  
   
   The market has spoken ? I frankly don't think so. And if it did, it certainly never spoke of "important result".
   
   There might be bugs in the proof.
   

   12:45 PM, November 02, 2007

Comment Feeds: This Post All