Joel Yliluoma wrote:

> Have to note that I have no idea how that machine
> that is represented as a pile of gold supposedly works.

The "pile of gold" represents the activity of the machine (for a 
specific initial configuration). The little boxes and dials represent 
the design of the machine itself.

Essentially, you have a "tape" that extends to infinity in both 
directions. That tape is divided up into squares, each of which can be 
white, yellow or orange (in this particular example). The machine itself 
can be in one of two different modes or "states". The machine has a 
read/write head that it can shuffle over the tape.

At each point in time, depending on which state the machine is in and 
what colour square is under the read/write head, the machine changes to 
a new state (possibly the one it was already in), writes a new colour to 
the square on the tape (possible the same colour that was already 
there), and moves the tape head 1 square left or right.

Then we repeat the operation all over again. And that's how the machine 
runs, basically.

Each row in the graph represents the contents of the tape at a 
particular point in time. What you're looking at is actually the 
*compressed* graph; generally Turing machines spend ages winding the 
head back and forward across the tape without actually changing 
anything. The compressed graph only shows the tape when something 
actually *changes*. This makes the graph much smaller, while still 
showing you the essential features.

If any of that made any sense...



(Turing machines are interesting because you can design one such that if 
you encode two numbers into patterns of coloured squares and put them on 
a tape, and then run the machine over the tape, eventually it produces 
the sequence of coloured squares representing the sum of the original 
two numbers. In other words, you can design a Turing machine that 
performs mathematical addition. And many other operations besides.

Now, the *universal* Turing machine is just a Turing machine that can 
simulate any possible Turing machine. Since you can build a Turing 
machine for any possible algorithm, it follows that a universal Turing 
machine can perform any possible algorithm...)

Post a reply to this message