Slashdot Mirror

← Back to Stories (view on slashdot.org)

A Model Railroad That Computes

Posted by timothy on from the network-of-tracks-is-the-computer dept.

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."

19 of 198 comments (clear)

  1. Just state machine? by notany · · Score: 5, Insightful

    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.
    1. Re:Just state machine? by KontinMonet · · Score: 4, Funny

      Microsoft patented a process for a 'limited resource computing device'. Presumably because they are aware of an unlimited resource computing device somewhere. Why don't you contact them?

      --
      Did he inhale?
    2. Re:Just state machine? by zootm · · Score: 4, Interesting

      Finite State Machines, however, are useless as models of computation when you're treating them in that way. True, you can theoretically model any physical computation device with an FSM (albeit one with billions of states, even for the most simple systems which allow arbitrary computation), there is a difference between being a simple regular language acceptor and being Turing Complete.

  2. Too much time by strider44 · · Score: 5, Funny

    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.

  3. Old Idea by Hasie · · Score: 4, Informative

    That is really awesome! The idea of a model railroad being a computer is not new though. I read a book by Desmond Bagley (or was is Alistair Maclean) many years ago where a scientist who wanted his work to remain secret built a model railroad/computer. His dying act is to give his model railroad timetables to the main character. The main character later realises that the timetables are actually code for this unique computer.

  4. MIT's Model Railroad Club by SoupIsGood+Food · · Score: 4, Interesting

    It's interesting to note that almost everything we find weird and wonderful about computers, and about the culture that builds, modifies and programs computers for the sheer love of intellectual challenge, stems from the MIT Model Railroad Club.

    The hackers who loved switches, relays, automation systems and doing beyond-tomorrow stuff with all of it irritated the hell out of the guys who liked collecting little models of trains, and eventually went on to be the Midnight Hackers of fame.

    SoupIsGood Food

    1. Re:MIT's Model Railroad Club by kahei · · Score: 4, Interesting


      That's where everything _you_ find weird and wonderful about computers comes from.

      If I had to pick a well-defined culture and declare that I belonged to it, as so many /.-ers do, I'd trace my roots back to the home computers of the 80s -- a very different mindset, a bit less cosy, but with the benefit of sprite graphics!

      And when I say sprite graphics, I mean all 15 sprites!

      Note for socially-undeveloped Lisp programmers from MIT: The point of the last sentence was that there were only 8 sprites on the main sprite graphics platform, the VIC chip, but you could produce 15 (and probably more) by confusing it sufficiently. Hacking, you see. Like with the trains. It's an analogy. C'mon, we can be freinds.

      --
      Whence? Hence. Whither? Thither.
  5. Re:Sorry... by zootm · · Score: 5, Informative

    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.

  6. Finite State Machines? Don't knock-em by joshv · · Score: 4, Informative

    I have to point out, though, that it's actually only a Finite State Machine, like a pocket calculator, not a general-purpose device

    Yes, and your desktop computer is also another example of a finite state machine. Granted, all those little silicon switches have an enomorous number of possible states, but rest assured, the total number is indeed finite.

  7. Mine was derailed... by Eternal+Vigilance · · Score: 5, Funny

    Would a UTM Railroad be a train of thought?

  8. True mechanical implementations? by kinnell · · Score: 4, Funny
    Do Slashdot readers know of any mechanical implementations of a truly Universal Turing Machine?

    Given the requirement for an infinitely long tape, I suspect the answer to this question might be no.

    --
    If I seem short sighted, it is because I stand on the shoulders of midgets
  9. Quantum Computer by fr00dy · · Score: 4, Interesting

    AFAIK the only truly universal turing machine must be implemented with reversible logic and be based on quantum mechanics. http://www.holbornbooks.co.uk/details.aspx?sn=3917 4This book explains it fairly well.

  10. D'uh! by Aardpig · · Score: 4, Insightful

    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.
    1. Re:D'uh! by smallpaul · · Score: 4, Interesting

      No need to be a jerk. The poster's meaning was clear enough. "Has anyone built a mechanical (non-electronic) computer which has the capacity to deal with an arbitrary amount of simulated tape and therefore run arbitrary computer programs up to the limits of the tape available at any particular time." If we all spent our times being as literal as you are, computer science would be quite impoverished. "No need to discuss Turing machines in CS class because Turing machines and computers are totally different things: one depends on infinite tape and the other on finite hard disks. Computer languages can therefore never be Turing-complete." It's a pet peeeve of mine and a way for pedants to try to sound "profound and knowledgable."

      The question is not vacuous and in fact someone has created a mechanical Turing machine.

  11. I'm English . . . . by Tetsugaku-San · · Score: 5, Funny

    I bet they still don't run on time.

    --

    My Portfolio
  12. Thank God for model trains by Inkieminstrel · · Score: 4, Funny

    If they didn't have the model train, they wouldn't have gotten the idea for the big trains

  13. Re:Finite State Machines? Don't knock-em by nuffle · · Score: 5, Informative

    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.

  14. Forget the computer thingy... by Reignking · · Score: 4, Funny

    This layout is horrible! Get some trees in there! Some buildings? This guy made up the computer idea to hide the fact that he couldn't use plaster-of-Paris.

    --
    One man's Funny is another man's Offtopic.
  15. Re:Old Idea (Desmond Bagley) by grinder · · Score: 4, Interesting

    You were right the first time. Desmond Bagley wrote "The Enemy" and it featured a model railway that computed genetic manipulations.

    It was bought by the main character at an auction, for 31000 pounds. When his boss heard that he had bought a train set for such an ungodly amount of money he said "You expect me to be able to clear that through Expenses?" To which the character replied "Call it by its real name, a computing device."

    'Twas a fine yarn that story. Nearly as good as Running Blind.