Suppose you have lots of train track, and a really fast train and you need to calculate the millionth digit of pi. You aren't one of those people who likes memorizing stuff like that so you figure that you might as well use what you have and get your train to somehow work it out. If that isn't a great introduction, then I don't know what is. Oh, and as a warning, this article is long... but not as long as it looks (if you are looking at the scroll bar thinking that I've rambled heaps more than usual).
For the non-Computer Scientists (what are you doing here?), Turing completeness is a property of a system (like a train set, or a computer, or a ball rolling down a hill, or an ant farm) that means that you can arrange it in such a way that a few moments before the universe is destroyed (or earlier, if you are lucky), it will be able to "calculate" anything that your desktop computer can calculate.
I was originally making a flash application to do all of this, but I couldn't find any useful documentation for the flash API, it was so horribly slow after adding a few pieces of track that I switched to a boring text based interface. The way it works is you 'draw' a track using normal characters, and you place a train somewhere and it goes about its calculations and stops when the train stops. If the train ever runs into a lower case letter, we print that letter. The train starts at the letter "T" (for "train") facing East and stops at the letter "H" (for "halt").
This is an example track
T-----hello-world----\
|
H |
| |
\-----/
You might think this prints out "hello world", but you'd be wrong. Trains can't print out spaces, that would be silly. So it just prints "helloworld" which is much better.
So, this would be useful if you knew that the millionth digit of pi was 7, then you could write:
T-----seven----H
But we need our train to be a bit smarter, so we introduce forks:
H
|
a
|
T-----<
|
b
|
H
This program will print "a", because the < fork always starts pointing up. But, we can change the fork by sending the train backwards through it. So if we send the train in from the south, the fork will now point down:
H
|
a
|
H--b--<
|
T--/
This prints "b", but changes the direction the fork faces.
Pretty lame.
The next fork, looks the same, but faces the other direction. This one first points down, but after you travel through it flips to pointing up (and back down the next time). If you come into this fork from the North or the South, your train crashes and you lose.
T------------\
|
H-a--\ |
| |
>---/
|
H-b--/
Prints "b" (but the next time you go through the fork it will print "a")
The last two forks we have are really boring. One is "V" the other is "^". If you go up through the "V", you always come out pointing right. If you go down through the "^", you always come out pointing left.
So that is it, with this, we can build a computer.
First, we build a single bit of memory:
flip ---------------------\ /--- finished flip
/-V---------------+---/
| | /---------\ |
| | | >--/
| | | |
| | | |
| | \--V------+-----------H zero
| | | |
read T--/ \-----< \-V---------H one
| |
\--------/
We have two "inputs" on the left, a "flip" and a "read". If we go in the "flip", we change the value we are storing (from 1 to 0, or 0 to 1). If we go in the "read", then we come out at either the "zero" or the "one".
So, we can make lots of these memory things (each one is just a single bit). Then we just need to connect them up together. Here is an example of connecting them together, creating a 3-bit counter.
/----overflow--------H------------------------------------\
\-----------------------------------------\ |
| |
/---------------------------------\ | |
| | | |
/--+----------------------\ /------/ | |
| | /-V---------------+---/ | |
| | | | /---------\ | | |
| | | | | >--/ | |
| | | | | | | |
| | | | | | | |
| | | | \--V------+------------------/ |
| | | | | | |
| \----/ \-----< \-V-------------------------------V/
| | | \\
| \--------/ |
| |
| |
\-----------------------------------------\ |
| |
/---------------------------------\ | |
| | | |
/--+----------------------\ /------/ | |
| | /-V---------------+---/ | |
| | | | /---------\ | | |
| | | | | >--/ | |
| | | | | | | |
| | | | | | | |
| | | | \--V------+------------------/ |
| | | | | | |
| \----/ \-----< \-V-------------------------------V/
| | | \\
| \--------/ |
| |
\-----------------------------------------\ |
| |
/---------------------------------\ | |
| | | |
/T-+----------------------\ /------/ | |
| | /-V---------------+---/ | |
| | | | /---------\ | | |
| | | | | >--/ | |
| | | | | | | |
| | | | | | | |
| | | | \--V------+------------------/ |
| | | | | | |
| \----/ \-----< \-V-------------------------------V/
| | | \---------m-----\
| \--------/ |
| |
\------------------------------------------------------------------------/
This will output "mmmmmmmoverflow" (7 m's). Since it is probably quite hard to intuitively see what is going on, the train flips the first memory cell, then goes and reads the result. If the result is "0", then it goes out the bottom path and eventually to the part which prints an "m". If the result was "1", then it goes to the next memory cell, and does the same thing.
In this example, every time we read the memory cell, we do the same thing - if it is "0", we print "m" and go to the start. If it is "1", we flip the next memory cell. To make our computer useful, we need to be able to do different things after reading depending on what state we are in. In this example, we have 4 tracks ("a", "b", "c", and "d"), each of them wants to do something (say, change the value of a memory cell) and then do some other stuff:
/V---------\
--a--/\-------\ \-----finished-a--H
/V-------+-\
T-b--/\-----\ | \-----finished-b--H
/V-----+-+-\
--c--/\---\ | | \-----finished-c--H
/V---+-+-+-\
--d--/\-\ | | | \-----finished-d--H
| | | |
/--< | | |
| \-< | |
| \-< |
| \-/
| /-\
| | |
| \V/
\--do-something-here-and-turn-around---/
With the arrangement of tracks at the top, you can extend it as much as you want, and it will go about its business, then return to the track that it started from. So in this case we print: "bdosomethinghereandturnarounddnuoranrutdnaerehgnihtemosodfinishedb", but if we had entered from the "a" track, we would get the same thing, but with an "a" at the start and end.
This is nearly all of the constructs you need to have a [turing machine] (this would be a 4 state turing machine). The next thing you need to be able to do is to have your subroutine return a value of some description so you can have the different states do different things depending on the value of a memory cell. You can do this by having an extra memory cell for each state. When you do the subroutine, you set each of these memory cells to the outcome. Then, when the subroutine returns, you can read from the state's personal memory cell to get the value. If you look at the way a memory cell works, you can set it to "1" or "0" (as opposed to flipping it) by entering through the corresponding output line.
Since this is way long enough, it can be an exercise for someone who is really bored. Also check out the Turing Train Terminal where a real model train was used to make a computer that can add two 3-bit numbers. Their layout is a lot simpler than all of mine because theirs is specialised, and they don't have the limitations that I imposed by using ascii characters to represent everything.
Get the train track interpreter here. (Ruby, public domain, very hackish - won't be much fun to work on)
RSS