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.
No, it isn't. Certainly they have some results but he's still an arrogant bastard who hasn't brought anything new to the table.
Nor is this 2,3 machine going to revolutionise science.
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.
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!
The wolfram site is slashdotted but this link for the article in nature is not.
~ In Trust, We Trust ~
There's a $1 million prize for proving or disproving P = NP from the Clay Mathematics institute if you're still interested.
An old-timer with old-timey ideas.
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.
Turing machines are abstractions of what it means to compute.
Consider the problem of sorting n numbers. In terms of computing, one is interested in computing a sequence of integers formed by rearranging given numbers that satisfy some (here monotonicity) property. Now, if one is given 5 numbers to sort one could do one thing to sort them and given 10 numbers to sort, something else. Existence of a Turing machine for sorting means that one could follow only one set of rules and sort any number of input numbers.
The general Turing machine has a tape to write on, on which one (the head) can move left and right and depending on the state of tape decide to change symbols and finally halt at some specific state. The number of states q and number of symbols s define a (q,s) Turing machine.
This notion obviously creates many different Turing machines for different problems. The natural question then is whether there is a Turing machine that simulates all other Turing machines by just reading the encoding of the given Turing machine (M) and its input (n) and simulating the steps on M on input n. If such a machine exists (and they do more or less), then if one were to create computing devices one would just need to implement the one Universal Turing Machine (UMT) and leave it to the programmer to code any other machine on top of it. That is how most computers work. They are essentially UMTs (of course you have to pretend that they have infinite memory in terms of possibility of adding more.)
So if you wanted a really tiny UMT, how tiny can it get? The result mentioned in the story says that you just need 2 states of the machine and 5 symbols on the tape, hence (2,5) UMT. The hope here is maybe someday we will actually implement these very small UMTs on nano-scale (maybe to program the http://en.wikipedia.org/wiki/Self-replicating_spacecraft van-neumann probe?)
If this machine had turned out to be a non-UTM then you would have needed a bigger computer to simulate all other computers. With this discovery we now know that everything that one can (reasonably) hope to compute algorithmically can be done by a pretty dumb rule. The controller of a real computer can be as small as requiring just 1 bit to store its state and just 3 bits to encode its symbols. Even though (maybe ) not for any practical use, the result sounds extremely interesting (and perhaps humbling). On the practical side, I can imagine this machine requiring very large tape for running relatively simple algorithms.
From the article:
So basically there's a machine that has two states, each of which can be three colors, and that machine can perform ANY computation that an x86 cpu can perform. The code to add two 32 bit numbers in an x86 processor might be just a few bytes and the code to do the same thing with this 2,3 Turing machine might be thousands of bytes, but it can do it. It will be horribly inefficient and slow, but it can be done. They've proved that a 2,2 machine is impossible so a 2,3 machine was the simplest possible theoretical Turing machine. This paper proved that one exists. It doesn't have a practical application right now, but the article mentions possible molecular computers that can use this simple machines to do calculations on strands of molecules like DNA.
here you go
A system is "Universal" if it can, given infinite memory and an appropriate program, compute any computable function. A previous system even more simple than this one, Rule 110, was proven to be Universal by one of Wolfram's associates (Wolfram had the idea that it might be, Matthew Cook discovered the proof). However, a Universal Turing machine has some extra requirements with regards to the implementation. So this is the simplest Universal Turing Machine.
If you already know programming, then here's how to think of it:
A Turing machine is a programming language.
A Universal Turing machine is a language that is sufficiently flexible enough to perform any computation (including emulate any other Turing machine - i.e. language)
A Non-Universal Turing machine is a language that is built to do a specific purpose well, but does not have enough flexibility to perform any computation.
For computer programmers, nearly every general-purpose language we deal with on a daily basis is Turing-complete. An example of a non-Turing Complete language might be a configuration file. It has a language, you may even be able to do some basic scripting in it, but unless it is built out of a general-purpose language you cannot perform any computation in it.
What they think it is useful for is to help us to make nanomachines easier. If we can construct a Turing machine with simpler parts, we can have a compiler that can pick up the slack in making the program.
On another note, Wolfram takes these tiny Turing machines as reason to not believe that people have souls, while I on the other hand take these to indicate that life must be designed, but that has to do more with the general properties of Turing machines rather than the size of them.
Engineering and the Ultimate
No. Color and state play very different roles. Colors ("symbols" are also used) decide the input and output strings that can be generated (the colors make up the alphabet), states are internal parts of the machine.
As such, you're using a different alphabet to write on your tape. Which means that the strings that will be accepted/rejected by one machine will definitely be different from those accepted by the other machine, and as such they are not equivalent. By definition, machines are equivalent if they decide the same language.
One CS student VS 893 DOS games: Let's play oldies
In the interest of counteracting Wolfram's megalomanaical "new kind of science" that attempts to blot out appropriate credit where it's due, I think it's worth just posting the name of the person who should be attributed with the 110 proof:
Matthew Cook.
That way, at least you'll see the name if you don't want to read the story.
This is bullshit.
In reading my own post, I realized that the fricking parent story doesn't even list the name of the person who did the proof.
Everytime Wolfram gets involved with something, it's like entering some bizarro land where no one exists besides Wolfram.
His name is
Alex Smith.
Alex Smith did the proof. Is that so frickin hard?
http://en.wikipedia.org/wiki/Stephen_Wolfram
The settlement aficr was free licenses to Caltech in perpetuity.
"Turing eventually killed himself by eating a poisoned apple after most of the scientific community shunned his work due to some personal habits."
Much, much sadder. He was prosecuted for homosexuality, sentenced to a course of estrogen, became depressed, and killed himself. This was how a grateful nation treated a man who had played a large, perhaps the leading role, in decoding Enigma signals - the decisive element in the Battle of the Atlantic. Tragic and wicked.
Damnit, that was supposed to be:
I read all of NKS. The critics are right. The "New" Kind of Science is at least 20 years old. NKS's value is that of a handbook of results in the fields of artificial life, artificial intelligence, complexity theory, and a few other related fields. In that respect, it is rather good. But Wolfram's citations are inadequate at best. My informed -- since I read dozens of primary sources first -- opinion is that he plagiarized the work of many. It is not revolutionary. It is a compilation.
I do like my Korzybski, by the way. But in many ways, Science and Sanity is a simplified version of Wittgenstein's Philosophical Investigations. The complexity in Wittgenstein's text is there for a reason. Serious problems arise without it, as he so carefully explained. Still, the spirit of Korzybski's work is admirable.
I think that you misunderstand Chomsky's critique of behaviorism. He did not claim that classical conditioning did not work on rats. Nor did he claim that classical conditioning did not work on humans for some behaviors. What he claimed is that behaviorism was not a complete psychological theory in that it could not explain human linguistic behavior. Behaviorist accounts of human language were based on a grossly oversimplified and inaccurate idea of what human linguistic behavior is like. Essentially, they thought that all you had to do was pair chunks of sound with meanings by classical conditioning. What Chomsky did was show that human language involves much more than simple wordmeaning associations, that behaviorists had not provided anything resembling an account of human language as it actually is, and that it was very unlikely that they could.
Chomsky's review of Skinner's Verbal Behavior was indeed the death knell of behaviorism as a theory of human cognition. It was one of the central events resulting in the development of what we now call cognitive science. Behaviorist psychology survived in some ways for several reasons. First, even if it doesn't explain human language, it does work for a lot of behavior, both of humans and of other organisms. If you were interested in rats, it was still reasonable to study operant conditioning of rats. Second, as a consequence of the first reason, classical conditioning is an effective form of behavior modification for certain types of behavior. Clinical psychologists therefore continue to make use of it. What they try to do is not induce native language acquisition. Third, there is a certain amount of inertia in any field. It takes a while for new ideas to be accepted even if the evidence for them is strong, and even then people working in areas not directly affected often don't find it worthwhile to change what they are doing. (Note, for example, that classical mechanics is not only used in engineering but continues to be taught by physicists even though in a technical sense since the introduction of relativity we know that it isn't right. It's much simpler to use it where it works than to do everything relativistically.)
The failure of Skinner and many other psychologists of the time to recognize the complexity of human language and therefore to believe that their theories could handle it has often been repeated, in psychology and AI. Quite a few linguistically oriented AI projects announced success only for it to turn out that the claims were vastly overblown because they had an inadequate understanding of the problem, which they therefore had not solved. For an entertaining critique of such work see: Norbert Hornstein and B. Elan Dresher (1976) "On Some Supposed Contributions of Artificial Intelligence to the Scientific Study of Language," Cognition 4, pp.32l-398. For a somewhat more recent example, I remember a talk by a proponent of neural nets in the late 1980s who claimed to have a net that "learned English syntax". The reality was that, if fed rather carefully constructed data, the net learned to distinguish transitive verbs from intransitive verbs. There is a lot more than that to "learning English syntax".
No, no, no. You don't need to make it wider. Just twist an end and glue it to the other, making a Moebius tape.
Here are a few reviews from people who did read the book (or at least who claim to have read it, I admit I did not sit down and watch them each read it from cover to cover):
Now I did not go and seek out reviews that were critical of the book, these were just the first 5 I found. In fact most do recommend the book in the end. However, they generally agree his book has a few flaws. Not that his work isn't interesting or that he is clearly wrong in his arguments (though most generally agree that some of his claims are not fully substantiated), but that despite Wolfram's near megalomaniac claims to the contrary, his approach really isn't all that new. Some react to this fact with amusement (like Kurzweil), some with anger (like Shalizi), but regardless it is clearly a valid criticism that Wolfram's work really isn't all that new. Don't claim that the reason people are critical of him is that they are just resisting thinking about things differently.
Mathematics is made of 50 percent formulas, 50 percent proofs, and 50 percent imagination.