Wolfram's 2,3 Turing Machine Is Universal! 288
Rik702 writes "Wolframscience.com have announced that an undergraduate from Birmingham, UK has proved Wolfram's 2,3 Turing Machine is universal." You can read a pdf of the proof as well as some related coverage.
Re:A New Kind of Science (Score:5, Insightful)
Wolfram's claim in NKS that he had discovered some fundamentally new way to approach science that couldn't be handled by existing peer review processes was hogwash. Others had done that kind of thing long before, and little in NKS helped advance the state of the art.
Wolfram's proof in NKS that his Rule 110 cellular automaton was a Universal Turing Machine, was not hogwash. (That UTM was different from the one described in the story, obviously.)
Re:A New Kind of Science (Score:5, Insightful)
Very true. He is a clever guy, but not as clever as he thinks he is, and the book was just regurgitated from other sources. There was very little new or really much science in it. Basically he enumerates a lot of possible combinations of rules and says "some of these will turn out to be slightly interesting, you mark my words.". Well, some of them did. I'm SO impressed.
Look at a map of the world. Some of those countries are going to end up going to war, you mark my words. See? I'm a visionary too.
TWW
Re:A New Kind of Science (Score:4, Insightful)
I recall that to, and was curious enough to see if the criticism was summarized well in Wikipedia. (It is.) [wikipedia.org] Personally, I loved the book, and read it knowing that it was standing on the shoulders of other's work. I remember first reading about the idea of modeling the world as cellular automata in a 1988 issue of The Atlantic, in an article called Did the Universe Just Happen? [digitalphysics.org] (search for "Wolfram" in that page) and I thought his book was a terrific work on the subject.
I can understand how people's nerves got a little tender by having their contributions not been properly attributed, footnoted, etc. It didn't ruin my enjoyment though.
Re:Wow (Score:4, Insightful)
Re:A New Kind of Science (Score:5, Insightful)
The main point here is that we are reaching limits in machine technology, and jumping to a different scale will require a new way of thinking about what we've already learned.
Let me recommend three books: "The Structure of Scientific Revolutions" by Kuhn, "Bionics" by Salsburg, and "How Inventions Begin" by Leinhard. Three different thinkers; three different descriptions of the progress of technology.
I have heard a number of criticisms on NKS, but most of the critics I've met have not actually read the book. (OK, it's a big book... I've found the same problems with people criticizing "Science and Sanity" by Korzybski, "Synergetics" by Fuller, and "Democracy in America" by de Tocqueville.) If you are going to criticize a book, please read it and understand it first.
Recently William Gibson mentioned the problems with writing Science Fiction due to the unpredictability of the future and rapid technological change. As our technology becomes more abstract, more materials will be "intelligent" in new ways. For instance, imagine concrete with the intelligence to repair itself when a pothole is in imminent probability of forming. This type of "Turing Machine" computational ability at the molecular level may be the key to inventing this product.
Uhh, what? (Score:4, Insightful)
What's the significance of 2,3? (Bit states, color?)
What did this discovery actually teach us? How is it useful?
Re:The paper (Score:2, Insightful)
Re:Turing Machines (Score:4, Insightful)
Re:A New Kind of Science (Score:5, Insightful)
Re:An Undergrad? (Score:3, Insightful)
Yes because an undergrad doesn't always have the experience and education to formulate such proofs.
But no because an undergrad doesn't have as many assumptions. An undergrad is a bit more naive you could say and they will be more likely to try and figure out something a lot of more experienced people assume is otherwise. An undergrad is more likely to spend time on problems like this as a discovery mechanism.
When I was an undergrad I used to like to play around with problems like this. NP-Complete problems (what a waste of time!), set theory things, etc. I liked to learn things first hand for myself sometimes instead of assuming the book was right.
I never found anything notable but it was fun.
This kid made a pretty great proof. I'm not sure how important it is but I do remember in a theory of computation course it was presented as an open problem.
Great Result - Great Inspiration (Score:5, Insightful)
It takes a push from various people, and communication and conflicts of opinions to wind up exciting someone to sit down and solve some excruciating problem.
I don't care whether it is math, mechanics, biology or physics, someone has to do the HARD work, and Wolfram contributed in his own promotional way, and Alex Smith solved the SOB of the smallest Turing problem, with a significant set of input from the judging panel requesting addtional work.
A community of interested people wound up involved in getting an advanced solution. Then others said "but what good is it in requiring an infinite memory/tape". Similar things were said about past inventions, until other inventors figured out how to make the prior/first invention practical.
I love math, but am not a mathemetician, so I have to contribute with the mundane discoveries and designs I do in my arena of medical product design, and they too will live on beyond me.
The complainers should leave something that outlives them. That is what makes for a great society.
Re:A New Kind of Science (Score:3, Insightful)
Case in point? In a recent interview, Noam Chomsky admitted to writing his famous criticism of B. F. Skinner's book "Verbal Behavior" BEFORE it had been published and, in fact, based his review on much older material including notes taken by students of lectures presented YEARS before the final version was published. This is evident to anyone who has read both Chomsky's review and Skinner's verbal behavior (further reading: McCorquodale, 1970).
And the impact of Chomsky's admission? Zero... Although, at the time, Chomsky's unfounded review effectively reduced the credibility of an entire field of psychology.
Re:Molecular TM is nonsense (Score:1, Insightful)
And, sure, the Turing model is hideously inefficient, but with something as small and simple as DNA, you can perform millions of computations not just per-second, but simulateously, perhaps bringing some NP-complete computations [wikipedia.org] within the realm of practical possibility.
Re:a 40-page proof for a "simple machine"? (Score:2, Insightful)
arbritrary_values(&x, &y, &z, &n);
assert(n>2);
assert(pow(x,n)+pow(y,n)!=pow(z,n));
The proof for that was something like 200 pages and took approximately 300 years, IIRC.
Re:Science is forever .. right angles (Score:3, Insightful)
Well, you got me there chief. Nature doesn't have any true right triangles. And without the right triangle you've got no trigonometry, so that's gotta go too. That also takes geometry pretty much out of the picture too, since there are no straight lines in nature either.
Now that you've got me thinking about it, calculus is based on infinitely small approximations. And we know the material universe is made of atoms, which are discrete. So calculus has to go too, since there is a limit on how small you can go. That also rules out some important irrational numbers, such as pi and e. So there goes pretty much all of engineering as well.
So my advice to you would be to go ahead and live your life without any of the benefits of trig, geometry, calculus, and engineering since they don't represent anything that exists exactly in nature. Enjoy your cave.
Me, I'll be in my house with the non-perfect 90 degree walls, electricity, light, heat, computer and internet connection.