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.
Comment removed (Score:3, Interesting)
Re: (Score:3, Informative)
Nor is this 2,3 machine going to revolutionise science.
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:5, Funny)
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.
Re: (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 versi
Re:A New Kind of Science (Score:5, Informative)
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".
Re: (Score:2)
What I find so hilarious is that it already exists in biological systems, I really think if we want to go to the next level we really have to get our minds around what already exists and use that as a base, since so many things are already figured out we just don't understand them.
Re: (Score:3, Informative)
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
Re:A New Kind of Science (Score:5, Insightful)
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, Informative)
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:A New Kind of Science (Score:5, Informative)
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/ [umich.edu]
The above link is worthwhile, entertaining, and should help bring back anyone who drank the Wolfram Kool-Aid.
(go blue)
Re: (Score:2, Interesting)
Re:A New Kind of Science (Score:5, Informative)
Re: (Score:3, Interesting)
Re:A New Kind of Science (Score:5, Interesting)
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?
Turing Machines (Score:3, Funny)
Re:Turing Machines (Score:5, Informative)
Re:Turing Machines (Score:5, Funny)
Re:Turing Machines (Score:4, Insightful)
Re: (Score:2)
Damn (Score:5, Funny)
But... (Score:5, Funny)
Re:But... (Score:5, Funny)
Re:But... (Score:5, Funny)
Re:But... (Score:5, Funny)
Re:But... (Score:4, Funny)
Re: (Score:3, Funny)
Re: (Score:2)
Re:But... (Score:5, Funny)
Re: (Score:2, Informative)
Re: (Score:2, Funny)
Re: (Score:3, Informative)
Re: (Score:2)
Re: (Score:2)
Re: (Score:2)
Re: (Score:2)
And STOP CALLING ME SHIRLEY!
Re: (Score:2)
Re: (Score:2)
Maybe, but only a limited version at best. Do not forget that one of the assumptions for a Turing machine is infinite memory space; AFAIK the largest memory space Linux currently runs in has 2^64 memory locations. As such Linux doesn't run all the programs a theoretical Turing machine runs.
Without even reading the article (Score:4, Funny)
(If anyone bothers to take this seriously, and feel they need to correct me, they need to step outside for a while and get some fresh air.)
Re: (Score:2, Funny)
2,3. 2+3=5 (Score:4, Funny)
Re:2,3. 2+3=5 (Score:4, Funny)
Re:2,3. 2+3=5 (Score:5, Funny)
Again, really? Yes, really (Score:5, Funny)
Slashdotted.. (Score:5, Informative)
if you like this... (Score:5, Interesting)
Anyway, I was thinking about 1D CA the other week, and realized one of the attractions was that you plot time and make it 2D... but there's no particular reason you can't do the same thing to a 2D CA, like Life...
http://kisrael.com/2007/10/21/ [kisrael.com] is the result, ethereal blue sculptures made by plotting 2D Life with Time as a physical dimension.
I'm not sure if I learned a lot or proved anything, but it *is* pretty...
Re: (Score:2)
http://kisrael.com/2007/10/26 [kisrael.com] is Conway West, where you get to play a little happy face trapped in Conway's Game of Life, with a ghost farting out random particles to add a random element the patterns. Dodge the Life cells and go for points! (made for http://glorioustrainwrecks.com/ [glorioustrainwrecks.com] Klik-of-the-Month 2 hour game jam)
Re: (Score:2)
Re: (Score:2)
Re: (Score:2)
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:Uhh, what? (Score:5, Informative)
Re:Uhh, what? (Score:5, Informative)
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.
Re:Uhh, what? (Score:4, Interesting)
- Estrogen treatment: gained weight, physical changes, possibly psychological changes too.
- Lost his security clearance so couldn't work on any of the crypto/high security work he did. (spies usually tried to subvert homosexual and/or prosecuted people who were dissatisfied with their government). Half of that work couldn't be published either which left him in a bad position as an academic.
- "most of the scientific community shunned his work due to some personal habits." as the GP said. Guess which habits this means
Probably caused a lot of rifts in his personal life too.
BTW, the inspiration for Apple computers' logo was actually Newton's apple. Older logos have a picture of Newton sitting under a tree with a glowing apple above him. It is unknown how much Turing influenced it. People often mention the rainbow apple in this regard.
Re: (Score:3, Informative)
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 numbe
It's in the linked article (Score:5, Informative)
From the article [wolfram.com]:
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.
Molecular TM is nonsense (Score:2)
Re:It's in the linked article (Score:5, Informative)
Re:Uhh, what? (Score:5, Informative)
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.
Re: (Score:2)
I may have to correct the phrasing of a previous post...
Does this mean... (Score:2)
Automat size (Score:2, Interesting)
Re: (Score:2)
Usually no consideration is paid to how efficiently a Turing Machine works, as long as it is finite. There is no optimization that goes into the Machine to solve real-world problems, only proof that they could be solved. In your example a plausible answer for the amount of tape necessary could range
Needs an infinite tape (Score:5, Funny)
The universal Turing machine itself consists of a large but quite finite set of quadruples. The problem is the longish tape.
Re: (Score:3, Funny)
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.
NKS (Score:2)
Yes! (Score:2)
Question for Turing Geeks. (Score:2, Interesting)
The two states being up and down, and the colors being white, yellow and orange.
Is there an equivalent 3,2 machine - {up, down, charm} and {white, black}?
His machine:
{S,C) -> {S,C,O}
{
{D, O} -> {D, Y, L},
{D, Y} -> {D, O, L},
{D, W} -> {U, Y, R},
{U, O} -> {D, W, R},
{U, Y} -> {U, O, R},
{U, W} -> {D, O, L}
}
3,2 machine
{
{c, w} -> {u, w, L},
{u, w} -> {c, w, L},
{d, w} -> {u, b, R},
{c, b} -> {d, w, R
I have discovered a truly wonderful proof... (Score:3, Funny)
Re: (Score:3, Informative)
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
a 40-page proof for a "simple machine"? (Score:2)
Re: (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.
Obvious replies (Score:2)
Imagine a Beowulf cluster of these.
But will it run Linux?
In Soviet Russia, universal are turning machines.
Re: (Score:2)
But will it blend?
Yes, but you'll need an infinitely large blender to blend the infinitely long tape.
Imagine a Beowulf cluster of these.
Impossible. Following the Wikipedia article [wikipedia.org] on Beowulf clusters: "It does not contain any custom hardware components and is trivially reproducible." The entire machine (not including the infamous infinite tape) is a custom hardware component. You could make a cluster of these, though. It just wouldn't be a Beowulf cluster.
One question to think about, though: Since Beowulf clusters are predominately open-source dri
Other simple universal machines (Score:3, Interesting)
There are also universal machines possible with S-K combinators, which in a sense is also one of the simplest if not the simplest, with only two possible commands: S and K. (I guess it depends on how simplicity is measured.) Amazingly, the shortest universal machine [slashdot.org] found so far with SK combinators has 272 bits, compared to 5495 bits for Roger Penrose's universal Turning machine built from the original Turing machine and 268,096 cells for the Life version.
I couldn't quite glean the size of a universal machine implemented with Wolfram's 2,3 cellular automaton, but I would imagine it would be very large.
Good news... (Score:2)
So, this is apparently a 2 bit machine, with each bit representing 3 states. That's 9 possible states total.
If this is correct, then I - or any other hobbyist - should be able to build this Turing machine with a few flip flops and LEDs. And supposedly, could use such a machine to emulate any other computer. What I'm wondering, though, is how practical such a machine would be.
A flaw in the argument:no *HALT*:resubmit for $25k (Score:4, Interesting)
Maybe someone should submit the same proof, concluding that it is *not* a universal Turing machine, and claim the $25k.
Not What It Seems? (Score:3, Interesting)
with an attitude like that (Score:2)
Re:Wow (Score:5, Funny)
Yes the 'blowing it' pun was intended...
Re: (Score:3, Funny)
Yes, but that'll take the 2,3 turing machine 37 billion steps before he can get the answer.
Re:Wow (Score:4, Insightful)
Re: (Score:2)
Domestic good-old American hookers should not be affected.
Re: (Score:2)
Re: (Score:2)
Although at least with $25k (which is what, 100 Euro these days?) he might be able to move out of his mom's basement.
Actually, he probably can't (at least not with that amount); it's only just over £12,000 [google.com], and the average house price in Birmingham is almost £160,000 [bbc.co.uk]. The amount he won probably wouldn't even cover the deposit for his own property.
Re: (Score:2, Funny)
Re: (Score:2)
Oh well.
Science is forever (Score:3, Interesting)
That all depends on your definition of accomplishment, now doesn't it.
Yes it does, but that runs both ways.
A scientific proof is something that gets to contribute to society forever. Your examples only help for a lifetime. Look around the room you're in and see how many examples of Pythagoras' theorem you can find.
Dead and buried 2500 years, and he's still contributing to our society. Even makes Mother Theresa look a little weak, IMO.
Re: (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
Re:An Undergrad? (Score:4, Interesting)
Re: (Score:2)
He was not. He was an ECE undergrad. They state it in the article. Which makes it even more impressive - this is an accomplishment that doesn't even really go along with his field.
Re: (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-Comp
Re: (Score:2)
Re: (Score:3, Funny)
Re: (Score:2)
Yes [wikipedia.org].
Re: (Score:2, Insightful)