Defining a TM: Tape, Head, and Transitions

From notebook to seven-tuple

In the previous guide the Turing machine was a picture: an endless paper tape, a head parked over one square, and a tiny finite brain that reads what is under the head, writes something back, and shuffles one step left or right. A picture is a fine start, but to prove theorems we need the picture written down without ambiguity — every part named, every rule pinned. The formal definition does exactly that, packing the whole machine into a seven-tuple: (Q, Sigma, Gamma, delta, q0, q_accept, q_reject). It looks heavier than the five-tuple of a DFA, but only two pieces are genuinely new, and both come from the same source — the notebook you can now write on.

Three pieces are old friends. Q is the finite set of states, the machine's small fixed brain. q0 is the start state. And instead of a whole set of accept states, a TM keeps things blunt with just two halting states: q_accept and q_reject, which must be distinct. Sigma is the input alphabet — the symbols your input string is allowed to be made of, exactly as for a finite automaton. So far this is a DFA wearing a slightly different coat. The leap is in the two remaining pieces: a richer alphabet for the tape, and a transition that does more than change state.

The tape alphabet and the blank

The tape is the unbounded notebook: an infinite line of cells stretching away to the right (some textbooks let it run both ways — it makes no difference to what the machine can compute). At the start, your input string sits in the leftmost cells and every other cell is blank. Because the machine can write as well as read, it needs symbols to write that the input never contained — scratch marks, separators, a working 0 or 1. So the cells draw from a bigger pool than Sigma: the tape alphabet Gamma (capital gamma).

Two rules tie Gamma down. First, Sigma is a subset of Gamma — every input symbol is of course a legal tape symbol. Second, Gamma contains one special character that Sigma must NOT contain: the blank symbol, usually drawn as a little box (we write it 'B' here). The blank fills every cell the input did not reach, and it is how the machine senses where its data ends: the first blank to the right of the input marks 'nothing more was given'. Keeping the blank out of Sigma is not fussiness — it is what lets the machine reliably tell genuine input apart from empty scratch space.

One move: write, then step

Now the heart of it. A DFA's transition reads a letter and changes state — that is all it can do. A TM's transition function delta does three things in one indivisible move, because the head it controls can both write and walk. The signature reads delta(q, X) = (p, Y, D), in words: when the machine is in state q and the tape head is reading symbol X, then move to state p, OVERWRITE that cell with symbol Y, and step the head one cell in direction D — either L (left) or R (right). Three effects, one tick of the clock.

Notice how much that single rule buys. Writing Y = X means 'leave this cell alone' (a pure read-and-move, just like a DFA). Writing a different Y is real editing — the machine can leave a breadcrumb, cross out a counted symbol, or build an answer cell by cell. And because the head may step LEFT, the machine can return to data it already passed, the one thing a finite automaton can never do. That combination — rewrite plus go-back — is the entire reason a TM escapes the finite-memory ceiling that trapped DFAs and the single-stack discipline that trapped PDAs. Some textbooks also allow a third direction S (stay put); it is convenient shorthand and adds no power, since a stay can always be faked by stepping right then left.

A configuration: the whole machine in one line

Just as a PDA had its instantaneous description, a Turing machine has a configuration — a complete snapshot you could write on a sticky note to pause the run and resume it identically. To freeze a TM you need three facts: which state it is in, the exact contents of the tape, and where the head is parked. The clever notation folds all three into a single string: write the tape contents, but insert the current state right BEFORE the symbol the head is reading. So 1 0 1 q3 0 1 1 means the tape holds 1011011, the machine is in state q3, and the head sits on the underlined 0 — the cell immediately after where the state name appears.

Why bother with this packing? Because it turns 'the machine runs' into a clean mathematical relation between strings: one configuration YIELDS the next according to delta, exactly the role the move relation |- played for a PDA. The starting configuration is q0 followed by the input, head on the first symbol; from there each step rewrites a cell and slides the state-marker one place left or right. A whole computation is just a chain of configurations, each yielding the next, and reasoning about Turing machines almost always means reasoning about how these snapshots evolve.

delta rules (machine that just marks the first 'a' as 'X' then walks right to a blank):
  delta(q0, a) = (q1, X, R)      in q0 reading a: write X, go right, enter q1
  delta(q1, a) = (q1, a, R)      in q1: skip over a's, keep going right
  delta(q1, B) = (q_accept, B, R)  hit the first blank: accept

Configuration trace on input  a a  (B = blank, head sits on symbol right after the state name):

  q0 a a B ...          start: state q0, head on first a
  X q1 a B ...          wrote X, stepped right, now in q1
  X a q1 B ...          skipped the a, stepped right, still q1
  X a B q_accept ...    read the blank -> accept; head one cell further right

Read 'q0 a a' as: tape is 'aa', head on the a just after q0.

Designing tiny machines, and the standard tricks

With the definition in hand, you can build real machines. Take the language a^n b^n c^n — equal runs of a's, then b's, then c's. A pushdown automaton famously CANNOT recognise this; one stack can balance two groups but not three. A Turing machine can, and the design is a vivid lesson in the core technique called marking: sweep across the tape and cross off one a, one b, and one c per pass (overwrite each with a scratch symbol like X), then return to the left and repeat. If on some pass the counts line up perfectly and only scratch marks remain, accept; if you ever run short of a matching symbol, reject. The back-and-forth — possible only because the head can step left — is what a PDA could never do.

Two more standard tricks round out the toolkit. Multiple tracks: imagine slicing each cell into stacked rows so one cell holds a small tuple of symbols — say (data, mark) — letting a single tape carry a number on the top track and a running annotation underneath. This is the trick of tracks, and it is pure bookkeeping: a tape with k tracks is still an ordinary one-tape machine, just with a tape alphabet of k-tuples. And shuttling: most TM programs are loops that walk the head right to find some feature, do a small edit, then walk it back left to a marker — exactly how copying a string (read a symbol, ferry it to a fresh region) or incrementing a binary number (walk to the low end, flip 1s to 0s until you hit a 0 and flip it to 1) actually run.

1. To increment a binary number, first shuttle the head all the way RIGHT to the least-significant bit (the standard low-order end).
2. Walk LEFT, overwriting each 1 you read with a 0 — these are the carries rippling up — and keep going.
3. The moment you read a 0 (or a blank past the high end), overwrite it with a 1 and stop: the carry has landed.
4. That single left-sweep with an overwrite IS binary increment — a four-state machine that computes a function rather than just answering yes/no.

That last point is worth dwelling on. So far automata only ever answered a yes/no membership question, but a Turing machine that halts with an output left on its tape is computing a FUNCTION — it is acting as a transducer, turning an input string into an output string. Increment, copy, and add are functions, not languages, and the same humble (write, step) rule handles them all. Recognising languages is just the special case where the only outputs that matter are 'accept' and 'reject'. The next guide pins down those two verdicts precisely — and confronts the unsettling third outcome a finite automaton never had: the machine that never halts at all.