Slashdot Mirror
Home-Built Turing Machine
stronghawk writes "The creator of the Nickel-O-Matic is back at it and has now built a Turing Machine from a Parallax Propeller chip-based controller, motors, a dry-erase marker and a non-infinite supply of shiny 35mm leader film. From his FAQ: 'While thinking about Turing machines I found that no one had ever actually built one, at least not one that looked like Turing's original concept (if someone does know of one, please let me know). There have been a few other physical Turing machines like the Logo of Doom, but none were immediately recognizable as Turing machines. As I am always looking for a new challenge, I set out to build what you see here.'"
I admire people who build things like this, but at the same time I also wonder just why the heck they do it.
I guess that's the difference between people, I'd rather build something new than re-create something that's been done before. (Honestly not trying to sound like an ass, just find it interesting.)
maybe i'm missing something but i'm used to people talking about "turing machines" as a machine that is "turing-complete", not looking like a hypothetical turing machine he described in his paper. Is this aesthetics over the principle he meant it to be taken by? Cool hardhack though btw, love to have one of those on my coffee table.
WÌÌfÍ--ÍSÌÒÍ...Í...ÌHÌÍfÍÍÍ--ÍÍÍ
Hot Tub Turing Machine!
For social reasons I will refrain from mentioning this to my friends (which I have) later tonight. Baaaah, I want one! This is so pointless but nifty, my inner collector is crying out. Damn fiscal responsibilities in life tell me it's a waste of money, but oh, the geeky child inside cries out!
"Sorrow is better than laughter, for by sadness of face the heart is made glad." [Ecclesiastes 7:3]
No relays. How sad.
Warning: this article may contain humor, sarcasm, parody, and perhaps even irony. Read at your own risk.
I think you'll find that every single computer ever made has been a Turing machine.
Purely technically, a Turing Machine that hasn't infinite tapes is simply a Finite State Machine. You cannot build a "real" Turing Machine. Doesn't make his creation less interesting though :-)
And you'd be wrong.... Computers are Finite State Machines with an insane number of states.
Couldn't that be said of any Turing machine? Whatever you build it out of is Turing-complete, I think.
RTFA. I know that's a sin, but seriously, do. You'll discover you are wrong.
The microcontroller loads the program as written in ascii on an SD card. It also can write the initial data onto the tape. After that, the computation is, indeed, performed by the "machine". Hence the optical reader for the characters on the tape.
That was my thought as well, shouldn't the program and data be on the tape.
A turing machine isn't just the head and the tape, its those things plus a state transition table. The microcontroller is doing the state transition table part.
Actually, if you'd bother reading the article, you'd find that the micro-controller is being used to do drive the electric motors, image process and maintain the turing machine's "state". that's it.
Sigs are for the weak.
A troll with mod points...
As for the article though, this is really cool stuff. This machine would have fit right in on the set of Terry Gilliam's Brazil.
Incorrect. The keyboard, mouse, and audio input insure it is indeed a Turing machine with infinite input.
- For the complete works of Shakespeare: cat
A Turing machine is supposed to represent what an infinitely patient mathematician with no insight can achieve when he has an infinite amount of paper and pencils. Obviously, the infinity here poses some problems, but you can build a finite Turing machine by finding a mathematician that has no insights,giving him tranquilizers to make him more patient, and locking him into your basement with some food and papers and pencils.
It looks like some berserk moderators got in here. Why all the troll mods?
The hardware is very elegant and well-done. The guy is a multi-talented geek of the highest order.
"Eve of Destruction", it's not just for old hippies anymore...
Until he installs an infitite tape, this is computationaly equivalent to a Finite Automata.
Wow...where can I buy a Turing-complete microcontroller?
The microcontroller is used to implement the action table of the turing machine. Nowhere in the description of a turing machine does it say how those transition rules are to be implemented.
Now, let's look at how this works. It reads a symbol from the tape using the camera. Then it checks its internal state, and sees what it should do with that symbol (should it change the symbol, change the state, and/or how should it move). Then it does that action and moves on to the next symbol as instructed by the last "rule". Considering that the only thing that the machine keeps track of from position to position is the state, it is indeed a Turing machine. The microprocessor's job (as he states) is to act as the read/write head for the machine. Turing never described HOW the head worked, just WHAT it did. And this head performs EXACTLY what Turing described. And that's why this is a Turing machine. If you wrote a program on your computer that did this, it too would be a Turing machine. The delineation is in how it handles and stores states, not the method in which it "processes" data... And Turing's original work described a Turing machine as using a person to perform the actions (but strictly following the ruleset). So I fail to see how this could possibly NOT be a Turing machine...
If a man isn't willing to take some risk for his opinions, either his opinions are no good or he's no good
The program would only ever be on the tape in the case of a Universal Turing Machine: http://en.wikipedia.org/wiki/Universal_Turing_machine...
If a man isn't willing to take some risk for his opinions, either his opinions are no good or he's no good
So does this technically pass the Turing test?
I am Slashdot. Are you Slashdot as well?
Ensure. Unless you mean those input devices actually insure your computer. Maybe that was part of the health care bill?
The duality between data and program is one of the fundamental concepts of computer science. The Turing machine is a program that runs another program. The outer program encodes the (simple, encodable) rules of the Turing machine, and was originally intended to be a human with unlimited paper and pencil. The inner program is the tape. Ask yourself this: what would this machine do without a tape?
Having worked in recursion theory, my (mental) picture of a Turing Machine is a little different.
The tape is vertical, and the head writes and reads from the side. The "state-transition table" is next
O__________O
^
!
[ ]
Stephan
http://stephan.sugarmotor.org
This is a very cool interpreter. But it's not a Turing machine.
A Turing machine is an interpreter. It interprets the code on the tape.
Imagine it was a human instead. This human is given a list of rules (a program) to follow. Then we give the human the tape (a program) and we tell him to follow the rules. That is a Turing machine, and that is what we have here, encoded into an actual machine instead of a list of rules. I think what you are missing is that the list of rules that the human is given is encoded as a program on the microcontroller. This is exactly what one expects from a Turing machine made into an actual machine.
From http://www.askoxford.com/concise_oed/insure
insure
verb 1 arrange for compensation in the event of damage to or loss of (property, life, or a person), in exchange for regular payments to a company. 2 secure the payment of (a sum) in this way. 3 (insure against) protect (someone) against (a possible eventuality). 4 another term for ENSURE.
You might want to pay attention to definition #4.
Yeah, but does it run Linux?
I don't care if it's 90,000 hectares. That lake was not my doing.
I agree, although for the sake of appearances, it would be cool if the finite state machine portion were hard-coded to implement a universal turing machine, and the only programmability was the starting contents of the tape.
I agree, although for the sake of appearances, it would be cool if the finite state machine portion were hard-coded to implement a universal turing machine, and the only programmability was the starting contents of the tape.
It would be more than cool--it would be actually demonstrate Turing's remarkable core insight. As it is, this a very clever micro-controller implementation of a programmable finite state machine that uses a long tape as an book-keeping device. He says in the description, "In a way the tape is the computer" but this is false. The programmable finite state machine in the micro-controller is a the computer.
The tape in this machine isn't doing any computing at all. It is just helping the finite state machine along. Turing's core insight was that you can get rid of the finite state machine and just have the tape, and a very simple set of universal rules. Implement those on a non-programable finite state machine and you've have, as you point out, a universal Turing machine where all the programability is in the initial number written on the tape. That would be mind-blowingly cool.
This is cool, but falls well short of mind-blowingly so.
Blasphemy is a human right. Blasphemophobia kills.
Actually that's a great question, and I'm curious about that too, except I think that the answer is if we consider voltage states. Technically there's three states that a signal could be in, which are {off, on, neither} where the third state is easier to illustrate if I can use voltages instead. Let's say that instead of off and on we consider nearly zero (demonstrated as 0) volts for off (makes sense, right?), five volts for on and then a third state where we're neither at 5V or 0V, say 2.5V.
Surely it's reasonable that there might exist a 2.5V in this pattern, right? For instance, if we're traveling from 0V to 5V, we must pass through 2.5V. I forget now the cases where a digital circuit can easily have 2.5V when it seems like it must have only either 0 or 5, but I recall it's quite normal. I think it has something to do with not having a direct ground always attached, the floating ground moves into 2.5V range.
So because of this, it's possible for a gate to exist in any of three states. That's the blank slot indicated on the tape. Think of it as a Heisenberg spot.
Now, who can tell me what I got wrong here?
2^3 * 31 * 647
Should be finite.
Utilizing the synergization of benchmark e-solutions to pre-workaround action items!
I believe the 1, 0 and blank are the characters of the TM's alphabet, not the states. The states are internal to the machine and there can be quite a lot of them depending on what the program is to accept the TM's language.
http://www.youtube.com/watch?v=cYw2ewoO6c4&feature=fvst
"The number you have dialed is imaginary. Please rotate your phone 90 degrees and try again."
Blank tape is unformatted media. Please run mkfs.tm first.
I would sure like to see your keyboard that has an infinite number of keys. There's a very important distinction between "practically infinite" and really infinite. A standard computer keyboard, not counting shift/ctrl/alt would have n! / (k! (n - k) !) or whatever the formula is, where ~105 is the number of keys on the keyboard.
Unity? Screw that: XFCE. Slashdot Beta? Screw that: SoylentNews. Australis? Screw that: Pale Moon. UX developers DIAF
Apparently my keyboard is a better model than yours. I can hit keys multiple times in any combination I like.
- For the complete works of Shakespeare: cat
I will bequeath my computer to my heirs along with instructions to enter new data every... let's say 108 minutes.
As parts break they will have to replace them in time for the next input.
See you in 80 years.
- For the complete works of Shakespeare: cat
Im impressed: For an infinite tape, the reels look very compact.
Turing's core insight was that you can get rid of the finite state machine and just have the tape, and a very simple set of universal rules.
Do you mean to say that a true universal turing machine has a fixed state transition table regardless of what the desired program was, and that programming is done solely by setting the initial tape? Having the program contained solely in the tape and manipulated with a fixed universal rule set, and still be able to program anything so to speak, would indeed be amazing.
Did Turing ever specify that simple set of universal rules?
No, actually he was correct. Having an unlimited amount of input (over a finite alphabet) does not promote a finite state machine to being a (classical) Turing machine. If you want to have a real Turing machine, then you must have unlimited writable memory (as well as a few other things). Finite state machines handle unlimited input just fine. Actual desktop computers have "only" a finite (gigantic) number of possible states, assuming you don't let people swap in an unlimited number of new hard drives.
$META_SIG_JOKE
...which still gives you a finite number of combinations as you could always have more combinations if you had one extra key.
Unity? Screw that: XFCE. Slashdot Beta? Screw that: SoylentNews. Australis? Screw that: Pale Moon. UX developers DIAF
Maybe he can put my friend's annoying cat in a box that's rigged up to release a hammer that will shattering a vial of acid if a radioactive isotope decays. Though in practice, nothing will change. It seems like it simultaneously may or may not claw me at any given point. I can't see how it simultaneously being dead or alive will be any more or less predictable than its own capricious nature, with respect to being clawed.
"That which does not kill us makes us stranger." -Trevor Goodchild
“Home-Built Time Machine”?
For a tiny moment there, my heart jumped. :/
Any sufficiently advanced intelligence is indistinguishable from stupidity.
A machine that can calculate anything, regardless of complexity? I, for one, welcome our new garage-built overlords.
You have a flawed understanding of 'infinity'.
Infinity plus one is not greater than infinity.
Neither is 'infinity and beyond'.
- For the complete works of Shakespeare: cat
Exactly my point. I've been saying all along that it is NOT infinity. You aren't listening.
Unity? Screw that: XFCE. Slashdot Beta? Screw that: SoylentNews. Australis? Screw that: Pale Moon. UX developers DIAF
It needs neither. It needs finite, but unbounded, memory.