Computability Theory — Turing Machines and the Halting Problem

⚡ Key Takeaways

One-line statement: A Turing machine is a formal model of computation, and the Halting Problem — deciding whether a given machine halts on a given input — is provably undecidable. Key result: No algorithm can decide, for all programs and inputs, whether the program will eventually stop. Where it applies: foundations of computer science, logic, program verification, complexity theory. Who/when: Alan Turing, 1936, with parallel work by Alonzo Church.

💡 The Core Insight

Computation can be made fully precise with a finite, mechanical device. Once it is precise, we can ask self-referential questions: feed a machine a description of itself. The Halting Problem is undecidable because a hypothetical "halt-detector" could be wired into a machine that does the opposite of what the detector predicts about itself — a contradiction. This diagonalization is the same logical engine behind Cantor's Theorem and Gödel's Incompleteness Theorems.

DefinitionTuring Machine

A (deterministic, single-tape) Turing machine is a 7-tuple

1

\quad M = (Q,\ \Sigma,\ \Gamma,\ \delta,\ q_0,\ q_{\text{accept}},\ q_{\text{reject}})

Derivation hint: This is a definition, not a derivation; each component is fixed by listing the finite data the machine needs. where:

$Q$ is a finite set of states;
$\Sigma$ is the finite input alphabet, with the blank symbol $\sqcup \notin \Sigma$ ;
$\Gamma \supseteq \Sigma \cup \{\sqcup\}$ is the finite tape alphabet;
$\delta : (Q \setminus \{q_{\text{accept}}, q_{\text{reject}}\}) \times \Gamma \to Q \times \Gamma \times \{L, R\}$ is the transition function;
$q_0 \in Q$ is the start state;
$q_{\text{accept}}, q_{\text{reject}} \in Q$ are the distinct accepting and rejecting halting states.

A transition $\delta(q, a) = (q', b, D)$ means: in state $q$ reading symbol $a$ , write $b$ , move the head one cell in direction $D \in \{L, R\}$ , and switch to state $q'$ .

DefinitionConfiguration and Computation

A configuration records the entire instantaneous state of $M$ : the tape contents, head position, and current state. We write it as $u\, q\, v$ , where $uv$ is the non-blank tape, $q$ is the current state, and the head reads the first symbol of $v$ . The yields relation $\vdash$ describes one step:

2

\quad u\, q\, av \ \vdash\ u\, b\, q'\, v \quad\text{when } \delta(q,a)=(q',b,R)

Derivation hint: Apply the transition function — write $b$ over $a$ , move the head right (so the boundary advances), and update the state; the leftward case is symmetric. $M$ halts on input $w$ if the computation starting from $q_0 w$ reaches $q_{\text{accept}}$ (accepts) or $q_{\text{reject}}$ (rejects). Otherwise it loops (runs forever).

DefinitionDecidable and Recognizable Languages

A language $L \subseteq \Sigma^*$ is:

Turing-recognizable (recursively enumerable, r.e.) if some $M$ accepts exactly the strings in $L$ (and may loop or reject on strings not in $L$ );
Turing-decidable (recursive) if some $M$ accepts every string in $L$ and rejects every string not in $L$ — i.e. $M$ halts on all inputs.

3

\quad L \text{ decidable} \iff L \text{ recognizable and } \overline{L} \text{ recognizable}

Derivation hint: ( $\Rightarrow$ ) a decider for $L$ also decides $\overline{L}$ by swapping accept/reject. ( $\Leftarrow$ ) run recognizers for $L$ and $\overline{L}$ in parallel (dovetailing); exactly one halts, telling you membership.

DefinitionThe Halting Problem

Encode each Turing machine $M$ as a string $\langle M \rangle$ over a fixed alphabet (a standard, computable encoding). The Halting Problem is the language

4

\quad H_{\text{TM}} = \{\, \langle M, w\rangle \ :\ M \text{ is a TM that halts on input } w \,\}

Derivation hint: $\langle M, w\rangle$ is a single string pairing a machine description with an input; "halts" means reaching $q_{\text{accept}}$ or $q_{\text{reject}}$ in finitely many steps. A closely related set is the acceptance problem $A_{\text{TM}} = \{\langle M,w\rangle : M \text{ accepts } w\}$ . Both are undecidable.

TheoremUndecidability of the Halting Problem — Turing 1936

$H_{\text{TM}}$ is Turing-recognizable but not Turing-decidable. Equivalently, there is no Turing machine that, given $\langle M, w\rangle$ , always halts and correctly outputs whether $M$ halts on $w$ .

ProofDiagonalization for

A_{\text{TM}}

We prove $A_{\text{TM}} = \{\langle M, w\rangle : M \text{ accepts } w\}$ is undecidable; the argument for $H_{\text{TM}}$ is identical in spirit.

Step 1 — Assume a decider exists. Suppose, for contradiction, a Turing machine $H$ decides $A_{\text{TM}}$ . Then $H$ always halts, with

5

\quad H(\langle M, w\rangle) = \begin{cases} \text{accept} & \text{if } M \text{ accepts } w \\ \text{reject} & \text{if } M \text{ does not accept } w \end{cases}

Derivation hint: This is the assumed specification of $H$ ; the whole proof derives a contradiction from it.

Step 2 — Build the contrary machine. Define a new machine $D$ that takes a single machine description $\langle M \rangle$ as input and does the following: 1. Run $H$ on $\langle M, \langle M\rangle\rangle$ (i.e., ask: does $M$ accept its own encoding?). 2. If $H$ accepts, then $D$ rejects. If $H$ rejects, then $D$ accepts. Because $H$ always halts, $D$ always halts. Formally:

6

\quad D(\langle M\rangle) = \begin{cases} \text{accept} & \text{if } M \text{ does not accept } \langle M\rangle \\ \text{reject} & \text{if } M \text{ accepts } \langle M\rangle \end{cases}

Derivation hint: $D$ simply flips $H$ 's answer on the diagonal input $\langle M, \langle M\rangle\rangle$ — that flip is what creates the contradiction.

Step 3 — Feed $D$ its own description. Run $D$ on input $\langle D \rangle$ . Substituting $M = D$ in [6]:

7

\quad D(\langle D\rangle) = \begin{cases} \text{accept} & \text{if } D \text{ does not accept } \langle D\rangle \\ \text{reject} & \text{if } D \text{ accepts } \langle D\rangle \end{cases}

Derivation hint: This is just [6] with the machine $M$ chosen to be $D$ itself — the self-reference step.

Step 4 — Contradiction. Equation [7] says $D$ accepts $\langle D\rangle$ exactly when $D$ does not accept $\langle D\rangle$ . Both possibilities are impossible. Hence the decider $H$ cannot exist, so $A_{\text{TM}}$ is undecidable. $\blacksquare$

Step 5 — Transfer to halting. If we could decide $H_{\text{TM}}$ , we could decide $A_{\text{TM}}$ : given $\langle M, w\rangle$ , first ask whether $M$ halts on $w$ ; if it loops, output "reject"; if it halts, simulate $M$ on $w$ to completion and report its accept/reject answer. Since $A_{\text{TM}}$ is undecidable, $H_{\text{TM}}$ must be too (a reduction $A_{\text{TM}} \le_m H_{\text{TM}}$ ).

∎

⚠️ Common mistake

The proof does not say halting is undecidable for every machine. For many specific machines we can easily prove they halt or loop. Undecidability is a statement about the general decision procedure — no single algorithm works for all $\langle M, w\rangle$ . The recognizability gap is also crucial: $H_{\text{TM}}$ is recognizable (just simulate $M$ on $w$ and accept if it halts), but $\overline{H_{\text{TM}}}$ is not recognizable — there is no way to confirm "loops forever" in finite time.

mathematician · Alan Turing | 1912–1954

In his 1936 paper "On Computable Numbers, with an Application to the Entscheidungsproblem," Alan Turing introduced the abstract machines that bear his name to make the notion of "mechanical procedure" mathematically exact. His goal was to settle Hilbert's Entscheidungsproblem — whether first-order logic has a decision procedure. By showing the Halting Problem undecidable and reducing it to logical decidability, he proved no such procedure exists. Turing later did foundational work in codebreaking at Bletchley Park, in the theory of computing machinery, and in mathematical biology. His name is honored by the Turing Award, computing's highest distinction.

🧠 Intuition

Think of trying to write a universal "freeze detector" for programs. You want a function `halts(program, input)` that returns `true`/`false` and never itself hangs. The diagonal trick is to write a short, sneaky program `paradox` that calls `halts` on itself and then deliberately misbehaves: if `halts` predicts it will stop, `paradox` enters an infinite loop; if `halts` predicts it will loop, `paradox` stops immediately. Now `halts`' prediction about `paradox` is wrong no matter what — the program is built to contradict the oracle examining it. The escape valve "well, just say I don't know" is closed by assumption: a decider must always answer. The only consistent conclusion is that the perfect decider cannot exist.

Figure

The diagonalization that defeats any halting-decider

```svg

```

ExampleA machine we CAN analyze — counting steps

Given: A Turing machine $M_1$ over $\Sigma=\{1\}$ that, on input $1^n$ (a string of $n$ ones), repeatedly erases the rightmost $1$ and moves left, halting when the tape is blank. We want to confirm it halts on $w = 1^5$ and count steps.

Steps: 1. Each "erase + scan back to the right end" pass removes exactly one $1$ . 2. With $n = 5$ , the machine performs $5$ erasure passes, then one final pass detecting the blank tape and halting. 3. Pass $k$ scans across roughly $(n-k+1)$ cells out and back, so the total step count is on the order of

8

\quad T(n) \;=\; \sum_{k=1}^{n} 2(n-k+1) + c \;=\; n(n+1) + c \;=\; n^2 + n + c

Derivation hint: Sum the round-trip scan lengths $2,4,\dots,2n$ over the passes; the constant $c$ accounts for the final halting check. 4. For $n=5$ : $T(5) = 25 + 5 + c = 30 + c$ steps.

Answer: $\boxed{M_1 \text{ halts on } 1^5 \text{ in } \Theta(n^2) = 30 + c \text{ steps}}$ . This is decidable for this specific machine — undecidability concerns no single algorithm working for all machines.

ExampleReducing a real question to the Halting Problem

Given: A claimed program `findCounter` that searches for the smallest even integer $> 2$ that is not a sum of two primes, halting if it finds one (a counterexample to the Goldbach Conjecture) and looping otherwise.

Steps: 1. Form $\langle \texttt{findCounter}, \varepsilon\rangle$ where $\varepsilon$ is the empty input. 2. "Does `findCounter` halt?" $\iff$ "Does a Goldbach counterexample exist?" 3. If we had a halting-decider $H$ , we could feed it $\langle \texttt{findCounter}, \varepsilon\rangle$ and settle Goldbach mechanically. 4. We possess no such decider (Theorem above) — and even unconditionally, no algorithm settles all such "does a search halt?" questions.

Answer: $\boxed{\text{A universal halting-decider would resolve open problems like Goldbach — strong evidence it cannot exist.}}$ Many deep mathematical conjectures can be encoded as halting questions of small programs.

⚠️ Common mistake

"Undecidable means we can never decide any particular instance." False. We can often decide individual cases. Undecidability forbids a single, total algorithm covering all inputs.

"A faster computer or quantum computer could solve it." False. The proof is independent of speed or hardware — it is purely logical. Quantum computers compute the same class of functions as Turing machines (the Church-Turing Thesis is not violated).

"Recognizable equals decidable." False. $H_{\text{TM}}$ is recognizable but not decidable. Recognizers may loop forever on non-members; deciders never loop.

CounterexampleA recognizable language whose complement is NOT recognizable

Consider $A_{\text{TM}}$ itself. It is recognizable: a universal Turing machine $U$ simulates $M$ on $w$ and accepts if $M$ accepts. But $\overline{A_{\text{TM}}}$ is not recognizable. If it were, then by [3] $A_{\text{TM}}$ would be decidable — contradicting the theorem. This concretely shows the class of recognizable languages is not closed under complement, and separates recognizability from decidability.

connection

The Halting Problem sits at the center of a web of foundational results.

It is the canonical undecidable problem against which others are compared via Mapping Reductions: to show $L$ undecidable, reduce $A_{\text{TM}}$ or $H_{\text{TM}}$ to $L$ .
Rice's Theorem generalizes it: every non-trivial semantic property of programs is undecidable.
The diagonal method mirrors Cantor's Theorem (uncountability of the reals) and underlies Gödel's Incompleteness Theorems — Turing's undecidability gives a clean alternative proof that arithmetic is incomplete.
The Church-Turing Thesis equates Turing machines with the $\lambda$ -calculus, general recursive functions, and every other reasonable model of computation.
In complexity theory, undecidability is the "infinite-resource" limit beyond the P versus NP Problem, which concerns efficient decidability.

🔬 Where this appears

⏳ History

- 1900 — David Hilbert poses his program for a complete, consistent, decidable foundation of mathematics; the Entscheidungsproblem is later (1928) sharpened by Hilbert and Ackermann.

- 1931 — Kurt Gödel proves his Incompleteness Theorems, showing arithmetic cannot be both complete and consistent.

- 1933–35 — Alonzo Church and Stephen Kleene develop the

\lambda

-calculus and the theory of recursive functions.

- 1936 — Church publishes an undecidability result for the Entscheidungsproblem using

\lambda

-definability; Turing independently introduces Turing machines and proves the Halting Problem undecidable.

- 1937 — Turing proves the equivalence of

\lambda

-definability, recursiveness, and Turing-computability, cementing the Church–Turing Thesis.

- 1943 — Emil Post formalizes related "production systems" and contributes to degrees of unsolvability.

- 1951 — H. G. Rice proves that all non-trivial semantic properties of programs are undecidable (Rice's Theorem).

- 1965 — The notion of computational complexity (Hartmanis & Stearns) refines decidability into resource-bounded classes, leading toward P versus NP Problem.

- 1970 — Matiyasevich completes the negative solution to Hilbert's 10th problem: Diophantine solvability is undecidable, reducing to Turing's framework.

open-problem

Undecidability is unconditional, but neighboring questions remain rich and partly open:

Busy Beaver function $\Sigma(n)$ , the maximum number of $1$ s a halting $n$ -state TM can print, grows faster than any computable function and is itself uncomputable. The exact value $\Sigma(5)=4098$ was only confirmed in 2024 by a community effort, while $\Sigma(6)$ is astronomically beyond reach.
Degrees of unsolvability (Turing degrees) form an intricate lattice; whether certain natural problems occupy specific degrees is subtle.
The boundary between decidable and undecidable in concrete systems (e.g., word problems, tiling problems, Diophantine families) is an active research frontier.
The Halting Problem is undecidable, yet probabilistic and average-case notions of "deciding halting for most programs" lead to ongoing investigation in algorithmic information theory (Chaitin's $\Omega$ ).

Computability Theory — Turing Machines and the Halting Problem

Formal Statement

Why It Holds

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also