Become a fan of Slashdot on Facebook

 


Forgot your password?
Close
typodupeerror
×
Robotics Science

A Model Railroad That Computes 198

Posted by timothy 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."
This discussion has been archived. No new comments can be posted.

A Model Railroad That Computes More

A Model Railroad That Computes

Comments Filter:
  • It may be because it's 4:11 am, but I didn't understand ANY of that. :( Anybody smarter care to fill me (and hopefully others) in?

    • Re:Sorry... (Score:3, Informative)

      by KontinMonet ( 737319 )
      Turing machines [stanford.edu]. FSM [wikipedia.org]

      • Re:Sorry... (Score:3, Insightful)

        by Guillermito ( 187510 )
        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
        • The parent asked what it all meant but was then modded out of sight...
        • So, what you're saying is that a human at the keyboard is an infinite source of random input?

          Given the users I'm forced to deal with, I'd have to agree.

          Although sometimes I'm tempted to make them non-infinite using decidedly violent methods.

    • Re:Sorry... (Score:5, Informative)

      by zootm ( 850416 ) on Monday February 14, 2005 @07:22AM (#11666391)
      A Turing Machine [wikipedia.org] 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 [wikipedia.org], 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.

      • Re:Sorry... (Score:2, Redundant)

        by pjt33 ( 739471 )
        A Turing Machine is a simple model of computation that encompasses anything that can be computed by a computer.
        You do seem to be assuming the Church-Turing hypothesis.
    • Explanation for dummies follows:

      It's about making computer from model railway system where computation is expressed in trains moving along rail. Think about trains as bits and rails as wires. If it's Turing equivalent you can port Linux in it.

      Not wery practical.

    • Not TURING machine, TOURING machince.

      Just another dog-gone Slashdot typo.

  • Just state machine? (Score:5, Insightful)

    by notany ( 528696 ) on Monday February 14, 2005 @07:15AM (#11666360) Journal
    I haven't been fortunate enough to find a computer that was more powerful than a sufficiently large finite-state machine.
    • Yep, this is a truly embarassing story. Just goes to show that if you use enough technical jargon, you can fool a Slashdot editor into accepting a troll.

    • Re:Just state machine? (Score:5, Funny)

      by KontinMonet ( 737319 ) on Monday February 14, 2005 @07:21AM (#11666384) Homepage Journal
      Microsoft patented a process [uspto.gov] for a 'limited resource computing device'. Presumably because they are aware of an unlimited resource computing device somewhere. Why don't you contact them?
      • 'limited resource computing device'
        I assume it has less than 64K [ptiservices.com] of memory.

    • Re:Just state machine? (Score:4, Interesting)

      by zootm ( 850416 ) on Monday February 14, 2005 @07:26AM (#11666403)
      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.
      • Hmm, how about distinguishing between a *theoretical* model, which is what a Turing Machine is (with infinite tape and all), and a *real* model (like a model railroad or a computer).

        I'd like to see you try to construct an infinite tape. ;)
        • Heh, I don't know why I went off on one there, actually -- now I've R'd TFA, all this distinction between FSMs and suchlike are nearly completely pointless. Blast!

          You do get space-bounded TMs, though, and they're more sensible things to be dealing with when working with results about computation. Although making a space-bounded UTM implementation with a train set that actually accepted usefully-sized programs would be completely impractical...
        • I'd like to see you try to construct an infinite tape. ;)
          Easy [swin.edu.au]

      • Re:Just state machine? (Score:2, Informative)

        by eyal ( 774028 )
        "billions of states" can be achieved with ~30 bits of memory.
        I believe that in order to model "any physical computation device" you're going to need many many more states
        (1KB RAM == 2^8192 states == ~1e2466 states).
        • I believe that in order to model "any physical computation device" you're going to need many many more states

          A state-machine is much more than just states. It's also the logic that dictates state-transitions. So for the FSM to be complex enough to be useful, the state transition logic will take up much more space than the actual state itself.

          30 bits may very well be enough to store the state of a system. But depending on how the bits represent the states, the transition logic may be more or less compl

    • Re:Just state machine? (Score:1, Funny)

      by Anonymous Coward
      When you realise, that computers are just finite state machines, you also realise that they must reach a point (state) where they have been before. Given the determinative nature of the computer the next state is given from the current. So it starts to repeat it self over, and over again. Isn't this the exact definition of a computer crash? So why does so many people bother switching on their computers when they know that it has entered an infinite loop, even before it has booted.
    • Incorrect. Most computers can function as a linear-bounded Turing Machine with In-Out, on account of the fact that they have input and output ports. That makes them substantially more powerful than a finite state machines and context-free grammars.
    • My computer is an infinite-state machine.
    • As far as we know, the whole universe is just a finite state machine (see, for example, Computational Capacity of the Universe [arxiv.org]). Infinite entropy for finite systems was the big problem with 19th century physics that the introduction of quantum mechanics fixed.
      • Thanks for reference [arxiv.org] (computational capasity of universe). I have been thinking this.

        For funny side of things. Now that we know that we 10E90 bits will be enough for everyone. 299 bits will be enough to address every bit in the universe. 296 bits if we want to access 8-bit bytes.

        It also seems evident that universe wasn't compiled with full optimizations. There is no input or output so all this computation could have been optimized out. Let's have silent moment for this tought [amazon.co.uk].

  • What to do with it... (Score:4, Interesting)

    by wertarbyte ( 811674 ) on Monday February 14, 2005 @07:18AM (#11666374) Homepage
    Could they use it to control another digitally controlled model railroad once they build the more advanced system?
    • 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.

  • Too much time (Score:5, Funny)

    by strider44 ( 650833 ) on Monday February 14, 2005 @07:19AM (#11666376)
    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.

  • Old Idea (Score:5, Informative)

    by Hasie ( 316698 ) on Monday February 14, 2005 @07:20AM (#11666381)
    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.

    • Re:Old Idea (Score:2, Informative)

      by k.a.f. ( 168896 )
      Desmond Bagley: The Enemy. His best book by rather a long margin.

    • Re:Old Idea (Desmond Bagley) (Score:4, Interesting)

      by grinder ( 825 ) on Monday February 14, 2005 @01:11PM (#11669559) Homepage

      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.

  • MIT's Model Railroad Club (Score:5, Interesting)

    by SoupIsGood Food ( 1179 ) on Monday February 14, 2005 @07:22AM (#11666390)
    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
    • See Bill Gosper's Webpage: http://gosper.org/bill.html [gosper.org].

      In EDUCATION, he says:

      • 1963 - 1972 Technology Model Railroad Club. Where I learned the most.

    • Re:MIT's Model Railroad Club (Score:5, Interesting)

      by kahei ( 466208 ) on Monday February 14, 2005 @08:05AM (#11666551) Homepage

      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.

    • It's where my interest in computers came from. Initially I would keep my Dad company and help him with his model railway. Wiring that up got me interested in electronics in the seventies and it was in those electronics magazines I saw the magic that was the hobbyists computer, Altair 8800s, UK101s and the like.

  • Finite State Machines? Don't knock-em (Score:5, Informative)

    by joshv ( 13017 ) on Monday February 14, 2005 @07:23AM (#11666394)
    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.
    • Is this not a Choo-Chooring machine?

    • 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

      • Re:Finite State Machines? Don't knock-em (Score:5, Informative)

        by nuffle ( 540687 ) on Monday February 14, 2005 @08:41AM (#11666728)
        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.
        • While technically a computer can be represented with an a really enormous FSM, to represent a computer with N bits of state (e.g., all the total bits in registers, RAM, hard disk, etc) requires a FSM with O(2^N) states, whereas to model that same system with a bounded-tape TM requires a tape with O(N) cells, so by some sort of vague hand-waving feel-good rational, I thereby claim that a bounded-tape TM is a more meaningful equivalent to a computer. A FSM for the microcontroller in my washing machine might
      • 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.
        Say, like, er, Clippy???
    • Yes, but mine's running Windows, so its a non-deterministic Finite State Machine.

  • Mine was derailed... (Score:5, Funny)

    by Eternal Vigilance ( 573501 ) on Monday February 14, 2005 @07:28AM (#11666409)
    Would a UTM Railroad be a train of thought?
  • The Babbage Engine was, I believe, intended to be a general-puspose programmable compute device. Although never completed by its inventor (sometime in the 19th century), I believe several have been completed in the recent past.
    http://www.sciencemuseum.org.uk/on-line/bab bage/in dex.asp
  • I saw a horse that could do math once... ask it to add, subtract, or multiply, and it was right 9 out of 10 times... No way yer newfangled iLocomotive can beat that sucker!

  • True mechanical implementations? (Score:5, Funny)

    by kinnell ( 607819 ) on Monday February 14, 2005 @07:29AM (#11666414)
    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.

  • Quantum Computer (Score:4, Interesting)

    by fr00dy ( 580649 ) on Monday February 14, 2005 @07:31AM (#11666421)
    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 4 [holbornbooks.co.uk]This book explains it fairly well.

  • D'uh! (Score:5, Insightful)

    by Aardpig ( 622459 ) on Monday February 14, 2005 @07:32AM (#11666424)

    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.

    • Do Slashdot readers know of any mechanical implementations of a truly Universal Turing Machine?


      Of course not.

      I'm sure there must be some... they'll be in a backroom somewhere, stacked next to the perpetual motion machines and the random noise compression algorithms. :-)

    • Re:D'uh! (Score:5, Interesting)

      by smallpaul ( 65919 ) <paul@presco d . n et> on Monday February 14, 2005 @08:38AM (#11666708)

      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 [wikipedia.org].

    • Re:D'uh! (Score:3, Insightful)

      by iabervon ( 1971 )
      An ideal Turing machine only needs an arbitrary amount of storage, not an infinite amount. It is perfectly acceptable to pause in the middle of a run until more tape is added to one end.

      A universal Turing machine has nothing to do with the size of the tape; it is a Turing machine whose FSM supports the emulation of any other Turing machine, when that machine's FSM is written in some format on the tape. That is, it's a computer that runs programs out of storage, rather that having them hardwired in (or, rat

  • Awake for 29 hours, what do I see..... (Score:3, Funny)

    by Eatmorecake ( 858982 ) on Monday February 14, 2005 @07:32AM (#11666426)
    I'm currently at work, graveyard, and this thing just blew my mind. Someone said this thing is terribly slow, (I doubt they meant it as an insult) but if you wanted to solve that problem you could make a three dimentional roller coaster version. That would be MUCH faster.

  • I'm English . . . . (Score:5, Funny)

    by Tetsugaku-San ( 717792 ) on Monday February 14, 2005 @07:38AM (#11666439) Homepage
    I bet they still don't run on time.
  • But when I first read this I thought "How could you possibly make a ocmputer out of a model railroad", followed almost instantly by the idea of using each trip around the railroad as the trigger that acts as a clock cycle.

    Very very slow, of course, but still - a way to make a computer out of a model railroad. ... :(

  • Old news (Score:4, Funny)

    by Timesprout ( 579035 ) on Monday February 14, 2005 @07:47AM (#11666465)
    Thomas the tank engine has been solving problems for ages now, and in multi task more he keeps the kids amused while he does it.

  • in order to implement an UMT storage has to have the potential to ->infinity.

    obviously !? its rather difficult to build infinite storage in a finite universe ;-P

  • Not entirely original ! (Score:4, Informative)

    by CdBee ( 742846 ) on Monday February 14, 2005 @07:55AM (#11666496)
    There was a 70s adventure novel - I believe by Hammond Innes although the title eludes my memory) in which a bomb-scientist who had promised to do no further research when he left government service is kidnapped

    Investigators found that he had a large model railway which was controlled by a computer and the answers to calculations were reported by numbered wagons being arranged in certain orders and locations.....

    It wasn't a very good book, actually.

  • Sure... (Score:4, Funny)

    by famebait ( 450028 ) on Monday February 14, 2005 @07:56AM (#11666499)
    Do Slashdot readers know of any mechanical implementations of a truly Universal Turing Machine?

    No, but I have an infinite tape lying around in my shed, so if you know how to do the logic stuff, we can team up.
    • I have one in my backyard... well technically it is my backyard... and my neighbor's... and their neighbor's...

      I call it the universe.
  • Imagine a Beowulf cluster of these...

  • Editor asleep again? (Score:2, Informative)

    by PDAllen ( 709106 )
    A 'proper' Turing machine is supposed to be able to take on infinitely many states, OK?

    That means that if you want to build one, before you get into how you are going to have the thing operate, you at least have to find a way of coding infinitely many discrete states using some finite amount of matter. Which is not possible: even if you could manipulate matter to the point of using every individual subatomic particle to store a bit of data, there are only finitely many particles and you will have a finite
  • My favourite Turing machine is the one implemented for Conway's life. I think that's pretty impressive.

  • Not a computer? (Score:2, Insightful)

    by plabtfall ( 859254 )
    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... autobiologi

  • Thank God for model trains (Score:4, Funny)

    by Inkieminstrel ( 812132 ) on Monday February 14, 2005 @08:14AM (#11666597) Homepage
    If they didn't have the model train, they wouldn't have gotten the idea for the big trains

  • MS Windows On Board . . . (Score:3, Funny)

    by Dausha ( 546002 ) on Monday February 14, 2005 @08:30AM (#11666675) Homepage
    "I have to point out, though, that it's actually only a Finite State Machine, like a pocket calculator, not a general-purpose device."

    So, does that means it runs Windows? Perhaps it is a special version Windows: Windows RR (as opposed to Windows 958MeNTXP2000CE). Of course, unlike other versions of Windows, it does not crash--it derails.

    Thank you. I'll be here all weekend. Please tip your kelnerino.
  • I choo-choo choose you!

  • Finite State Chicken (Score:3, Interesting)

    by ch-chuck ( 9622 ) on Monday February 14, 2005 @09:13AM (#11666981) Homepage
    Kind of interesting to see that a Chicken [nationalreview.com] can be trained to play a perfect game of Tic-Tac-Toe.

  • Forget the computer thingy... (Score:4, Funny)

    by Reignking ( 832642 ) on Monday February 14, 2005 @09:27AM (#11667120) Journal
    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.
  • As goofy as this may seem, these methods are some of the best ways to:
    1) Demonstrate micro-level computing to people.
    2) Stretch one's imagination as a programmer.

    I recall many fun hours spent building contraptions with legos, lincoln logs, erector sets, and more. Nothing of this complexity, but the understanding of interactions on a physical level really did help me relate to things on a code level.

    Is there any online museum or page summarizing such contraptions?

  • Halting (Score:2, Funny)

    by Redwing ( 311189 ) *
    Turing showed that such a train can never compute whether it will stop at a given station.
  • Alan Turing, meet Gomez Addams..
  • Do Slashdot readers know of any mechanical implementations of a truly Universal Turing Machine?

    Since a universal TM by definition requires an infinitely long tape, uh... no, I don't think there are any mechanical implementations. What a dumb question.

  • A Universal Turing Machine is currently theorized to be an unsolvable problem... that is not to say that it is impossible... but someone would have to disprove the current dogma of Computing Theory in order to create one.
  • Imagine, a search engine (perhaps a small diesel) looking for those missing op codes. I suppose that there would be more likelihood of crashes too, especially if there are too many wet leaves on the tracks.
  • Wasn't there some guy building logic games out of Lego DACTA? With a couple dozen of those and a hand crank you could make an infinite state machine, right?

  • mechanical implementations (Score:3, Informative)

    by Bob Hearn ( 61879 ) on Monday February 14, 2005 @01:34PM (#11669873) Homepage
    Not exactly the same thing, but it is possible to build computers of a sort out of very simple physical systems: sliding-block puzzles. You know, where you have a box of wooden rectangular pieces, and you have to slide them around so as to make one reach a certain position.

    The resulting computers are nondeterministic. They are computers in the sense that, given a Turing machine and a given input, you can construct a corresponding sliding-block puzzle that is solvable if and only if the Turing machine would eventually print YES. The catch is that this only works when the Turing machine is allowed to use only an amount of tape polynomial in its input size (but then, the same is effectively true of real computers). Technically, this means that sliding-block puzzles are PSPACE-complete - that's the next complexity class up from NP-complete.

    Anyway, the construction does involve building logic gates out of sliding-block components, so the things are rather like actual computers. The constructions are based on the earlier result that you can build computers out of Rush Hour puzzles.

    More info here:
  • A truly universal turing complete machine would need an infinite amount of memory. So no, there are no real physical implementations of universal turing machines.
  • By far the coolest implementation of a turing machine is the one at the University of Washington. It's steam powered! [washington.edu]
  • Maniacal turing machine... A cross between The Moon is a Harsh Mistress and 2001: A space Odyssey.

Slashdot Top Deals

"Hello again, Peabody here..." -- Mister Peabody

Close