Slashdot Mirror
A Model Railroad That Computes
tri44id writes "Several blogs have noted an Austrian team that has built a model train set that is a primitive computer. I have to point out, though, that it's actually only a Finite State Machine, like a pocket calculator, not a general-purpose device. Their plan for a general purpose layout is for an infinite-state machine, not a FSM+tape that Turing envisioned in his original paper. Turing took the concept a further step, by presenting a Universal Turing Machine that embodies a special set of states and transitions that allows its tape to be programmable to emulate any other TM. Do Slashdot readers know of any mechanical implementations of a truly Universal Turing Machine? (Danny Hillis' famous tinkertoy tic-tac-toe machine has neither infinite tape nor programmability, and is thus yet another FSM. It shouldn't be hard to elaborate the Austrian model train FSM to use a series of cars carrying movable magnets to represent Turing's tape cells writable with different symbols, and thus become a true TM or even UTM."
I haven't been fortunate enough to find a computer that was more powerful than a sufficiently large finite-state machine.
Dyslexics have more fnu.
See how big that railway system is and see what it does: calculates 1 + 1. Besides the fact that you'd need underlying mechanics to control the other model railroad, it'll also be absolutely enormous and as slow as hell. Just think of how long one train would take to calculate one instruction using that thing, and think of how many instructions required... which would be a hell of a lot.
Do Slashdot readers know of any mechanical implementations of a truly Universal Turing Machine?
Of course not. A truly Universal Turing Machine needs an infinite amount of tape. Or RAM. Or HDD. Or Spaghetti. Or any other infinite amount of storage device. Hell, the submitter makes this clear in their spiel, just after they ask the vacuous question above. I guess they should read what they write a little closer; or stop prancing around like a tit, trying to sound profound and knowledgable.
Tubal-Cain smokes the white owl.
I think the original poster's point is that *real* computers are just FSMs, because they dont have the infinite tape that TMs are supposed to have.
In that sense, if you add all the bytes of the processors registers plus all the bytes of the RAM, plus all the bytes of hard drives, you get a really, really big natural number. That number would represent the state of the machine.
You could easily extend that to a network of computers, aggregating all individual states to form a big network state.
On the other hand, that conceptualization falls once you add the human factor (think of mouse clicks or keyboard input). It is not as easy to link a human's state to a natural number.
So, when human input is involved (or maybe some other input source, like a temperature sensor) I think that input can be regarded as the infinite tape, making real computers TMs after all.
After reading this article and the article on the tinkertoy "computer", it surprises me what people consider to be a computer. Did anyone else notice the fact that the train "computer" is just pushing digits around? It computes in *unary*, which is the most inane operation one can think of. We're supposed to be impressed if someone can get a machine to take the input, 11011101 (Meaning 2+3+1) and produce the output, 11111100 (meaning 6)? I'd rather use my much more powerful hands... I mean... autobiological computers.
You're trying to be clever but I hope you do know that having a "finite number of states" is not in and of itself a definition of a FSM.
You could use your general purpose computer as a finite state machine but it would be an enormous waste of power. Let's imagine for a second that you take your computer with its 4GB of RAM and 100GB of hard disk and invent state names for every possible state. You then write a program in terms of transitions between these states (this is what FSMs do, after all). Now you go to someone else's computer with a little bit less RAM. You cannot repesent as many states now so you must decide which of your named states are least important: like dropping functionality from a program by throwing away functions.
On the other hand, if you think of your computer as a Turing machine and think of the hard disk as a tape then you can run the same program on computers with different amounts of "tape" and the programs will just use the amount of tape that they need.
It is demonstrably the case that a finite state machine cannot be programmed to run a JVM or a Python interpreter. For that you need something that is Turing-complete.
You're missing the point here -- a modern computer is not a closed device. Its ability to interact with the outside world via I/O of various kinds gives it the full range of a TM's power. A computer is not just its RAM and CPU and hard drive.