Turing’s Machine

No, sorry, I don’t mean the Bletchey Bombe machine that cracked the Enigma cipher. I mean his theoretical machine; the one I’ve been referring to repeatedly the past few weeks. (It wasn’t mentioned at the time, but it’s the secret star of the Halt! (or not) post.)

The Turing Machine (TM) is one of our fundamental definitions of calculation. The Church-Turing thesis says that all algorithms have a TM that implements them. On this view, any two actual programs implementing the same algorithm do the same thing.

Essentially, a Turing Machine is an algorithm!

The abstract Machine that Turing conceived is a way of defining what can be calculated or — more specifically — what you can write an algorithm to do. The idea is instrumental in his halting proof.

It is possible to build actual (or virtual) Turing Machines. Creating a virtual one in software is a common exercise for undergraduate Computer Science students. Those with a mechanical bent sometimes make physical TMs!

Or virtual 3D models of Turing Machines!

One problem is that a TM assumes infinite resources, so you can never make a perfectone. Compounding the problem, as calculation devices go, they’re hideously inefficient, so they really need infinite resources (and infinite time)!

Conceptually a TM is a tape (infinite in length!) along which a machine moves (or the tape moves past the machine). The tape, at regular intervals, is marked or not. The machine controls tape movement (back and forth), can read the marks, and can change them (from marked to not or vice-versa).^[1]

What makes each TM an algorithm is an internal state table telling the machine what to do next depending what’s on the current position of the tape.

Which may cause you might ask: “Hey, wait! If the tape only has a mark or not, how much can the machine have to do? I see only two options.”

You are correct. There are only two options. Marked; not marked. The magic lies in what we might think of as the “back trail” — all the steps the machine does to get to that point on the tape.

To illustrate this, imagine we’ve been placed in a maze, at the entrance (the red square in the upper left).

We’re going to use the left-hand rule to find the exit.

We’ll assume our starting position is facing outwards (to the left, or west, on the maze map, as if we’d backed into the maze).^[2]

The algorithm goes like this:

1. Turn 90° to our right.
2. Facing a wall? If Yes Goto #1 (else continue).
3. Go forward one space.
4. Is this the exit? If Yes Solved! (else continue).
5. Turn 90° to our left.
6. Goto #2.

It’s the equivalent of walking through the maze with our left hand always touching the wall on the left. The first couple of steps into the maze look like this:

• Turn right (now facing north).
• Facing a wall? Yes. Goto #1.
• Turn right (now facing east).
• Facing a wall? No! Continue.
• Go forward one space.
• Is this the exit? No. Continue.
• Turn left (now facing north again).
• Goto #2.
• Facing a wall? Yes. Goto #1.
• Turn right (now facing east).
• Facing a wall? No! Continue.
• Go forward one space.

It’s taken a lot of algorithm steps to move two cells into the maze, but eventually the algorithm will take us to the exit (green square in the lower right).

The algorithm explores all the grey squares. The darker ones are the direct path to the exit, which is always the inner edge of the explored area.

The point is that at any given point in the maze, we’re faced with the question, “Am I looking at a wall?”

That’s the same question as, “Is there a mark on the tape?”

But there was also the question, “Am I at the exit?”

That can be rephrased as, “Am I looking at a wall (with an exit)?” Now the overall question is, “Am I looking at a wall? If so, does that wall have an exit?”

This actually models the point about “back trail” in the small. To ask whether the wall is an exit, we first must ask whether it’s a wall. The mark meaning “exit” doesn’t mean anything except following a mark meaning “wall”.

In the large, the maze shows how following a series of (pairs of) marks not only travels a path through the maze, but locates the exit.^[3]

More to the point, where we are in the maze reflects all the steps taken to get to that point. This is indicative of any process. The state constantly evolves and — at any given point — reflects the steps that got it there.^[4]

Something else to note is that, while the algorithm had only six steps, the execution of that algorithm involves a lot of steps. Those six steps get repeated many times, a common characteristic of algorithms.^[5]

§

[click for big]

The flowchart is shown to the right.

The maze-solving algorithm we just considered had two decision points (wall? exit?). It also had steps done between those points.

Very often, when we characterize a system, we only care about the system’s state when we need to make a decision. The intermediate states between decisions don’t matter because they don’t affect anything. We can ignore them.

This is the key difference between a typical flowchart (such as we’ve been looking at so far) and a typical state diagram (which we’ll get to in a bit).

The vending algorithm also has two decision points (in yellow). The first asks whether enough coins have been tendered for a purchase. The second asks whether change is owed.

But this algorithm has two very important other points: Wait states (in cyan). The maze algorithm never waited, it just plowed through the maze.

A long wait state!

Conceptually, a wait can be viewed as a constant loop — the very loop drivers hate from passengers: “Are we there yet?” “Are we there yet?” “Are we there yet?” “Are we there yet?”

At some point the answer is, “Yes, damnit!” and the loop exits.^[6]

The main point here is that the vending algorithm has two stable states (the wait states) and a number of transitory states. A stable state is a state where a process stops until some event prompts (or allows) it to continue.

The system performs transitory steps “at its own speed” (so to speak) but stops at stable steps. This is another characteristic of algorithms.

§

So far we’ve looked at flowcharts — which are state diagrams — but often include more transitory states (especially if important to understanding the algorithm).^[7]

State diagrams often lump transitory states between stable states into a single task performed between those stable states. That reduces the diagram to functional skeleton that outlines the algorithm’s behavior.

Below is a simple state diagram for an algorithm that identifies valid email addresses in text. Each state (cyan box) waits for another character of text. (We can imagine, for example, it’s monitoring someone’s typing.)

Any illegal character — one that couldn’t possibly be in an email address — resets the process to the beginning. So long as it gets legal characters, it progresses through the states.

If it gets to the final state (far right), the next illegal character it gets signals the end of the email. (Even a space will do it.)

Each state change (black lines with arrows) involves some number of transitory states. For example, the algorithm might be filling a buffer with the characters it finds. A jump back to restart needs a step clearing that buffer.

This isn’t a perfect algorithm (but a better one has more boxes and lines). For instance, it believes an email address can end with a period! And it has no problem with multiple periods with nothing between them. Both are illegal in an email address.

§

This may seem to have gotten away from Turing’s Machine, but each of the three examples we’ve studied is a Turing Machine.

The Machine part is trivial. It just reads, moves, or writes, the tape.

It’s the flowchart wired into the machine that makes it do what it does. The combination of that flowchart and a machine that executes it defines what we mean by calculation or computation.

[If you’d like to know more about how the flowchart is wired into the TM, I’ve just started a series on my programmer blog that explores state engines (aka TMs). Most (or at least much) of the first article should be reasonably accessible even to non-programmers.]

^[1] If that sounds familiar, it may be from all the times I’ve said that computers read numbers and write numbers (and do math). Reading and marking the tape is the same thing. Also, that the tape is marked or not corresponds directly to binary one and zero. This is computing at its lowest level!

^[2] As is common with maps, left is east, up is north, and so forth.

^[3] Assuming paths do not reconnect once they branch away — that generates loops in the maze graph which can defeat the left-hand rule.

^[4] There are multiple paths that can take you to a given spot in a maze, so a given state does not necessarily imply a specific back trail of states.

^[5] In fact, the ability to iterate (loop) is a required characteristic of code — of anything capable of expressing an algorithm.

^[6] Some computer algorithms (parts of them) operate exactly like that. The code enters a loop of constantly asking if input is available.

A better architecture allows the process to enter a quiescent “sleep” state. Then input interrupts wake it up to process the input.

^[7] We’re talking about flowcharts used for visualizing and discussing algorithms, so irrelevant details are just noise. The abstract flowchart for a full algorithm necessarily has all the steps.