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.
I just wasted about half a day compiling and recompiling my linux kernel to get it "just right".
But still, I feel even I have the authority to say that some people just have too much time.
A Turing Machine is a simple model of computation that encompasses anything that can be computed by a computer. The strongest claim about the ability of a programming language is that it's "Turing Complete", which means that anything that can be computed on a Turing Machine can be computed in a language. Turing Machines are designed to be very simple, and they're good for theoretical things about computer science.
A Universal Turing Machine is a Turing Machine that takes, as its input, an encoding of another Turing Machine, then simulates it. As such, you can prove that with a Turing Machine, you can compute anything that any other Turing Machine can.
By contrast, Finite State Machines, or Finite Automata, are far less complex models of computation. If you treat them as language acceptors (i.e., everything that they compute is whether or not a string is valid in a language) they are only as powerful as simple regular expressions. They can be modelled very quickly by computers, though, since they are deterministic and require no lookahead.
Would a UTM Railroad be a train of thought?
I bet they still don't run on time.
My Portfolio
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. He wasn't trying to be clever, just accurate. Your computer is a finite state machine; It is not a Turing machine. We tend to think of them as Turing machines only because they have an enormous number of states; thus they seem to act like Turing machines as long as we don't do anything that requires more states than the computer has. However, when you run out of ram and/or disk space, you've just recognized the limitation of your desktop FSM. It is demonstrably the case that a finite state machine cannot be programmed to run a JVM or a Python interpreter. That is incorrect. Every computer program is a FSM.