Wolfram: The Simplest Universal Turing Machine is proven by 20 year old student

http://blog.wolfram.com/2007/10/the_prize_is_won_the_simplest.html

by rms • 19 years ago

53 14 19 years ago

blog.wolfram.com

koolmoe2• 19 years ago

I found this part interesting:

"I asked him why he'd worked on it. He said he'd seen it as a nice puzzle. That at first he was pretty sure the Turing machine's behavior was simple enough that he could prove that it wasn't universal. But then, as he studied it, he realized that there were little bits of behavior that were more complicated. And it was with these that he managed to show universality."

Just another data point in favor of tinkering, I guess.

amichail2• 19 years ago

Did all the members of the prize committee agree that this submission should win? Or did Wolfram make the final call based on their feedback?

whacked_new• 19 years ago

I am not familiar with Wolfram's style, but there seemed to be an unsatisfying lack of Alex Smith, but lots of Me, NKS, and PCE, in that post. The headline deserves note because the proof is by a 20-yo but the post doesn't do him justice.

Interesting nevertheless and I hope to get to read more news about the author.

amichail2• 19 years ago

This blog post comes from the humble version of Wolfram!

koolmoe2• 19 years ago

Here are some alternative sources:

http://www.newscentre.bham.ac.uk/press/2007/10/24Oct07Turing...

http://www.nature.com/news/2007/071024/full/news.2007.190.ht...

The second link is particularly informative.

Nate• 19 years ago

There are always two underlying themes in all Wolfram's writings:

1) Wolfram is a genius: the next Newton.

2) Buy Mathematica.

dangph• 19 years ago

He really is a genius though.

lst• 19 years ago

I'll reserve my surprise for the first time someone using this nice theory in some real, traceable experiment...

jimbokun• 19 years ago

"It's just that in our normal efforts of engineering, we've been too constrained to see with such things."

Who is he referring to here? Pretty much any CS or ECE student will encounter the Turing machine at some point. Wolfram talks like he is the only one aware of something that I'm sure is common knowledge among the "normal" engineers responsible for creating the computing machines we use every day.

programnature• 19 years ago

That quote is pretty vague, but I don't think he is trying to say that people haven't heard of Turing machines, which they obviously have.

I think the point is that "textbook" turing machines, just like other "textbook" forms of engineering, are typically constructed by hand, top-down to have a specific, predictable behavior.

What is interesting about Alex Smith's proof is that it implements the reverse approach, starting with an empirical discovery of the 'natural primitives' of the emergent behavior and building up the construction from the bottom up.

jey2• 19 years ago

Where's the paper? And most importantly, how the hell did he go about proving that?

Published proofs are often so opaque, but I always wonder what the mental thought process was to get to the proof. What were you tinkering with, what were the failures, etc

DocSavage• 19 years ago

Here's the paper: http://www.wolframscience.com/prizes/tm23/TM23Proof.pdf

jey2• 19 years ago

Awesome, thanks

DaniFong• 19 years ago

I heard from a math grad student at Princeton that there's some really weird drama behind Wolfram and some of his proofs.

Apparently someone working at Wolfram labs discovered a one dimensional, universal Turing equivalent cellular automata, announced it, and then tried to publish it under his own name. Wolfram apparently sued to keep him from ever speaking of the proof, but the court documents _included_ speaking to Wolfram about it.

So for about a year (or more?), there was a universal Turing machine, but no proof.

I guess this is a different machine, but it still seems really sketchy.

Wolfram: The Simplest Universal Turing Machine is proven by 20 year old student

Related Stories