Home-Built Turing Machine 123
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.'"
Cool...I think. (Score:2, Insightful)
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.)
Re:Cool...I think. (Score:4, Insightful)
Re: (Score:2)
I don't think it has been done before though. At least not as a hardware implementation.
The requirement for an infinite length of tape may have been a minor problem, IMHO.
Re: (Score:1)
Re: (Score:3, Informative)
Strictly speaking, limiting a Turing machine to a finite tape makes it something other than a Turing machine (e.g. a linear bounded automaton).
Re: (Score:3, Interesting)
Personally, having been entirely fascinated with Turing and his work during my college years (from a mathematical point of view - the Entscheidungsproblem [wikipedia.org] rather than CS), seeing an actual Turing machine sends shivers up my spine. Kudos!
For anyone interested in knowing more about this fascinating scientist, I recommend the book by Andrew Hodges [amazon.com].
Re: (Score:1)
Re: (Score:2)
I didn't think it was all that rare but the last time I read it was in 2000 and borrowed from the university library so I might be mistaken. I guess if you really can't find a lower price, I'd just check out the movie with Kate Winslet
Here's the link to the UK version (if you don't mind paying international shipping)
hmmm (Score:3, Insightful)
Re:hmmm (Score:5, Funny)
To provide randomized starting positions for your game of life simulations, without sinning against Von Neumann, a vintage mahogany-clad Geiger-Müller counter would of course be included...
Re:hmmm (Score:5, Interesting)
Re: (Score:2)
There really needs to be some sort of mod point emergency reserve...I would break the hermetic seal for you, kind sir.
Also, your comment, for some reason, reminds me of most Javascript code that I've seen...
Re: (Score:1)
Re: (Score:2)
Re: (Score:2)
Re: (Score:1, Informative)
A "Turing machine" is what you see in the video—or at least it would be, if it were an ideal abstraction with an infinite supply of tape and the ability to remember an unlimited number of states (although the number of states would be finite in any given program). A "Turing-complete" machine/language is one that is capable of simulating a Turing machine—again, adjusting for finite memory within the bounds of common sense.
The significance is that Turing proved that a Turing machine can execute an
Re: (Score:2)
I'd imagine that, when you explain the concept of a Turing machine to someone, having a physical implementation like that, where all operations are explicit and obvious, might help.
Know what I'm thinking? (Score:5, Funny)
Hot Tub Turing Machine!
This made me have a major geek moment. (Score:5, Funny)
Re: (Score:1)
Pointless? It can do ANYTHING!
Re: (Score:1)
"Parallax Propeller chip-based controller" (Score:4, Funny)
No relays. How sad.
Re: (Score:1)
No relays. How sad.
Nice use of Spaceley Sprockets though.
Re: (Score:1)
I found that no one had ever actually built one (Score:1, Interesting)
I think you'll find that every single computer ever made has been a Turing machine.
Re: I found that no one had ever actually built on (Score:5, Insightful)
Re: I found that no one had ever actually built on (Score:4, Insightful)
Incorrect. The keyboard, mouse, and audio input insure it is indeed a Turing machine with infinite input.
Re: (Score:3, Funny)
Re: (Score:1, Funny)
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.
Re: (Score:1)
Re: (Score:2)
Apparently my keyboard is a better model than yours. I can hit keys multiple times in any combination I like.
Re: (Score:1)
Re: (Score:2)
You have a flawed understanding of 'infinity'.
Infinity plus one is not greater than infinity.
Neither is 'infinity and beyond'.
Re: (Score:1)
Re: (Score:3, Interesting)
Re: (Score:2)
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.
Technically... (Score:5, Insightful)
Re:Technically... (Score:5, Interesting)
Re: (Score:3, Interesting)
Well, if you want to split hairs, at least split them to the end...
Eventually, of course, the universe will run out of mass for you to make tape out of, but the machine is still a proper Turing machine.
How is this "still a proper Turing machine"? There are programs that would work on a theoretical Turing machine (with arbitrary amount of tape), but would run out of memory in your scheme.
The OP point stands: we will never actually be able to build a real Turing machine[1]. Still, computers are very good approximations (for programs that require up to a certain amount of memory).
[1] Assuming the universe is actually expanding and that the th
Re: (Score:2)
How is this "still a proper Turing machine"? There are programs that would work on a theoretical Turing machine (with arbitrary amount of tape), but would run out of memory in your scheme.
"Good news, guys, we've solved the halting problem [wikipedia.org]... only wrinkle is, it requires all the matter in the universe, and complete entropic heat death. Oh, and it doesn't really come up with a solution, it just halts."
Re: (Score:2)
Purely technically, a Turing Machine that hasn't infinite tapes is simply a Finite State Machine.
Then by extension, you could not program one either. So essentially all those Turing machines programmed in computers really aren't. The fact is, from the busy beaver's point of view, the Turing machine is real as long as you don't run out of tape. It perhaps would help this Turing machine if the reels of tape were larger (so it would not run out of tape before it halted). Of course, the more complex Turing machines will run out of tape (or exceed the limits of the computer!).
I think the bigger flaw to this
Re: (Score:2)
A Turing Machine is a mathematical model of computation. In any math model there may be an impedance mismatch between the model and it's translation to physical representation. The key is to make sure the mismatch only affects items which are not critical to the usefulness of the model.
I agree that from a physical and practical point of view, this is a Turning Machine, because it is the best approximation of the model in physical form that anyone will be able to build.
Re: (Score:2)
Bureaucrat Corporate_Troll you are technically correct, the best kind of correct.
Re: (Score:1)
Re: (Score:2)
I think what we have here is something that can implement a large subset of Turing machines (i.e. specific initial tape/state table combinations) but falls short of being a universal Turing machine because there will always be computable algorithms that it can't run because of (a) lack of tape or (b) tape melting due to the sun leaving the main sequence.
My call would be that you can't have a physical implementation of a true universal Turing machine - because you need to be able to "run" a non-computable
How cute. (Score:2)
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.
Turing Machine=Mathematician Without Insight (Score:5, Funny)
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.
Re: (Score:2)
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.
You just described every elementary school math class.
Setting aside the Turing stuff... (Score:5, Insightful)
Re: (Score:2)
Re: (Score:1)
Re: (Score:2)
What are the orders of geekhood and who ordains them? and which is the highest?
The Order of the Circular Slide Rule. I take it you haven't even got a straight one.
Unkempt facial hair and dodgy personal hygiene just don't confer the same authority.
Re: (Score:2)
Re: (Score:2)
Re: (Score:2)
Finite State Machine (Score:2)
Re: (Score:1)
Re: (Score:2)
Until he installs an infitite tape, this is computationaly equivalent to a Finite Automata.
If you're going to be pedantic, then get it right --- the machine is computationally equivalent to a finite automaton.
What I find tickling about this implementation is the clear evidence of an embedded FSM emulating the programmed TM. Since the erase, write, and read portions of the head are physically displaced, the interpreter needs to shift the tape back and forth to execute a simple TM operation like "read symbol at current location" or "write a 1 at current location". Then, of course, there are the m
Re: (Score:3, Funny)
If you replace every instance of "Finite State Machine" with "Flying Spaghetti Monster", the post sounds more like a religious discussion.
Re: (Score:2)
Re: (Score:1)
Re:Finite State Machine (Score:4, Funny)
What I find tickling about this implementation is the clear evidence of an embedded FSM emulating the programmed TM.
The Flying Spaghetti Monster is embedded in the programmed Transcendental Meditation?
Proof of Intelligent Design!
Re: (Score:2)
Until he installs an infinite tape, this is computationally equivalent to a Finite Automata.
Welcome to theoretic physics. Hope you enjoy your career computing landscape probabilities over the 10^500 purported vacuum states. Bring lots of sharp pencils, you'll need them.
Experimentally, this machine is indistinguishable from a real Turing machine until it whumps up against the end of the tape and the tape daemon refuses to splice a continuation tape. This is known as Fermat's procurement failure.
Then again, there is no such thing as an observable distinction of a real Turing machine from a fake o
Turing tested and approved? (Score:2)
Re: (Score:2)
I guess you were joking, but just for the benefit of any passing geek wannabes:
The Turing Test (an "hard AI" concept) and the Turing Machine (a conceptual computer) are related only in that they were conceived by the same man. You don't need a Turing Machine to pass the Turing Test.
Arrangement (Score:2)
The tape is vertical, and the head writes and reads from the side. The "state-transition table" is next
O__________O
^
!
[ ]
Stephan
Re: (Score:2)
I'm sure with effort you could draw an ASCII art Turing machine that looks like goatse...
Obligatory (Score:2)
Yeah, but does it run Linux?
Re: (Score:2)
Not until someone writes a Gcc backend that produces tapes for it.
Re: (Score:2)
Yes, but only on a Beowulf cluster of them in Soviet Russia. YMMV.
Re: (Score:2)
Non-infinite (Score:2)
Should be finite.
Re: (Score:1, Interesting)
So you haven't seen this? (Score:2, Interesting)
http://www.youtube.com/watch?v=cYw2ewoO6c4&feature=fvst [youtube.com]
I'm impressed (Score:5, Funny)
Turing on using human computer as 'Paper Machine': (Score:2)
His next project? (Score:2)
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.
Did anyone else read that as: (Score:2)
“Home-Built Time Machine”?
For a tiny moment there, my heart jumped. :/
Calculate anythihng? (Score:1)
Re: (Score:3, Interesting)
Couldn't that be said of any Turing machine? Whatever you build it out of is Turing-complete, I think.
Re:You're Doing It Wrong (Score:5, Informative)
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.
Re: (Score:1)
No, I'm right. He says the micro's job is to read and write to the tape, and perform the simple steps as instructed by the tape.
That's fine, and that's cool. But it's not a Turing machine; it's a Turing machine emulator. I could write a program on my computer, feed it a virtual "tape" and do the same thing. It'd only be following the directions on the 'tape', but it'd be an interpreter.
This is a very cool interpreter. But it's not a Turing machine.
Re: (Score:1)
Re:You're Doing It Wrong (Score:5, Informative)
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...
Re: (Score:2)
Re: (Score:2)
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 machin
Re: (Score:2)
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?
Re: (Score:1)
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 e
bad moderation (Score:3, Insightful)
It looks like some berserk moderators got in here. Why all the troll mods?
Re: (Score:2)
It's OK, the sane mods overruled the idiots. He's at +5 now. The system works!
Re: (Score:2, Troll)
That was my thought as well, shouldn't the program and data be on the tape.
Re:You're Doing It Wrong (Score:4, Interesting)
All in the head? (Score:3, Insightful)
Re: (Score:3, Informative)
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" [wikipedia.org]. that's it.
New Math? (Score:3, Funny)
Re: (Score:2)
Skeptical look.... Is this micro-controller made with real bits of Turing?
Re: (Score:1)
Re: (Score:2)
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 re
Re: (Score:3, Insightful)
Re: (Score:2)