Slashdot Mirror
Wolfram's 2,3 Turing Machine Is Universal!
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.
That was on my To Do list for next week.
He tried to kill me with a forklift!
Clarification:
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.)
Apology to Ubuntu forum.
...does it run Linux?
Give me Classic Slashdot or give me death!
For some perspectives on the complete nonprofundity and borderline academic dishonesty of Wolfram's book from some people who _do_ know what they're talking about, see this review (PDF) from the Notices of the American Mathematical Society and this collection of many more links to reviews.
Constructive logic destructs my brain.
Yes the 'blowing it' pun was intended...
Wolfram never actually proved Rule 110. The actual work for that was done by Matthew Cook - who presented the paper at a conference while he was working in Wolfram's employ - and eventually got himself and the conference sued. Apparently, working for Wolfram means you sign over any and all papers, ideas, and patents over to him, without receiving any real credit for them.
Another little-known fact is that Wolfram was just one of several people who initially coded Mathematica. He decided one day to take all the code, form a company on his own, and engage in expensive lawsuits with all of his former collaborators to gain ownership of the code.
As far as I'm concerned, the man at this point is wasted intelligence. He may come out with another non-trivial result or two over the course of the rest of his life, but his best contributions to the science may yet come from his wallet - like sponsoring prizes like this one.
http://www.cscs.umich.edu/~crshalizi/reviews/wolfram/
The above link is worthwhile, entertaining, and should help bring back anyone who drank the Wolfram Kool-Aid.
(go blue)
But it's worth noting that the Rule 110 proof, while not hogwash, was also not Wolfram's.
Give me Classic Slashdot or give me death!
I for one now admit that all previously welcomed overlords can be emulated by this 2 state, 3 color overlord.
@AlexSheive
The wolfram site is slashdotted but this link for the article in nature is not.
~ In Trust, We Trust ~
Sometimes the changes in Science come from just thinking about things differently. Whether Stephen is arrogant or not is irrelevant to the ideas or claims being evaluated. I doubt anything is invented in a vacuum, but rather a product of all the little discoveries and thoughts finally coalescing into something tangible.
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.
"The mind works quicker than you think!"
N = 1. Solved! I can't believe they weren't able to figure that out.
steampunk web design
Well said, Comic Book Guy!
You don't read a lot of serious science here because this isn't the place for it.
Every so often a fairly specialized technical discussion will crop up and even to people like me, who are casually interested, it is obvious that people who are serious about the subject are posting. They don't write full blown journal quality posts because a) see above, and b) as you correctly point out, Slashdot's demographic on the whole doesn't have the higher level knowledge necessary to understand them.
But that doesn't mean there isn't an interesting discussion going on. On the contrary, there are good opportunities to interact with serious people you would otherwise never be able to access. If you can effectively ignore the "I got wireless working under Linux so I know everything" mentality anyway.
Along the lines of the RIAA submissions from NewYorkCountryLawyer. How many attorneys who actively defend against RIAA lawsuits as their primary practice do you meet in a day?
"Sacrifice for the good of The State" - The State
Alan Turing is usually considered to be the father of computers. He invented a theoretical machine that he conjectured could solve any problem that could be solved by a machine. It consisted of a an infinitely long tape (memory) and a small finite set of operations that could be performed infinitely fast. Modern computers are *very* similar to his theoretical machine, except they're only very fast (as opposed to infinitely fast) and they only have a lot of memory (as opposed to an infinite amount of memory). No one has ever found a problem that could be solved by a more complex machine and could show that it couldn't be solved by a Turing machine. (BTW, Turing eventually killed himself by eating a poisoned apple after most of the scientific community shunned his work due to some personal habits. This was the inspiration for Apple computers' logo.) So Wolfram proposed an even simpler machine and conjectured that it could solve anything that a Turing machine could solve. Now this guy proved that Wolfram was right. I should mention for completeness that two other guys (Church, and dang, I forgot the other one) also proposed systems that were provably equivalent to Turing's machine around the same time, but Turing's was the easiest one to turn into an actual machine.
As an undergraduate in 1968, I did an independent study that estimated the size of the universal turing machine described in: Davis, Martin (1958), Computability and Unsolvability, New York NY: McGraw-Hill Book Company. This was tedious but not hard. For any slashdotters ready to rush out and implement a working universal Turing machine, be forwarned that your parts list needs to include an infinitely long tape. Worse, when calculating the output of an arbitrary recursive function on your universal Turing machine, you won't know in advance how long the tape needs to be, in case you were cheap and bought a tape with finite length rather than the more expensive infinite one.
The universal Turing machine itself consists of a large but quite finite set of quadruples. The problem is the longish tape.
Lots of nitpicking of the solution and Wolfram and such have been posted. Let the nitpickers contribute!
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.
I believe it's "the machine can be in one of two states, and each point on the tape can have one of three colors"; not "a machine that has two states, each of which can be three colors," which is gibberish.
Those who fail to understand communication protocols, are doomed to repeat them over port 80.