Encoding Turing Machines and the Undecidability of Acceptance

The acceptance problem takes two inputs, a machine and a string, and asks whether the machine accepts the string. Three facts make it the central undecidable problem. Machines are finite objects, so they can be written down and fed to other machines. The step relation of a machine is trivially decidable, so simulation is mechanical. And a machine that decides acceptance can be turned against itself. The first fact is an encoding claim, and it is the part most often glossed over in proofs that cite the other two.

Naming a machine with a finite string

A Turing machine has a finite state set, a finite tape alphabet, and a finite transition table. All three can be written as sequences of integers. The standard reduction fixes the tape alphabet to two symbols plus a blank: a machine over a larger alphabet can be simulated by one over binary by replacing each symbol with a fixed-width block of bits and expanding every transition into a sequence of steps that reads and writes a block. The simulation costs a constant factor per cell, with the constant depending on the size of the original alphabet, and the class of computable functions is unchanged. It is therefore enough to encode machines whose tapes hold zeros, ones, and blanks.

The step relation is local. If the transition function maps (q, a) to (q′, b, R) and the configuration is u q a v, the next configuration is u b q′ v. Moving left off the left end appends a blank to u; moving right past the end of v appends a blank. Every step is decidable, and constant time if the tape is stored as two stacks around the head position.

What remains is a serialization format. Number the states from 1 to k, make 1 the start state and reserve two numbers for the accepting and rejecting states, and write each transition as a five-field tuple: current state, read symbol, next state, written symbol, direction. Separate fields within a tuple and separate tuples from each other with distinct delimiters, then concatenate. With a fixed enumeration of states and symbols and a fixed order on tuples, the map from machines to strings is injective, and its image is decidable: a parser reads the string once and either produces a well-formed machine or rejects it. Parsing is linear in the length of the string, and the resulting description is a constant factor larger than the number of transitions.

Two consequences follow immediately, and they are worth separating. First, machines can be enumerated. Order all strings by length, and within a length lexicographically, keep those that parse, and every machine appears exactly once. The set of machines is countably infinite. Second, a machine can be given to another machine as input, because its description is a string over the same alphabet machines read. This is what separates Turing machines from finite automata in a way that matters for the rest of the subject: an automaton’s description can also be encoded, but the encoding does not normally serve as an input the automaton itself consumes.

The notation ⟨M⟩ stands for the encoding of M. The angle brackets mean “some fixed encoding”, and the proofs depend only on the properties above, never on the particular delimiter choice.

A configuration is the whole state of the computation

At any moment, everything that determines the future of a computation is the tape contents, the head position, and the current state. A record of those three is a configuration, also called an instantaneous description. For a machine whose tape is infinite in one direction, write the configuration as u q v, where u is the string left of the head, q is the state, and v is the string from the head position rightward.

The step relation is local, as described above. A computation is a path C₀ ⊢ C₁ ⊢ … through a graph whose vertices are configurations. That graph is infinite in general, because there are infinitely many possible tape contents, and the acceptance question is whether an accepting configuration is reachable from the start configuration. For a deterministic machine every vertex has at most one successor, so the graph is a union of paths rather than a branching tree. Reachability along a single path is the entire problem, and it is decidable for any fixed step bound and undecidable in the unbounded case. The deterministic, singly branching structure is why the difficulty is not combinatorial explosion: there is exactly one path to follow, and the trouble is that it may never end.

def step(delta, state, tape, head):
    """tape: dict from cell index to symbol; head: integer index."""
    a = tape.get(head, 'B')
    if (state, a) not in delta:
        return None                     # no transition: the machine halts
    nxt, write, move = delta[(state, a)]
    tape[head] = write
    return nxt, head + (1 if move == 'R' else -1)

def run(delta, tape, state='start', head=0, limit=None):
    steps = 0
    while state not in ('accept', 'reject'):
        if limit is not None and steps >= limit:
            return 'timeout'            # bounded simulation cannot prove non-halting
        r = step(delta, state, tape, head)
        if r is None:
            return 'reject'             # halting without accepting is rejection
        state, head = r
        steps += 1
    return state

A computation is a path C₀ ⊢ C₁ ⊢ … through a graph whose vertices are configurations. That graph is infinite in general, because there are infinitely many possible tape contents, and the acceptance question is whether an accepting configuration is reachable from the start configuration. For a deterministic machine every vertex has at most one successor, so the graph is a union of paths rather than a branching tree. Reachability along a single path is the entire problem, and it is decidable for any fixed step bound and undecidable in the unbounded case. The deterministic, finitely branching structure is why the difficulty is not combinatorial explosion: there is exactly one path to follow, and the trouble is that it may never end.

The universal machine and the cost of simulation

A universal machine U takes ⟨M, w⟩ and runs M on w. On a two-tape machine this is direct. One tape holds ⟨M⟩ and is read only; another holds the simulated tape with a marker for the simulated head; a work track holds M’s current state number. Each simulated step requires locating the transition for the current state and scanned symbol, which costs a scan of the description, so simulating t steps of M costs a number of U steps proportional to t times the length of ⟨M⟩. That factor is a genuine property of interpreters, not an artifact of the proof: an interpreter pays a dispatch cost per interpreted instruction, and the cost grows with the size of the program’s control structure.

U recognizes the set A_TM = {⟨M, w⟩ : M accepts w}. It does not decide it, because when M loops on w, U loops on ⟨M, w⟩. The gap between recognizing and deciding is the subject of Recognizers, Dovetailing, and Complement Asymmetry, and it is what makes the next section necessary: a decider for acceptance cannot be built by simulation alone.

The diagonal argument, step by step

Suppose H decides acceptance: H(⟨M, w⟩) accepts when M accepts w, rejects otherwise, and always halts. Build D as follows. On input x, D checks whether x parses as a machine encoding; if it does not, D rejects. Otherwise D runs H on the pair consisting of x and x, that is, on the encoding of the machine x applied to its own description. If H accepts, D rejects; if H rejects, D accepts. D halts on every input because H does.

D is a Turing machine: it is H composed with a finite parse check and a swap of the accept and reject states. The swap modifies the finite control by a constant number of states. So D has an encoding; call it d.

Run D on d. The definition of D says that D accepts d exactly when H rejects the pair (d, d). The specification of H says that H accepts (d, d) exactly when the machine encoded by d, which is D, accepts d. Combining the two, D accepts d if and only if D does not accept d. No truth value satisfies that, so H cannot exist.

Two hypotheses carry the proof, and every diagonal argument needs both. D must be effective: its description must exist and be constructible from H’s description. And the encoding must be total on machines: D must be applicable to its own description, which requires that encodings are strings over the input alphabet and that D handles arbitrary strings, not only well-formed ones. Drop either and the contradiction evaporates.

Counting gives existence; diagonalization gives a witness

Cantor’s argument supplies a cheaper proof that some language is undecidable. The set of all languages over a finite alphabet is uncountable, since each language is a subset of the countable set of strings and the power set of a countable set is uncountable. The set of machines is countable. So machines cannot cover all languages. This shows that undecidability exists without exhibiting a single undecidable language.

Diagonalization does more: it names A_TM and proves it undecidable, which makes it usable as the source of the reductions described in Mapping Reductions and the Halting Problem. Both arguments share a limitation that shapes how the result should be read. Undecidability is a statement about a whole function, not about any finite collection of instances: every finite language is decidable by a lookup table, so no individual input is hard, and a decider’s obligation is the unbounded quantifier over inputs together with the unbounded computations those inputs can provoke.

One of those two unbounded quantities can be bounded, and the result is worth stating because it locates the difficulty precisely. Fix a machine with k states, tape alphabet size b, and consider only computations that use at most s tape cells. A configuration is determined by the state, the head position among at most s cells, and the tape contents, so there are at most k · s · b^s of them. A deterministic computation longer than that must repeat a configuration, and a machine that repeats a configuration loops forever. So halting within a known space bound is decidable: simulate for at most k · s · b^s steps and report the outcome. What this shows is where the unbounded quantifier sits. Undecidability requires unbounded space as well as unbounded time: the bound above is usable only once a space limit s is in hand, and for a general machine no such limit can be read off the description, so a simulation that must decide halting cannot stop at a bound it has no way to compute.