Slashdot Mirror
Wolfram's 2,3 Turing Machine Is Universal!
Rik702 writes "Wolframscience.com have announced that an undergraduate from Birmingham, UK has proved Wolfram's 2,3 Turing Machine is universal." You can read a pdf of the proof as well as some related coverage.
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.
I hated this subject... If only my lecturer had told me I could win US$25k, it might have been more interesting.
The Bible: Historically verifiable fact from an observers point of view
This kid has just accomplished more than most of us can hope to accomplish in our entire lives.
I'll form my OWN solar system! With blackjack! And hookers!
That was on my To Do list for next week.
He tried to kill me with a forklift!
...does it run Linux?
Give me Classic Slashdot or give me death!
I just finished compiling Wolfram's 2,2 Universal Turing Machine!
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
typing out those 1's and 0's
you would be right. Why do people defeat themselves before ever trying?
* Winners compare their achievements to their goals, losers compare theirs to that of others.
The Law of Fives is never wrong.
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.)
If you don't know what AltaVista is (was), get off my lawn.
The establishment of the correctness of proof requires more than a Mathematica infomercial.
Cheers,
Kilgore Trout, Ph.D.
Universal is not Wolfram's 2,3 Turing Machine but a media conglomerate.
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.
Weaselmancer
rediculous.
I for one now admit that all previously welcomed overlords can be emulated by this 2 state, 3 color overlord.
@AlexSheive
Isn't anyone else simply amazed that this was proven by an undergrad?
The wolfram site is slashdotted but this link for the article in nature is not.
~ In Trust, We Trust ~
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!
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...)).
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...
SO YOU'RE GOING TO DIE: The Comic for Dealing with Death
... in Soviet Russia at least.
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?
Does this mean it runs native on the new Intel based Macs? :)
> 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.
Can anyone estimate how long tape is needed to do some real-world computation? Like adding/multiplying two (n-bit) integers?
From the article:
So basically there's a machine that has two states, each of which can be three colors, and that machine can perform ANY computation that an x86 cpu can perform. The code to add two 32 bit numbers in an x86 processor might be just a few bytes and the code to do the same thing with this 2,3 Turing machine might be thousands of bytes, but it can do it. It will be horribly inefficient and slow, but it can be done. They've proved that a 2,2 machine is impossible so a 2,3 machine was the simplest possible theoretical Turing machine. This paper proved that one exists. It doesn't have a practical application right now, but the article mentions possible molecular computers that can use this simple machines to do calculations on strands of molecules like DNA.
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.
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.
-- Ed Avis ed@membled.com
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.
Wolfram probably could have chosen a more modest title for his book, and put his particular ocntributions to CAs in better perspective, but I do think he's right in his emphasis on CAs being a relatively new and important tool for future scientific modeling. It's an attempt to describe the world at a more fundamental level than we currently do, using computers and rules instead of equations. Equations aren't old hat, but they are old school. They often describe things in a macroscopic way - you don't get more out of them than you put in, you simply get a (literally) formulaic output. With CAs, as this proof demonstrates, you can theoretically model anything.
Computers also don't speak equations, so when you translate them to a computer language, you're never really getting what you want, but an approximation. CAs are fundamentally computers themselves. The only frustrating thing about employing CAs to model nature is the alienness of the method. Our minds aren't adept at thinking in terms of thousands of local interactions, and our science has reflected that. Unfortunately, if we can't ever figure out how to make sense of such methods, they'll never be of value to us.
While you may carp about the "science" of NKS there's a sh*t load of extremely interesting potential there.
If you look at kisrael's visualization http://kisrael.com/2007/10/21/ and click on the display mid-low area, you can get "structures" of varying complexity.
What if these structures where generated by a "seed", say protein or molecule in a solution. The seed reacts with the surrounding contents forming a structure at a molecular level. This could be used to build things at the nano level. We could call it an assembler (kurweil).
Problem is constructing the seed(s) for complexity. How you going to predict what'll form. Maybe have a library, component parts list, to build more complex structures.
$proof =~ /perl/
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?
Something doesnt sound right here.
That's just the beauty of this thing... in itself, it is already a Beowulf cluster! of anything!
But will it blend?
Imagine a Beowulf cluster of these.
But will it run Linux?
In Soviet Russia, universal are turning machines.
Coder's Stone: The programming language quick ref for iPad
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.
of this, but it doesn't pass the /. lameness filter ;^)
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.
The society for a thought-free internet welcomes you.
I got totally turned on after reading his proof! Now if only he'd trim that beard down a bit....
Any explanation that begins with "Helps us understand..." or "Has implications for..." is unlikely to contain a real idea.
Identifying an application for a computing machine does not show why universality is important, or why the Turing model is useful.
There may be an idea lurking in the "DNA computer" area, but it must surmount the (large) hump of the Turing-like machines' absurdly inefficient calculations.
Can you imagine all the people working towards that prize that are quite pissed off? Of course, there are going to be many who don't like the proof.
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.
don't cut it off www.mgmbill.org
I'm making a note here: HUGE SUCCESS.
"Your superior intellect is no match for our puny weapons!"
a Beowulf cluster of these!
ah year. no more text here
I don't get it... Right now the computer I am typing on uses only two states to do every computation it does.
So... what?
I do not respond to cowards. Especially anonymous ones.
; in out
; 0 01 -> 0 10 -
; 0 10 -> 0 01 -
; 0 11 -> 1 10 +
; 1 01 -> 0 11 +
; 1 10 -> 1 01 +
; 1 11 -> 0 01 -
; ^-- state ^-- direction
; ^^-- color[BA]
; tape counter
; esi tape side A
; edi tape side B
_010:
btr [edi],ecx
_001:
_111:
dec ecx
State0:
btc [esi],ecx
jnc _010
bts [edi],ecx
jnc _001
_011:
inc ecx
State1:
bts [esi],ecx
jnc _110
btc [edi],ecx
jc _111
inc ecx
jmp State0
_110:
btr [edi],ecx
inc ecx
jmp State1
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.
Andrey Markov was his name, and the algorithm he proposed can be described as a system of several search-and-replace statements that are applied one by one to a string, until one of them matches. Then, the statements are tried against the modified string from the beginning, and so on. Optionally, some statements may cause the "machine" to halt when they first match. If no statement can be applied, the machine also halts.
Of course, this is equivalent to a Turing Machine, as they can emulate each other.
WYSIWIG, but what you see might not be what you need
Am I the only one who read the article and still hasn't understood what's that 2,3 machine about? 2 states and 3 colours? What the hell is that? How does that translate in terms of numbers of operands and what not?
You just got troll'd!
Your sig contradicts itself. Breathing is not forbidden, and holding your breath is also not forbidden, however you cannot breathe while holding your breath. Therefore, since both things are preclusive of each other your mandate is impossible to follow.
The initial parameters don't include the pattern, as the pattern is part of the machine. If we have the machine, we have the pattern, and we have Turing completeness.
Evidently, the key to understanding recursion is to begin by understanding recursion. The rest is easy.
Sorry I can't find any right angles. All the ones I look at, when I look closely enough, they turn out not to be right angles. Can you give me a real world example of a perfect right angle?
The two of you are closer than you may think. I was there when Behaviorism got a bad rap and bad rep, and basically, there was a revolt against "mindless conditioning" and "brainwashing". Ultimately, like any science, some of the useful parts are still used. I truly regret the passing of "programmed instruction, developed by Skinner and Crowder, because it was a very effective way to learn some knowledge and some skills.
One element leading to the failure of Behaviorism as a complete explanation, is the ability of humans to hold values, desires and beliefs. William James' dictum that "to be cheerful, one only has to act cheerful" implies that the person has a desire to be cheerful. Behavioral experiments proved that a person who didn't want to be cheerful would , over a cycle, end up less cheerful than when they started. Behavior modification works very well if the subject is induced to desire the end results.
Chomsky's structural analysis has stood the test of time (as a description of languages), but his theories of cause and effect have suffered major blows. Cognitive Science is the "new" art, but, like Newton's Physics in the light of Quantum Mechanics, there will still be a place for the useful portions of previous scientific thought.
"The mind works quicker than you think!"
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.
Weaselmancer
rediculous.
Newton didn't do everything he claimed first. but
he was a rabid self promoter.. and like Cesar,
credit goes to good self promoters, mostly.
replace( newton, wolfram)
--told ya.
Would a singularity blender be able to blend an infinite tape?
There is no actual requirement that a device be "simple" in order to qualify as a Turing machine.
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.
I was discussing that idea with a co-worker the other day.
All the ramifications of using 8 bits for a byte.
A 32 bit addressing system with an 8 bit byte can addresses about 4 billion sets of 8 bits, or 32 gibibits.
If you just used 16 bits in a byte, you could double the useable storage capacity of a 32 bit address model.
Advantage, a C 'char' would be able to hold a 16 bit unicode character, or a CD audio sample, or half a screen coordinate.
A 32 bit byte could hold a pointer to it's own kind, or a 24 bit color plus alpha channel, or a full size Unicode character (For hieroglyphics or Klingon characters) in one memory location, while giving quick access to 16 gibioctets of RAM.
Complex CPU instructions could be fixed-width single large bytes, allowing a very rich CISC dictionary, possibly some new instructions would be effective concatenation of multiple old instructions.
Hard drive manufacturers may not want to label what is now a '500 gigabyte' drive as '125 gigabyte', until they realize it's also a '4 terabit drive!'
Is this a correct way of interpretting it? "Two states" could be a single 1-bit register. The tape holds the program and the "three colors" at each point are the CPU's three possible instructions. Hmmm, but where is the result of the program stored/output ?
Ok, the machine has two states, each of which can be three colors, and can perform any computation. But, how many states are needed for a machine with only two colors? That is, an "x,2 machine" where you should fill in the x.
The first correct proof of that here at Slashdot, will receive a congratulatory message, from G3ckoG33k!
The definition of 'universal' used in for the competition is not precisely defined, but rather skirted around; see the section "Uses of the Term Universality" (which for some reason doesn't have an anchor, so I can't link to it directly) in the technical details of the prize. Instead of 'halting', the Turing machine in the proof exhibits behaviour that can be considered to be equivalent to halting; there are points in the tape where if the Turing machine moves to their right, it never goes back to their left again, so the information there is preserved as long as the machine is running, and particular sorts of configurations of the section between two such points can be interpreted as saying that the machine has 'halted' (if it generates such a configuration, then every time one of those points is passed the next section will also have a similar configuration, and so on for ever, so the machine is no longer doing any useful computation but instead just doing the equivalent of a very busy busy-wait where it recalculates what it's already calculated over and over again).
(1)DOCOMEFROM!2~.2'~#1WHILE:1<-"'?.1$.2'~'"':1/.1$.2'~#0"$#65535'"$"'"'&.1$.2'~'#0$#65535'"$#0'~#32767$#1"
Yes, so basically it continues forever with NOP as soon as it has finished the program, like the PC on my desk here. This does however, require an infinite program "tape".
don't cut it off www.mgmbill.org
That seems easily solved with RNA or DNA. Gives you 4 symbols and plenty of length...
At least he didn't prove Rule 99.1
I assume the pattern to be the program. This pattern is then acted upon by the rules of this simple 2,3 cellular automaton. I think the combination of bits and rules creates the universal machine. Please explane if I'm wrong.
Yeah, this is pretty much greek to me. What does this mean?
Utilizing the synergization of benchmark e-solutions to pre-workaround action items!
At this point, I'm confused enough about the particular definitions being used here, and the model of Turing machine / cellular automaton that they're using, that I don't know. My original impression was that the definition of the machine had to be slightly modified so that the simple pattern of non-zero bits was built into the tape at initialization, but it looks like it could be that the pattern is supplied as input to the system. I'm not familiar with their model, if it's not just a normal semi- or bi-infinite tape Turing machine.
Evidently, the key to understanding recursion is to begin by understanding recursion. The rest is easy.
Or you could use a 36-bit word-addressed architecture, like the PDP-10 and the Multics hardware did.
list. It looks like Wolfram paid $25,000 for an invalid proof.
Except the ones who are dead.
j'ai découvert une démonstration vraiment admirable (de ce théorème général) que cette si