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.

Comments

A New Kind of Science

[CRCulver]

I remember the discussion here five years ago when Wolfram released his book A New Kind of Science . Many claimed that it was hogwash and (as it was apparently not peer-reviewed) irresponsible, but at least the movement he has tried to spark is finally showing some results.

Re:A New Kind of Science

[r3m0t]

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.

Re:A New Kind of Science

[UbuntuDupe]

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.)

Re:A New Kind of Science

[nagora]

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.

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

[pohl]

I recall that to, and was curious enough to see if the criticism was summarized well in Wikipedia. (It is.) 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? (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

[cjeris]

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.

Re:A New Kind of Science

[Anonymous Coward]

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)

Re:A New Kind of Science

[Hatta]

But it's worth noting that the Rule 110 proof, while not hogwash, was also not Wolfram's.

Re:A New Kind of Science

[meburke]

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.

Re:A New Kind of Science

[Anonymous Coward]

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.

It (Originally SMP) was also written on Caltech equipment and Caltech sued Wolfram; hence Caltech does not pay for any copy of Mathematica they run.

Re:A New Kind of Science

[SlowMovingTarget]

Well said, Comic Book Guy!

Re:A New Kind of Science

[Hijacked Public]

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?

Re:A New Kind of Science

[Quadraginta]

Boy you're telling me. I remember when Wolfram was the wunderkind of the 1980s and 1990s, who was going to Change The World(TM) with his brilliance. Ha. Jeff Bezos or Linus Torvalds have done far more with computers to Change The World in interesting and useful ways.

Re:A New Kind of Science

[machinelou]

It's probably more common that criticism comes from people who have NOT read the source material than from people who have. And, for reasons I do not completely understand, such criticism tends to be believed.

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:A New Kind of Science

[bmajik]

I'm about 1/4 of the way through the NKS book and I find it absolutely fascinating. It "inspired" me to create some basic 2-color nearest-neighbor automata (you can get through university without studying this sort of thing, btw (!)) and I found the material very approachably written. I'm sure you could cover the material with far fewer pages if you expected the reader to have pencil/paper (or a debugger?), and didn't have so many pretty images, but i thought that the comparison of automata-generated shells to actual aquatic life was the most damning evidence that what wolfram was postulating was fundamentally worth thinking about.

That he may or may not be the first person to suggest anything in his book is not interesting to me; that his book was cheap enough (i got it about a year ago at a bargain table) and accessible enough (it's in my "bathroom reading" shelf) that I'm thinking and learning things I otherwise wouldn't be makes it sufficiently valuable IMO.

Efforts to cast the book as some renegade peice of science that "conventional academia" won't publish are mostly drama. The guy's writing style is a bit dramatic at times (i seem to recall him using the same linking phrase to go from "thing that sounds implausible" to "i think it's actually true" in nearly every section of every chapter.) but that doesn't get in the way of it being a read that makes me think about it for hours after i've put it down.

Re:A New Kind of Science

[Anonymous Coward]

http://www2.fbi.fh-darmstadt.de/~vmi/chronologie/main.htm

1981? Stephen Wolfram develops SMP (Symbolic Manipulation Program) at CalTech. When he licenses it, CalTech asserts ownership. They settle out of court. Wolfram goes on to develop Mathematica.

http://en.wikipedia.org/wiki/Stephen_Wolfram

He led the development of the computer algebra system SMP (Symbolic Manipulation Program: SMP was essentially Version Zero of Mathematica) in the Caltech physics department during 1979-1981, but a dispute with the administration over the intellectual property rights regarding SMP -- patents/copyrights and faculty involvement in commercial ventures -- eventually caused him to resign from Caltech.[4] SMP was further developed and marketed commercially by Inference Corp. of Los Angeles during the period 1983-1988. In 1981, Wolfram was awarded a MacArthur Fellowship. In 1983, he left for the School of Natural Sciences of the Institute for Advanced Study, where he studied cellular automata, mainly with computer simulations.

The settlement aficr was free licenses to Caltech in perpetuity.

Re:A New Kind of Science

[workdeville]

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.

Re:A New Kind of Science

[machinelou]

Off topic but.. You couldn't be more wrong. Lab animals could not be conditioned in the way behaviorism predicted? Really?

First of all, behaviorism and conditioning are not theories in the sense that nobody sat in a chair, came up with stuff off the top of their head, and then tried to prove it. Rather, they were descriptions of the results of experiments THAT HAD ALREADY BEEN CONDUCTED. Hence, reinforcement? Yea, it works. Punishment? You bet. Stimulus discrimination, extinction, schedule effects.. Yea. The descriptions were also somewhat special because they were related to principles that were general enough to span species (humans, rats, mice, pigeons, dogs, birds, sea lions, dolphins, fish, insects) and responses (language, thinking, level pushing, drug abuse/self-administration, 2 and 3-point shots attempted by players on NCAA basketball team, imprinting by birds, self-injury). Basically, it's much harder to list things that animals and people do that can't be described using behavioral principles than things that can.

Second, behavioral approaches have become the de-facto standard in many areas. Functional analysis, a behavioral technique to determine why people engage in behavior, was written into law (IDEA, the individuals with disabilities and education act). Know anyone with a child who has developmental disabilities? Chances are, their child works or has worked with a behavior analyst. And, as you alluded to, behavioral preparations are widely used by neuropsychologists to study the BRAINS of intact organisms (ironic?)!

If anything, it seems like Chomsky's theories have died. I know people who have graduated from linguistics departments only to then become Board Certified Behavior Analysts and practice behavior analysis because its presents very practical way to assess and teach language to children. The only thing I'm confused about is why you (and many, many others) still think the opposite.

Need citations? Google the Journal of Applied Behavior Analysis or the Journal of the Experimental Analysis of Behavior. There are several other good journals, but these are the best and they're available free online.

Re:A New Kind of Science

[belmolis]

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:A New Kind of Science

[nwbvt]

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):

• http://www.kurzweilai.net/articles/art0464.html?printable=1
• http://www.goertzel.org/dynapsyc/2002/WolframReview.htm
• http://www.cscs.umich.edu/~crshalizi/reviews/wolfram/
• http://www.nybooks.com/articles/15762
• http://www.maa.org/reviews/wolfram.html

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.

Turing Machines

[ebolaZaireRules]

I hated this subject... If only my lecturer had told me I could win US$25k, it might have been more interesting.

Re:Turing Machines

[caffeinemessiah]

There's a $1 million prize for proving or disproving P = NP from the Clay Mathematics institute if you're still interested.

Re:Turing Machines

[muellerr1]

N = 1. Solved! I can't believe they weren't able to figure that out.

Re:Turing Machines

[MyLongNickName]

Or P=0. My solution is more complete :)

Damn

[3.5 stripes]

That was on my To Do list for next week.

But...

[Hatta]

...does it run Linux?

Re:But...

[Palshife]

It runs everything.

Re:But...

[johnw]

It runs everything. But it needs a memory upgrade and a new video card to run Vista.

Re:But...

[sapone]

But it needs a memory upgrade and a new video card to run Vista. Well, next time you buy a Turing machine, you should go right for the Aleph brand memory tape. Plain old infinity obviously doesn't cut it.

Re:But...

[Anonymous Coward]

But it needs a memory upgrade and a new video card to run Vista.

Huh... I go through the trouble of finding a new card and an infinite tape that's twice as long, and the damn thing still displays the same three colors as before the upgrade.

Re:But...

[Lord Bitman]

Infinite tape that's twice as long is logically impossible. Clearly to double the memory you need to make it twice as wide

Re:But...

[b4stard]

here you go

Re:But...

[Bazman]

Was it Turing or Bill Gates who said that an infinitely long tape ought to be enough for anyone?

Re:But...

[Anonymous Coward]

It always comes down to length versus girth for those people....

Re:But...

[Chemisor]

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.

Re:Wow

[russ1337]

Fine, he's a math geek. An ubergeek even. $10 says he hasn't, and never will, get laid

The dude has $25K to spend on a very attractive hookers. I'm sure he's doing the math to figure out whether he's better off blowing it all on one, or getting 2,500 ten-dollar hookers.

Yes the 'blowing it' pun was intended...

2,3. 2+3=5

[ettlz]

The Law of Fives is never wrong.

Re:2,3. 2+3=5

[insertwackynamehere]

The man fnord makes fnord a good fnord point.

Re:2,3. 2+3=5

[Guppy]

"The man makes a good point." -- how the heck does a simple me-too comment like this get modded up? I find this rather upsetting, somehow.

Without even reading the article

[Tibor the Hun]

Without even reading the article, I feel confident to say that, no it does not. All that universal applications allow you to do is run them on both PPC and Intel chips, as opposed to having 2 separate forks for each platform.

(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:Without even reading the article

[Anonymous Coward]

(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.) I work next to a waste treatment plant you insensitive clod!

Science is forever

[Weaselmancer]

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.

Again, really? Yes, really

[arsheive]

I for one now admit that all previously welcomed overlords can be emulated by this 2 state, 3 color overlord.

Re:Wow

[grumpyman]

The dude has $25K to spend on a very attractive hookers. I'm sure he's doing the math to figure out whether he's better off blowing it all on one, or getting 2,500 ten-dollar hookers.

Yes, but that'll take the 2,3 turing machine 37 billion steps before he can get the answer.

Slashdotted..

[Seismologist]

The wolfram site is slashdotted but this link for the article in nature is not.

Re:Wow

[fotbr]

Have you seen the exchange rate lately? He better spend it soon, or that $25k isn't going to buy him much in the way of hookers.

if you like this...

[kisrael]

yeah, I know I'm pimping my own site, sosumi...
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/ 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...

Uhh, what?

[Webz]

Could anyone take a stab at explaining what this discovery actually means, in layman's terms? What is the significance of a univeral turing machine? What if the turing machine wasn't universal?

What's the significance of 2,3? (Bit states, color?)

What did this discovery actually teach us? How is it useful?

Re:Uhh, what?

[spikenerd]

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.

Re:Uhh, what?

[hansraj]

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.

Re:Uhh, what?

[johnnyb]

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.

Re:Uhh, what?

[Budenny]

"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.

Re:Uhh, what?

[Eponymous Bastard]

Became depressed because of:
- 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:An Undergrad?

[stranger_to_himself]

I am. Not because I don't think they're capable, but when I was an undergrad we just learned things and then repeated them. It took me a long time to believe I could contribute anything meaningful to my subject. I also think it's notable that he was a computer science undergrad, and not reading mathematics. We need to encourage undergrads in math to think more, then maybe we'll see more of this kind of thing.

Re:The paper

[Alexpkeaton1010]

Cut him some slack. Undergraduate Engineering students do not normally publish many papers. I'm sure the official published journal version will be cleaned up. Very impressive for a 20 year old!

Automat size

[ledvinap]

Can anyone estimate how long tape is needed to do some real-world computation? Like adding/multiplying two (n-bit) integers?

Re:An Undergrad?

[nate nice]

Yes and no.

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.

It's in the linked article

[jgoemat]

Universal Turing Machines are "[...] extremely basic abstract symbol-manipulating devices which, despite their simplicity, can be adapted to simulate the logic of any computer that could possibly be constructed."

From the article:

Here it is. Just two states and three colors. And able to do any computation that can be done.
[...]
There were some simpler universal Turing machines constructed in the mid-1900s--the record being a 7-state, 4-color machine from 1962.

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.

Re:It's in the linked article

[Relic of the Future]

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.

Needs an infinite tape

[Tim2]

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.

Re:Needs an infinite tape

[wiredog]

No problem. I'll use a Moebius strip.

Re:WTF

[Bloodoflethe]

.42

Great Result - Great Inspiration

[BoRegardless]

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.

Question for Turing Geeks.

[mightybaldking]

At the wolfram site, he shows the rules for this 2,3 machine (two state, three color).
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},
{u, b} -> {c, b, R},
{d, b} -> {c, b, L}
}

Are these equivalent?

Re:Question for Turing Geeks.

[Iwanowitch]

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.

Other simple universal machines

[ortholattice]

I had thought that the Game of Life was one of the simplest possible, although someone else will have to clarify how it compares. I think Life was proved universal a number of years ago, and an actual implementation is here: Life Universal Computer.

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 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.

I have discovered a truly wonderful proof...

[Anonymous Coward]

of this, but it doesn't pass the /. lameness filter ;^)

Re:Wow

[Jedi_Yo_Jo]

he could retire in mexico with 25K

Re:a 40-page proof for a "simple machine"?

[Ant P.]

unsigned int x,y,z,n;
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.

A flaw in the argument:no *HALT*:resubmit for $25k

[viking80]

The original Universal Turing machine was defined to end with the *HALT* instruction. The 2,3 Turing Machine can not halt, and is therefore not universal. It appears that Wolfram conceded that computers today dont really halt, they just keep ticking after the program is complete, so they accepted the 2,3 machine as universal, and the proof as completed.

Maybe someone should submit the same proof, concluding that it is *not* a universal Turing machine, and claim the $25k.

Re:Science is forever .. right angles

[Weaselmancer]

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.

Not What It Seems?

[Jane Q. Public]

TFA (the first link) claimed that this was a proof of the "simplest" Turing machine. However, as I understand what was written, and without reading the whole proof, it appears that this is not actually the case. What he proved was that his chosen candidate Turing machine, among "2,985,984 possible 2,3 machines", was universal. That does not mean that his machine is the simplest possible, only that it is among the simplest known CATEGORY of such machines (2,3). There may well be some kind of example of one that is, in a significant way, simpler.