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."
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?
Quid festinatio swallonis est aetherfuga inonusti?
Africus aut Europaeus?
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.
Could they use it to control another digitally controlled model railroad once they build the more advanced system?
Life is just nature's way of keeping meat fresh.
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.
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.
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
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.
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.
Dyslexics have more fnu.
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.b bage/in dex.asp
http://www.sciencemuseum.org.uk/on-line/ba
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!
Don't you mean.. BIZZARO!
Is this not a Choo-Chooring 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
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.
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'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.
Don't you mean.. BIZZARO!
I bet they still don't run on time.
My Portfolio
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.
Just call the Stoch Tape company and they might could at least help you out. Here is where you should look for help 3M.
May
That's it, I'm putting on my Nikes and drinking the CoolAid!
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.
Do not try to read the dupe, thats impossible. Instead, only try to realize the truth
What truth?
There is no dupe
number of states with finite hardware, dumbass.
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
When the seagulls follow the trawler, it's because they think sardines will be thrown in to the sea
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.
I have been a user for about 10 years. This ends Feb 2014. The site's been ruined. I'm off. Dice, FU
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.
sudo ergo sum
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.
Imagine a Beowulf cluster of these...
Remember, there are no stupid questions. But there are a lot of inquisitive idiots.
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 state machine.
Per the Heisenberg uncertainty principle, you cannot try to encode your state as an infinite-precision real which is (part of) the position or whatever of an object either, if you want to build a machine which is always contained in a finite space.
You could build a machine which will extend up to physical limits: stick a radar reflector in space, well away from any gravitational influence (which might be a problem, but...), and build a rocket ship which keeps track of how far away the radar reflector is, in the obvious way, keeps it an exact multiple of 1 metre, and runs a universal program (can do this in silicon logic on board) with that distance as the register. Assume that somehow it is possible to fuel the ship. With a bit of care, you can program things such that this program goes wrong with very low probability (you can allow for relativity, you can't rule out quantum effects deciding to move things suddenly by >0.5m, but it is very very unlikely). That will function as a universal Turing machine whenver you put in a program that does not require you to store any really large numbers. But when you are required to store large numbers you may run up against a physical limit in that you may well find there is an upper limit on the length of a geodesic in space-time, and you will be unable to store bigger numbers.
My favourite Turing machine is the one implemented for Conway's life. I think that's pretty impressive.
I am trolling
There is an online demonstration of an Alan Turing Machine. http://abacus.sourceforge.net/alanturingmachine/ab acus.php
It is basically an idea of a primitive computer with 2 main components. The components include a Tape to hold the data and a Finite State Machine to contain the instructions to process it. This is like the Processor and Memory relationship. The Tape in the demonstration is finite though.
That is way cool. I have to setup my old model trains and see if I can run Doom 3 on them. Just when I thought I would never use those old model trains. This is indeed good news.
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.
If they didn't have the model train, they wouldn't have gotten the idea for the big trains
"Do Slashdot readers know of any mechanical implementations of a truly Universal Turing Machine?"
42.
I feel extremely sorry for you then.
Because it took me only 15 to 20 minutes (including compile time) to get my kernel 'just right'. =)
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.
"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.
What those who want activist courts fear is rule by the people.
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.
This is totally incorrect. Please don't confuse people by bringing quantum computers into this. A quantum computer can be simulated quite happily on a normal computer (albeit with a potential exponential cost in time and memory). Quantum computers are no more universal than a standard, classical universal Turing machine (which is called "universal" for a reason).
But does it run linux?
> A 'proper' Turing machine is supposed to be
> able to take on infinitely many states, OK?
No, a TM has finitely many states. I does have an infinite memory tape. However, the memory is only potentially infinite. Any terminating computation uses only a finite amount of memory.
You can implement a TM just fine, for example in C. If a computation runs out of memory, you just have to get another hard disk... Any computation that will eventually return a result can be computed like that, provided you have enough money for new disks. Any other computation that will never produce a result, will just exhaust your time and money.
Since a Universal TM is just an ordinary TM, this obviously also works for universal TMs.
I choo-choo choose you!
Kind of interesting to see that a Chicken can be trained to play a perfect game of Tic-Tac-Toe.
try { do() || do_not(); } catch (JediException err) { yoda(err); }
You don't "just" have to get another hard disk :-) You also need to be able to store and manipulate arbitrarily large values just to figure out which disk you're addressing. See the infinite monkeys RFC for an example.
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.
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.
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?
"The Sage treasures Unity and measures all things by it" - Lao Tzu
heh.
Turing showed that such a train can never compute whether it will stop at a given station.
Raisinettes are my raison d'etre
> You also need to be able to store and
;-)
> manipulate arbitrarily large values just to
> figure out which disk you're addressing.
That's right. But, in principle, storing arbitrarily large numbers is not difficult. Actually doing it would probably be a nightmare though -- you might need several disks just to store the number of the disk you're addressing
For any slashdot conversation related to the computing field, the odds of "quantum computing" being mentioned increase exponentially proportional to the life of the conversation.
You could turn it into just such a machine by putting ipods on each truck and a wireless network to download data . . . oh no wait Putting magnets on the trucks doesn't help. To work, the movement of the trains has to create the ISM. You could do it by shunting the cars into different sequences and having an infinite number of cars. Wow. Maybe that's how DNA works?
In case you're looking for the Journal the orignal paper by Adam Chalcraft and Michael Greene, see. html#53
http://www.srcf.ucam.org/archim/eureka/backissues
Alan Turing, meet Gomez Addams..
You can't talk about Wikipedia's flaws on Wikipedia
I'm sure this UTM will be able to calculate how often somebody forgets to close a pair of parentheses.
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.
In the posts here, there is some confusion between the notion of a Turing machine simpliciter, and the notion of a Universal Turing machine. For all the technical details including the relationship between Turing machines and finite state automata, people should refer to Hopcroft, J. and Ulman, J. (1969), Formal Languages and Their Relation to Automata, Addison-Wesley, and Hopcroft, J. and Ulman, J. (1979) Introduction to Automata Theory, Languages and Computation,. Also of note is McCulloch, W. and Pitts, W. (1943), "A Logical Calculus of the Ideas Immanent in Nervous Activity" in Bulletin of Mathematical Biophysics, 5/115.
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.
-Vendal Thornheart
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?
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.
Yes, but mine's running Windows, so its a non-deterministic Finite State Machine.
Squirrel!
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:
they seem to act like Turing machines as long as we don't do anything that requires more states than the computer has
You mean they act like a Turing machine as long as we don't do anything that requires a longer tape than the computer has
It's a finite state machine, but still a very cool little project.
There are 2 kinds of people in this world. Those that can keep their train of thought,
How big a layout would one need to operate as a common 8 digit pocket calculator?
UTM is an unsolvable problem. We should keep in mind that since a UTM requires infinitly long tape there does not exits a mechanical implementation, since all our representations of storage are by nature finite. However, we can take memeory to be infinite, (i.e. when we need more space on the tape, we add more memory sticks) thus making a general computer theoretically able to simulate a UTM. Interesting project nonetheless.
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.
Oh shit! I forgot to click "Post Anonymously"...
Strangely the machine gave the error not enough cheese error, and requested a stuffed bear be placed on top of it...
Is this anything like Bistro Mathmatics?
It's not what you know. It's not who you know. It's what you know about who you know.
Scary, just how well some authors have predicted the future. Yes, ok, hindsight and all that...
By far the coolest implementation of a turing machine is the one at the University of Washington. It's steam powered!
It is sort of like saying that Shakespeare is equivalent to a roomful of typing monkeys because you can generate all possible N-page plays in a finite amount of time with a finite number of monkeys.
Perhaps a better analogy would be that you can model the behavior of the planets with epicycles to any degree of precision as long as you add enough epicycles, but it is not a good model of orbits. It's been well over ten years since I've studied this, though, so insert grains of salt as appropriate...
Maniacal turing machine... A cross between The Moon is a Harsh Mistress and 2001: A space Odyssey.
The message on the other side of this sig is false.
Living in Vienna I find it sad to be informed a year after it was exhibit. But monochrom always have some crazy/nice ideas and some of them can be seen in the Museumsquartier (u-bahn station: Volksgarten). Visit it if while you're in Vienna.
b4n
You forgot some places to put your swap file:
RAM
Hard drives
Removable storage
Internet
None of those are infinite, but the last two can be very big indeed.
Hmm, I thought I had a point when I started righting this comment - I guess my brain ran out of states.
Slashdot - Mutual Assured Discussion
In America, a railroad is more of a Finite State Touring Machine.
( Dear God, will he ever halt??? )
I think I can, I think I can, I think I can...