Wolfram: The Simplest Universal Turing Machine is proven by 20 year old student(blog.wolfram.com)
blog.wolfram.com
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
15 comments
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.
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.
This blog post comes from the humble version of Wolfram!
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.
"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.
"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.
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.
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.
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.
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.
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.
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
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
Here's the paper:
http://www.wolframscience.com/prizes/tm23/TM23Proof.pdf
Awesome, thanks
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?
I'll reserve my surprise for the first time someone using this nice theory in some real, traceable experiment...
Interesting nevertheless and I hope to get to read more news about the author.