Turing Machines & Undecidability

A Turing machine is not a model of a particular computer. It is the definition of what computation means, and every result in this chapter is a statement about the limits of computation itself rather than about any technology.

The machine is deliberately minimal: a finite control, an infinite tape, and the ability to read, write and move one cell at a time. Nothing about it is efficient, and that is the point — efficiency questions belong elsewhere, while this chapter asks only what is possible at all.

The central discovery is that some things are not possible, and the reason is always the same. A Turing machine can be encoded as a string, so machines can take other machines as input. That self-reference is what makes diagonalisation available, and diagonalisation is what produces every undecidability result here.

So the diagnostic question for any decision problem is: can the problem be turned against itself? If a decider for the problem could be used to build a machine that contradicts its own behaviour, the problem is undecidable.

The second organising fact is that almost every undecidability proof is a reduction rather than a fresh diagonalisation. Prove the halting problem undecidable once, then show that a decider for the new problem would give a decider for halting.

1. The Machine

A Turing machine is a finite control plus an infinite tape divided into cells. A move reads the current cell, writes a symbol, moves the head one cell left or right, and changes state.

The tape is the machine's only memory, and it is unbounded. That single feature separates it from every weaker model: a finite automaton has no tape, and a pushdown automaton has one accessible only at the top.

A configuration is the complete state of a computation: the tape contents, the head position and the current state. A computation is a sequence of configurations, and the machine halts when it enters a halting state.

Three outcomes are possible on any input: halt and accept, halt and reject, or run forever. That third possibility is what makes the whole subject non-trivial.

2. Variants Are All Equivalent

Many variations on the model have been studied, and every one of them recognises exactly the same class of languages.

Nondeterminism is the striking case. For finite automata it adds no power and costs an exponential state blow-up; for pushdown automata it adds power; for Turing machines it adds no power again, but the deterministic simulation takes exponential time.

The simulation explores the nondeterministic machine's computation tree breadth-first, which is why it costs so much. Whether that exponential cost is necessary is exactly the P versus NP question, unresolved and the most famous open problem in the subject.

The Church-Turing thesis states that any function computable by any effective procedure is computable by a Turing machine. It is not a theorem — "effective procedure" is informal — but every model ever proposed has turned out equivalent, which is strong evidence.

3. Recursive and Recursively Enumerable

Two classes must be distinguished precisely, because most exam errors here are confusions between them.

A language is recursive, or decidable, if some Turing machine halts on every input and correctly accepts or rejects.

A language is recursively enumerable, or semi-decidable, if some Turing machine halts and accepts on every member, and may run forever on non-members.

Every recursive language is recursively enumerable; the converse fails.

The relationship between the two is captured by one theorem. A language is recursive if and only if both it and its complement are recursively enumerable.

The proof is a parallel simulation. Run the semi-decider for $L$ and the semi-decider for its complement, interleaving steps. Every string is in exactly one of them, so exactly one machine halts, and its identity gives the answer.

The immediate consequence is that recursively enumerable languages are not closed under complement, since closure would make every semi-decidable language decidable.

The complement of the halting language is the standard example of a language that is not even recursively enumerable.

4. The Halting Problem

The halting problem asks whether a given machine halts on a given input.

It is recursively enumerable, because a universal machine can simulate the encoded machine and accept if the simulation ever halts.

It is not recursive, and the proof is diagonalisation.

Suppose a machine $H$ decides it, answering yes when $M$ halts on $w$ and no otherwise. Build a machine $D$ that, on input $M$, runs $H$ on the pair $(M,M)$ and then does the opposite: if $H$ says $M$ halts on itself, $D$ loops forever; if $H$ says it does not halt, $D$ halts.

Now run $D$ on itself.

If $D$ halts on input $D$, then $H$ said so, and $D$ was built to loop in that case — a contradiction.

If $D$ does not halt on input $D$, then $H$ said so, and $D$ was built to halt in that case — also a contradiction.

Both branches contradict, so $H$ cannot exist.

The argument depends on nothing but the ability to encode a machine as a string and feed it to itself. That self-reference is the whole mechanism, and it recurs in every undecidability result.

5. Reductions

Once one problem is known undecidable, others follow by reduction rather than by fresh diagonalisation.

A reduction from $A$ to $B$ is a computable function converting instances of $A$ into instances of $B$ with the same answer.

The logic then runs in two directions, and keeping them straight is essential.

If $A$ reduces to $B$ and $B$ is decidable, then $A$ is decidable: solve $A$ by converting and asking the $B$-decider.

If $A$ reduces to $B$ and $A$ is undecidable, then $B$ is undecidable: a $B$-decider would give an $A$-decider, contradicting the assumption.

The direction that proves undecidability reduces the known-hard problem to the new one, never the reverse. Reducing the new problem to halting proves nothing about the new problem's difficulty.

The standard technique for showing a language property undecidable is to build, from an instance of halting, a machine whose language depends on whether the original halts.

6. Rice's Theorem

Rice's theorem generalises all of this into one statement.

Any non-trivial property of the language recognised by a Turing machine is undecidable.

A property is non-trivial if some recursively enumerable language has it and some does not. It must be a property of the language, not of the machine.

That second condition is where questions are built. "Does this machine have fewer than 50 states?" is decidable, because it is a property of the machine's description rather than of the language it recognises. "Is the language of this machine empty?" is undecidable, because it is a property of the language and is non-trivial.

Rice's theorem settles a large family of questions instantly.

The last two escape Rice's theorem for different reasons. State counting is a syntactic property of the description. Bounded halting is decidable because simulating 100 steps always terminates — the bound removes the unbounded search that causes undecidability.

7. Other Undecidable Problems

Two further problems are examined by name.

Post's Correspondence Problem asks whether a sequence of domino-like tiles can be arranged so that the top string equals the bottom string. It is undecidable, and it is useful because reducing from it is often easier than reducing from halting when the target problem concerns strings rather than machines.

Many grammar questions are undecidable, and the boundary is worth holding exactly.

The pattern is that questions about one grammar's basic structure are decidable, while comparisons between grammars are not — with the deterministic equivalence result as the notable and deep exception.

8. Worked Examples

Example 1. Prove that the halting problem is undecidable.

Assume a decider $H$ exists, taking an encoded machine $M$ and an input $w$, halting always, and answering yes exactly when $M$ halts on $w$.

Construct $D$ as follows. On input $x$, interpreted as an encoded machine, $D$ runs $H$ on the pair $(x,x)$.

If $H$ answers yes, $D$ enters an infinite loop.

If $H$ answers no, $D$ halts immediately.

$D$ is a legitimate machine, since $H$ is assumed to exist and always halt, and looping is trivially implementable.

Now consider running $D$ on its own encoding.

Suppose $D$ halts on input $D$. Then $H(D,D)$ answered yes, and by construction $D$ loops forever. So $D$ does not halt — contradicting the supposition.

Suppose $D$ does not halt on input $D$. Then $H(D,D)$ answered no, and by construction $D$ halts immediately. So $D$ halts — again contradicting the supposition.

Both cases are impossible, so the assumption that $H$ exists must be false.

The only assumption used was that machines can be encoded as strings and fed to themselves. Nothing about tapes, states or transitions entered the argument, which is why the same technique applies far beyond Turing machines.

Example 2. Show that the problem "does machine $M$ accept the empty string" is undecidable.

Reduce from halting. Assume a decider $E$ for this problem exists.

Given an arbitrary instance of halting — a machine $M$ and an input $w$ — construct a new machine $N$ as follows.

$N$ ignores its own input entirely. It writes $w$ on its tape, simulates $M$ on $w$, and if that simulation halts, $N$ accepts.

Now consider what $N$'s language is.

If $M$ halts on $w$, then $N$ accepts every input, including the empty string. So $N$ accepts the empty string.

If $M$ does not halt on $w$, then $N$ never reaches its accepting step for any input, so its language is empty. It does not accept the empty string.

So $N$ accepts the empty string exactly when $M$ halts on $w$.

Running $E$ on $N$ therefore answers the halting question for $M$ and $w$. Since $E$ always halts by assumption, this would decide the halting problem.

The halting problem is undecidable, so $E$ cannot exist.

Note the direction of the reduction. The known-undecidable problem was converted into the new one, which is what proves the new one hard. Converting the new problem into halting would have proved nothing.

Example 3. Which of these are decidable: whether a Turing machine has an even number of states; whether it halts on all inputs; whether it halts within 50 steps on input $w$?

Even number of states: decidable. This is a property of the machine's description, not of the language it recognises. Count the states in the encoding and check parity. Rice's theorem does not apply, because Rice concerns properties of $L(M)$.

Halts on all inputs: undecidable. This is the totality problem. It is a non-trivial property — some machines halt on everything and some do not — and it depends only on the machine's behaviour rather than its syntax. It is undecidable, and in fact is not even recursively enumerable, since no finite amount of simulation can confirm that a machine halts on all of infinitely many inputs.

Halts within 50 steps: decidable. Simulate for exactly 50 steps and report whether the machine halted. The simulation always terminates because the step count is bounded, which removes the unbounded search entirely.

The general principle is that bounded questions are decidable and unbounded ones usually are not, and that syntactic properties of the description are always decidable however complicated they look.

Example 4. Apply Rice's theorem to decide whether "is $L(M)$ regular" is decidable.

Check the two conditions Rice's theorem requires.

First, is it a property of the language rather than the machine? Yes. Whether $L(M)$ is regular depends only on the set of strings accepted, not on how many states the machine has or how it is written. Two machines with the same language always agree on this property.

Second, is it non-trivial? A property is non-trivial if at least one recursively enumerable language has it and at least one does not.

Some machine recognises the empty language, which is regular, so the property is sometimes true.

Some machine recognises $\{a^n{b}^n\}$, which is recursively enumerable and not regular, so the property is sometimes false.

Both conditions hold, so Rice's theorem applies and the property is undecidable.

Notice how little work this required. Without Rice, proving it would need an explicit reduction from halting, constructing a machine whose language is regular exactly when some other machine halts. Rice packages that construction once and for all.

Example 5. Explain why the complement of the halting language is not recursively enumerable.

The halting language is recursively enumerable: a universal machine simulates the encoded machine and accepts if the simulation halts.

Suppose its complement were also recursively enumerable.

Then both the language and its complement would be semi-decidable, and by the parallel-simulation theorem the language would be recursive — that is, decidable.

But the halting language is undecidable, as diagonalisation established.

The contradiction shows the complement cannot be recursively enumerable.

Intuitively, the asymmetry is about what can be confirmed. Halting can be confirmed by observing it: simulate, and if the machine stops, you know. Not halting cannot be confirmed by any finite observation, because however long the simulation runs without stopping, it might stop on the next step.

That asymmetry between confirmable and unconfirmable is exactly the difference between recursively enumerable and its complement.

Example 6. Is the language of a Turing machine that accepts exactly the strings of length 5 decidable to recognise?

Read the question carefully: it asks whether the property "$L(M)$ equals the set of strings of length 5" is decidable, given $M$.

Apply Rice's theorem.

Is it a property of the language? Yes — it is a statement about which strings are accepted, and two machines with identical languages agree on it.

Is it non-trivial? Some machine has exactly that language, so the property is sometimes true. Some machine has the empty language, which is not the set of length-5 strings, so it is sometimes false.

Rice's theorem applies, so the property is undecidable.

Contrast this with a superficially similar question: "does $M$ accept the specific string $aaaaa$ within 100 steps?" That is decidable by bounded simulation.

The difference is the quantifier. Checking one string with a step bound is a finite computation. Determining the entire language requires reasoning about infinitely many inputs with no bound, and that is precisely what no decider can do.

Summary

A Turing machine is the definition of computation: a finite control and an unbounded tape, with three possible outcomes on any input, the third being that it never halts.

Every variant — multi-tape, multi-track, two-way, multi-dimensional, nondeterministic — recognises exactly the same languages. Nondeterminism costs exponential simulation time, and whether that cost is necessary is the P versus NP question.

Recursive means a machine always halts with a verdict; recursively enumerable means it halts on members and may loop on non-members. A language is recursive exactly when it and its complement are both recursively enumerable, which is why the recursively enumerable class fails closure under complement.

The halting problem is recursively enumerable and undecidable. The proof is diagonalisation and uses only the fact that a machine can be encoded and fed to itself.

Reductions transfer undecidability. To prove a new problem undecidable, reduce the known-hard problem to it, never the reverse.

Rice's theorem states that every non-trivial property of the language recognised by a machine is undecidable. Properties of the machine's description escape it, and so do questions with an explicit step bound, because bounded simulation always terminates.

Post's Correspondence Problem is undecidable and is often the easier source for reductions about strings.

For context-free grammars, membership, emptiness and finiteness are decidable, while ambiguity, equivalence and intersection emptiness are not — with deterministic equivalence as the deep exception.

The complement of the halting language is not even recursively enumerable, because halting can be confirmed by observation while non-halting cannot be confirmed by any finite computation.