Beta
×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

Wolfram's 2,3 Turing Machine Is Universal!

CmdrTaco posted more than 6 years ago | from the theory-flashbacks dept.

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

cancel ×

288 comments

Sorry! There are no comments related to the filter you selected.

A New Kind of Science (3, Interesting)

CRCulver (715279) | more than 6 years ago | (#21100283)

I remember the discussion here five years ago when Wolfram released his book A New Kind of Science [amazon.com] . 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 (3, Informative)

r3m0t (626466) | more than 6 years ago | (#21100361)

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 (4, Insightful)

nagora (177841) | more than 6 years ago | (#21100501)

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 (1, Funny)

Anonymous Coward | more than 6 years ago | (#21101029)

I fail to see the connection between Wolfram's speculation that there will turn out to be very simple universal Turing machines and your banal statement that some countries in the world will go to war. Ergo, the fact that you're not impressed by the proven truth of the former does not, of itself, make it unimpressive.

That doesn't make his huge book any less tedious, however.

Re:A New Kind of Science (5, Funny)

SlowMovingTarget (550823) | more than 6 years ago | (#21101303)

Well said, Comic Book Guy!

Re:A New Kind of Science (5, Insightful)

meburke (736645) | more than 6 years ago | (#21101055)

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 (1)

Troed (102527) | more than 6 years ago | (#21101879)

imagine concrete with the intelligence to repair itself

I found the Stephen Baxter Destiny's Children series to contain a few of these in reality very obvious-but-not-obvious technology descriptions. I think it is in book 3 an intelligent house paint is described.

Re:A New Kind of Science (4, Insightful)

Quadraginta (902985) | more than 6 years ago | (#21101689)

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 (-1, Offtopic)

DevStar (943486) | more than 6 years ago | (#21100383)

Wolfram vs Slashdot. No offense, but most people on Slashdot have very little technical skill (relative to those who are technically skilled :-)), whereas Wolfram has shown strong technical skill many times. Slashdot is good for seeing good flame wars, but no one really expects any deep technical or scientific postings on here.

Re:A New Kind of Science (5, Informative)

cjeris (29514) | more than 6 years ago | (#21100527)

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 [ams.org] and this collection of many more links to reviews [usf.edu] .

Re:A New Kind of Science (5, Interesting)

Hijacked Public (999535) | more than 6 years ago | (#21101349)

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 (5, Insightful)

UbuntuDupe (970646) | more than 6 years ago | (#21100427)

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 (5, Informative)

Hatta (162192) | more than 6 years ago | (#21100869)

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

Re:A New Kind of Science (4, Insightful)

pohl (872) | more than 6 years ago | (#21100503)

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 (5, Informative)

Anonymous Coward | more than 6 years ago | (#21100847)

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/ [umich.edu]

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 (2, Interesting)

Anonymous Coward | more than 6 years ago | (#21101095)

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 (0)

Anonymous Coward | more than 6 years ago | (#21101389)

Rubbish. Caltech, like most universities has a site license of Mathematica

Re:A New Kind of Science (0)

Anonymous Coward | more than 6 years ago | (#21101927)

Rubbish. Caltech, like most universities has a site license of Mathematica
How much did they pay for it?

Re:A New Kind of Science (0)

Anonymous Coward | more than 6 years ago | (#21101087)

It still is hogwash, and the problem was not that it was not peer-reviewed but that it completely ignored other related work.

Turing Machines (3, Funny)

ebolaZaireRules (987875) | more than 6 years ago | (#21100331)

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 (4, Informative)

caffeinemessiah (918089) | more than 6 years ago | (#21101045)

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

Re:Turing Machines (5, Funny)

muellerr1 (868578) | more than 6 years ago | (#21101211)

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

Re:Turing Machines (3, Insightful)

MyLongNickName (822545) | more than 6 years ago | (#21101501)

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

Re:Turing Machines (0)

Anonymous Coward | more than 6 years ago | (#21101845)

I can't believe is they demonstrated bitranslateral interference with a Shiner matrix value of .01 inside the Vurner-Chroaski limit. The Chi bipolar inhibitor of the Turing Machine nearly has the same overall covalence as Dr. Brown's flux capacitor!!!

This of course proves that blue is red, and the sky is the ground, and mathematicians have much too much fun labeling bizarre, esoteric things.

Re:Turing Machines (1)

TheRaven64 (641858) | more than 6 years ago | (#21101213)

I'm amazed the prize took so long for someone to win (although I wasn't aware the prize existed, and so perhaps it wasn't well publicised). Proving random things are Turing complete is typical first-year coursework for a computer science degree. Generally, the way of doing it is to implement an emulator for something else that is already known to be universal on it. Looking at the 2,3 machine, it looks like this would take a while but not be particularly difficult (the fact that the proof turned out to be 40 pages indicates that a while might be a long while).

Wow (0, Offtopic)

Quaoar (614366) | more than 6 years ago | (#21100339)

This kid has just accomplished more than most of us can hope to accomplish in our entire lives.

Re:Wow (-1, Flamebait)

fotbr (855184) | more than 6 years ago | (#21100553)

Fine, he's a math geek. An ubergeek even.

$10 says he hasn't, and never will, get laid. Although at least with $25k (which is what, 100 Euro these days?) he might be able to move out of his mom's basement.

Re:Wow (5, Funny)

russ1337 (938915) | more than 6 years ago | (#21100619)

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

Re:Wow (2, Funny)

grumpyman (849537) | more than 6 years ago | (#21100967)

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.

Re:Wow (3, Insightful)

fotbr (855184) | more than 6 years ago | (#21101049)

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.

Re:Wow (0)

Anonymous Coward | more than 6 years ago | (#21101603)

Get a professorship
get tenure
get a grad student
get laid

Re:Wow (0)

Anonymous Coward | more than 6 years ago | (#21101047)

Is that your way of compensating so you don't feel worthless? Can't you just be happy for the guy?

Re:Wow (-1, Offtopic)

russ1337 (938915) | more than 6 years ago | (#21100563)

This kid has just accomplished more than most of us can hope to accomplish in our entire lives.

Tell me about it. This guy is 20. I was lucky if I could put two lego bricks together back then.

with an attitude like that (1)

Shivetya (243324) | more than 6 years ago | (#21100605)

you would be right. Why do people defeat themselves before ever trying?

Re:Wow (-1, Troll)

Zorbane (1095631) | more than 6 years ago | (#21100611)

That all depends on your definition of accomplishment, now doesn't it. Good for him, not trying to dim his glory, but who accomplished more......him, or a person who made sacrifices and gave their life to charity work.....or the person who was just content to be a good worker, good spouse, and/or good parent? Most people worthy of admiring never see the front page of a newspaper.....or even a headline on /.

Science is forever (2, Interesting)

Weaselmancer (533834) | more than 6 years ago | (#21100791)

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:Science is forever (0)

Anonymous Coward | more than 6 years ago | (#21101785)

Actually no one knows that Pythagoras even existed. There's actually a saying that there's as much evidence of Pythagoras than there's of Prometheus, but your point is clear, just wanted to out that Pythagoras might not be the best example. ;)

Re:Wow (1)

realthing02 (1084767) | more than 6 years ago | (#21100851)

And that all depends on who you feel is "worthy" or not.

I don't understand the point of your statement. It's almost as if you were becoming defensive at the fact you (as the GP put it) would never accomplish something like this in your entire life. Maybe you have, but the comment was off topic and made little to no argument whatsoever. Sorry if this seems trollish, it just bugs me that your post had no point to it.

Lastly, there is a problem when someone is content being 'good' enough. I want to be the best at what I do, I am not, I guarantee that, but if I ever feel like I'm good enough, than there is a real problem.

A truer answer (0)

Anonymous Coward | more than 6 years ago | (#21101015)

But bottom line: everything dies. Pythagoras, Wolfram, me, you, the parent poster, everyone who is content to be 'good enough,' and all the masses that have been so wonderfully 'helped' by all the discoveries of the past. So, really, pretty soon none of us are going to have to worry about this argument of constitutes 'being accomplished' because we're all going to die at some point, right? Be the best at what you do if that's fun, but if you aren't, at you won't have to live with that failure forever!

Re:Wow (0, Redundant)

Zorbane (1095631) | more than 6 years ago | (#21101243)

You're right, it does seem trollish....and you must not understand the point of the comment....nor the use of the word good in the context in which it was used. It is not about being defensive, but about the seeming constricting of the definition of accomplishment to something merely material/scientific...that is what bugs me. And I fail to see why "argument" would be necessary since all that was asked was who could be said to accomplish more. For some reason, in the second part of your post, you take the use of good and seem to twist it into a bit of a straw man for some good ole sniping commentary. I was speaking of motivation, not ambition. A hacker (the type that wears black clothes and sport a handlebar mustache) may want to be the best in terms of ambition, but one would generally find his motivation lacking in the "good" department.

Re:Wow (1)

realthing02 (1084767) | more than 6 years ago | (#21101363)

If this is your defense, than you are almost willfully ignorant of what the GP meant by "Accomplish". That is, to do something that could potentially affect many lives. Yes, being a good husband, good father, good etc etc is virtuous, but that doesn't mean it is an accomplishment in the same vein that the GP is intending the word to be used.

Had the GP said done more than, or is more important, than i can see issue being taken. but he almost absolutely meant accomplished in the "touches many people" sense.

Re:Wow (0)

Anonymous Coward | more than 6 years ago | (#21101027)

Awards are for extraordinary (extra-ordinary meaning above the ordinary) work.. not ordinary work. We do not give awards for doing what you were supposed to do anyway. Award for not mugging people on the street? Award for not raping the girl in the parking lot? Give me a break. This is a sad commentary on society when people who simply do what is expected are entitled to awards and the people who fail to pull their weight are considered average rather than deserving of punishment. Accomplishments of science of use to all mankind are far and away more valuable, and more deserving of reward, then some charity worker or parent who helps individuals.

Re:Wow (-1, Troll)

Anonymous Coward | more than 6 years ago | (#21101169)

He's probably a fag. Turing was a homo. My bet is this guy is too. Stands to reason. Q.E.D.

Damn (5, Funny)

3.5 stripes (578410) | more than 6 years ago | (#21100345)

That was on my To Do list for next week.

CmrdTacocks (-1, Troll)

Anonymous Coward | more than 6 years ago | (#21100359)

Yes, he loves cocks.

PS: The new discussion system is unpleasant.

But... (5, Funny)

Hatta (162192) | more than 6 years ago | (#21100429)

...does it run Linux?

Re:But... (5, Funny)

Palshife (60519) | more than 6 years ago | (#21100469)

It runs everything.

Re:But... (5, Funny)

johnw (3725) | more than 6 years ago | (#21100641)

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

Re:But... (5, Funny)

sapone (152094) | more than 6 years ago | (#21100891)

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... (3, Funny)

Anonymous Coward | more than 6 years ago | (#21100913)

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

iabervon (1971) | more than 6 years ago | (#21101271)

An infinite tape that's twice as long isn't any bigger. You need a continuous tape. Or if you prefer, you can get a tape that has a position for each possible state of the entirety of a regular infinite tape, although those tend to get torn too easily.

Re:But... (5, Funny)

Lord Bitman (95493) | more than 6 years ago | (#21101585)

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... (2, Informative)

b4stard (893180) | more than 6 years ago | (#21101823)

here you go [wikipedia.org]

Re:But... (0, Redundant)

ledvinap (412654) | more than 6 years ago | (#21101291)

In fact such upgrade may be impossible. The universe probably does not contain enough matter for such memory/tape...

Re:But... (1)

eclectro (227083) | more than 6 years ago | (#21101887)

It runs everything.
The real problem is not compatibility. The problem is that when the machine goes to 65536+1 position on the tape, one of the colors turns to blue and the machine halts.

Re:But... (1)

johnw (3725) | more than 6 years ago | (#21100505)

...does it run Linux?
Surely what he's proved is that it does?

Re:But... (1)

Mark_in_Brazil (537925) | more than 6 years ago | (#21100693)

...does it run Linux?
Surely what he's proved is that it does?
Yes, in some sense at least. FTFA:

This result ends a half-century quest to find the simplest universal Turing machine.

It demonstrates that a remarkably simple system can perform any computation that can be done by any computer.

And STOP CALLING ME SHIRLEY!

Re:But... (1)

UbuntuDupe (970646) | more than 6 years ago | (#21100511)

Well Linux definitely runs it. ;-)

Oblig (1, Funny)

Anonymous Coward | more than 6 years ago | (#21101137)

... in Soviet Russia at least.

Re:But... (1)

ultranova (717540) | more than 6 years ago | (#21101327)

Well Linux definitely runs it. ;-)

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 (3, Funny)

Tibor the Hun (143056) | more than 6 years ago | (#21100645)

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

WTF (1, Funny)

Anonymous Coward | more than 6 years ago | (#21100475)

I just finished compiling Wolfram's 2,2 Universal Turing Machine!

Re:WTF (0)

Anonymous Coward | more than 6 years ago | (#21100855)

Wolfram runs Gentoo?

So that's why NKS took so long to finish.

Re:WTF (1)

MindKata (957167) | more than 6 years ago | (#21101185)

I just finished compiling a Wolfram's 2,2 Universal Turing Machine as well, but it just flashes a light on and off. I think I'll call it the Wolfram flip flop. So I guess that means the answer to life is somewhere between 0 and 1 ?

Re:WTF (3, Funny)

Bloodoflethe (1058166) | more than 6 years ago | (#21101905)

.42

Nanotechnology implication (0)

Anonymous Coward | more than 6 years ago | (#21100483)

The question is important, for all the reasons that Wolfram states. The proof is remarkably short, driving straight to the point. The implications for Nanotechnology are particularly significant. Wolfram's involvement in the Artificial Life conferences, and the International Conferences on Complex Systems (the 7th one runs 28 Oct-2 Nov 2007) have definitely paid off. By itself, this is probably not enough for a Fields Medal or Macarthur Fellowship, but this young man is someone to keep an eye on. Bravo!

-- Prof. Jonathan Vos Post

Re:Nanotechnology implication (-1, Troll)

Anonymous Coward | more than 6 years ago | (#21100709)

I have a question about the proof. Have you ever been with a woman?

Imagine... (-1, Redundant)

untree (851145) | more than 6 years ago | (#21100513)

Imagine a Beowulf clust--- :sigh: I lost motivation halfway through the obligatory comment.

so is my Room of Monkeys... (0)

Anonymous Coward | more than 6 years ago | (#21100541)

typing out those 1's and 0's

2,3. 2+3=5 (3, Funny)

ettlz (639203) | more than 6 years ago | (#21100629)

The Law of Fives is never wrong.

Re:2,3. 2+3=5 (3, Funny)

insertwackynamehere (891357) | more than 6 years ago | (#21100811)

The man fnord makes fnord a good fnord point.

If this computer can do everything... (-1, Flamebait)

jackpot777 (1159971) | more than 6 years ago | (#21100639)

...and it's so simple, just think of the metaphysical implications. Something as complex as an eye or a brain could be created with such limited initial parametes. No, never mind that: this thing can run Windows WITHOUT the major security flaws!

You know what? Just mark me as Flamebait on this one.

Sorry.

Re:If this computer can do everything... (-1, Troll)

Anonymous Coward | more than 6 years ago | (#21100663)

how about we mod you a boorish and boring? that suits the situation better.

Re:If this computer can do everything... (1)

tsjaikdus (940791) | more than 6 years ago | (#21101255)

> Something as complex as an eye or a brain could be created with such limited initial parametes
.
I doubt that to be true, because Wolfram writes:
.
> And in Alex Smith's construction the Turing machine "tape" (i.e., memory) must be filled with an infinite pattern of bits.
.
So, infinite is not so limited. The key point in the story (as far as I understand) is that this pattern can be created without the need for a universal computer. But that doesn't mean that you'll only need a few parameters to start with.

Not So Fast (0)

Anonymous Coward | more than 6 years ago | (#21100685)


The establishment of the correctness of proof requires more than a Mathematica infomercial.

Cheers,
Kilgore Trout, Ph.D.

woah (-1, Offtopic)

ilovegeorgebush (923173) | more than 6 years ago | (#21100695)

Clever bastard!

correction (0, Troll)

jovius (974690) | more than 6 years ago | (#21100701)

Universal is not Wolfram's 2,3 Turing Machine but a media conglomerate.

Again, really? Yes, really (5, Funny)

arsheive (609065) | more than 6 years ago | (#21100883)

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

An Undergrad? (2)

holmedog (1130941) | more than 6 years ago | (#21100955)

Isn't anyone else simply amazed that this was proven by an undergrad?

Re:An Undergrad? (3, Interesting)

stranger_to_himself (1132241) | more than 6 years ago | (#21101173)

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:An Undergrad? (1)

holmedog (1130941) | more than 6 years ago | (#21101521)

Same goes for me, that is half the reason why I was surprised. As a computer sci undergrad, we didn't really have any opportunity to try and expand on what we were learning. Most of the time we were too busy trying to re-invent the wheel (such as in Compiler Construction when we tried to re-create directive driven languages).

Re:An Undergrad? (0)

Anonymous Coward | more than 6 years ago | (#21101293)

This is a subject where you don't need any heavy machinery to prove results. Same goes to e.g. proving that algorithms are NP-complete where you just have to come up with some elaborate construction and some interesting trick. These are the subjects where smart undergrads are usually employed by universities to do research, because they can. You won't see undergrads getting any interesting results in subjects like algebraic geometry which requires lots of technical background which is why math undergrads usually tweak concrete algorithms or do something related to combinatorics in their research.

Re:An Undergrad? (2, Insightful)

nate nice (672391) | more than 6 years ago | (#21101783)

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.

Slashdotted.. (5, Informative)

Seismologist (617169) | more than 6 years ago | (#21100973)

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

The paper (0)

Anonymous Coward | more than 6 years ago | (#21101129)

The result might be interesting, but I've never seen a paper looking as horrible as this one. Is this guy using word and has he ever heard of splitting text into sections or how to use captions? This thing brings to mind papers in social sciences where the author has come up with the great idea of presenting an argument with predicate logic (they never know how to write math and I've suffered reading a few (my wife is a prof. in social sciences...)).

Re:The paper (2, Insightful)

Alexpkeaton1010 (1101915) | more than 6 years ago | (#21101245)

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!

if you like this... (4, Interesting)

kisrael (134664) | more than 6 years ago | (#21101131)

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/ [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:if you like this... (1)

kisrael (134664) | more than 6 years ago | (#21101241)

Also (and this is all stuff I happened to do on Saturday, which is why it's on my mind)

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:if you like this... (1)

geminidomino (614729) | more than 6 years ago | (#21101809)

http://kisrael.com/2007/10/26 [kisrael.com] is Conway West
Ain't he that rapper who thinks he should be in the bible?

Uhh, what? (3, Insightful)

Webz (210489) | more than 6 years ago | (#21101143)

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? (5, Informative)

spikenerd (642677) | more than 6 years ago | (#21101705)

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? (3, Informative)

hansraj (458504) | more than 6 years ago | (#21101765)

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 [wikipedia.org] 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.

It's in the linked article (4, Informative)

jgoemat (565882) | more than 6 years ago | (#21101795)

Universal Turing Machines [wikipedia.org] 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 [wolfram.com] :

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.

Molecular TM is nonsense (1)

Ed Avis (5917) | more than 6 years ago | (#21101935)

Wolfram's hype about molecular computers is hogwash. Yes, any molecular computer would need to be simple and follow simple rules like a Turing machine. But there's no way you'd actually build one using the Turing machine structure, moving left and right along a linear tape. The simplest algorithms taking linear time on an ordinary general-purpose computer can take quadratic time or worse when implemented on a one-dimensional Turing machine. A TM is a universal computer in that it can imitate any other, but that doesn't say anything about how long it will take to do so. Any finite number of steps is fine, no matter how slow. A TM is a thought experiment, not a device for practical computing.

If you really built a molecular device you'd surely build a machine for a specific application, rather than making a general-purpose programmable molecule and then feeding it an input program laboriously written out on an N-colour tape.

That said, this is a nifty theoretical achievement - finding arguably the simplest universal computer possible - and who knows, perhaps the small definition of this TM will allow others to prove further things about computation in general.

Does this mean... (1)

Cycline3 (678496) | more than 6 years ago | (#21101229)

Does this mean it runs native on the new Intel based Macs? :)

#irc.7Rolltalk.com (-1, Offtopic)

Anonymous Coward | more than 6 years ago | (#21101361)

errorsC. Future I come here but now developers it simple,

Automat size (2, Interesting)

ledvinap (412654) | more than 6 years ago | (#21101415)

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

Obligatory: (-1, Redundant)

dpbsmith (263124) | more than 6 years ago | (#21101495)

Imagine a Beowulf cluster of these!

Needs an infinite tape (5, Funny)

Tim2 (151713) | more than 6 years ago | (#21101861)

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.
Load More Comments
Slashdot Login

Need an Account?

Forgot your password?

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>