Computability and decidability §

Step 1 — What a model of computation is. A model of computation fixes, in mathematical terms, what counts as a mechanical procedure, so that “computable” stops being a vague word. A Turing machine is the standard choice: a finite control (a finite set of states) that reads and writes one cell of an unbounded tape at a time. The full 7-tuple definition, the notion of a decidable language, and the complexity classes built on top of it are developed on the Computer-Science side in Computability and Complexity Classes; here we only need the machine as a black box that either halts or runs forever.

Step 2 — Universality and self-reference. A Turing machine can be written down as a finite string of symbols, so a machine’s description is itself data. A universal machine $U$ reads a pair $(\langle M\rangle, w)$ — the code of a machine $M$ and an input $w$ — and simulates $M(w)$ step for step. Because a machine’s code is just a string, a machine can be handed its own code as input. This self-reference is the engine behind every undecidability proof on this page: it is what lets us build a machine $D$ that reasons about its own behavior.

The simulator below runs a concrete Turing machine that decides the language $L = \{0^n 1^n : n \ge 0\}$ — a decidable (but not regular) language. Load an input and step through to watch the machine mark off matched $0$/1 pairs.

Authoritative sources

• A. Turing (1936), On Computable Numbers, with an Application to the Entscheidungsproblem

Example problem. Why does universality matter for undecidability, and not merely for convenience?

Step 1 — Decidable vs. semi-decidable. A decider must answer both yes and no in finite time. A semi-decider only has to answer yes in finite time; on a “no” instance it is allowed to loop forever. So every decidable set is semi-decidable, but not conversely: a semi-decider can “miss” the negative answers by never halting on them.

Step 2 — A concrete semi-decidable set. The halting set $K = \{e : \varphi_e(e) \text{ halts}\}$ (the set of machine codes that halt when run on their own code) is semi-decidable: to test whether $e \in K$, run machine $e$ on input $e$; if it halts, accept. If it never halts, the test runs forever — exactly the behavior a semi-decider is allowed to have. We will see in the next section that $K$ is not decidable, so it is a genuine example of a set that is semi-decidable but not decidable.

The three-way split is shown below: a set can be decidable (both directions answer), semi-decidable only (positives answer, negatives may loop), co-semi-decidable only (negatives answer, positives may loop), or neither.

Authoritative sources

• H. Rogers, Jr., Theory of Recursive Functions and Effective Computability (1967)

Example problem. Give a set that is co-semi-decidable but not decidable, and justify it.

Step 1 — Diagonalization. Suppose a decider $H(M, w)$ existed, answering “halts” or “loops” for any machine $M$ and input $w$. Build a machine $D$ that, on input $m$, runs $H(m, m)$ and does the opposite: if $H$ says “$m$ halts on $m$,” then $D$ loops; otherwise $D$ halts. Now run $D$ on its own code $D$: $D$ halts on $D$ exactly when it does not — a contradiction. So no such $H$ exists. (The same self-referential structure appears in Cantor’s proof that the reals are uncountable. Gödel’s incompleteness theorems reach a similar self-reference by a different route — arithmetization plus the fixed-point lemma, not direct diagonalization — see Mathematical logic.)

The diagram below lays out the diagonal: the rows are machines, the columns are inputs, and the highlighted diagonal is where each machine is run on its own code. The machine $D$ is built to disagree with the diagonal everywhere, so at the cell $D(D)$ it must both halt and loop.

Authoritative sources

• A. Turing (1936), On Computable Numbers, with an Application to the Entscheidungsproblem
• A. Church (1936), An Unsolvable Problem of Elementary Number Theory

Step 2 — Reductions: spreading undecidability. Once one problem is known undecidable, others follow by reduction. A problem $A$ reduces to a problem $B$ (written $A \le_m B$) if a machine can, given any instance of $A$, produce an instance of $B$ that is a “yes” exactly when the original was. If $B$ were decidable, then so would be $A$; so if $A$ is undecidable and $A \le_m B$, then $B$ is undecidable too.

Concrete reduction. Show that ACCEPTS-SOMETHING $= \{M : M \text{ accepts at least one input}\}$ is undecidable by reducing the halting problem to it. Given a halting-problem instance $(M, w)$, build a machine $M'$ that, on any input $x$, first ignores $x$, simulates $M(w)$, and accepts if and only if $M(w)$ halts. Then $M'$ accepts some input (indeed every input) exactly when $M(w)$ halts, so $(M, w) \in \text{HALT} \iff M’ \in \text{ACCEPTS-SOMETHING}$. If ACCEPTS-SOMETHING were decidable, HALT would be — contradiction.

The same reduction pattern proves the undecidability of the first-order Entscheidungsproblem (Church 1936), the word problem for groups (Novikov 1955; Adian 1958), and the tiling problem (Rogers 1952; Berger 1966).

Authoritative sources

• P. S. Novikov, The unsolvability of the word problem for groups and semigroups (1955)
• R. Berger, The undecidability of the domino problem (1966)

Example problem. Reduce the halting problem to the problem ACCEPTS-EMPTY $= \{M : M \text{ accepts the empty string } \varepsilon\}$.

Step 1 — The decidable base. A decidable (Δ₀) predicate is one a machine can answer yes/no on in finite time. The hierarchy is built by stacking quantifiers over such a base. The base itself is level 0: a set defined by a decidable predicate with no quantifiers is just decidable.

Step 2 — The Σ₁ / Π₁ base of the hierarchy. Adding a single existential quantifier over a decidable predicate gives Σ₁: $n \in S \iff \exists x\, R(x, n)$. To semi-decide such an $S$, search $x = 0, 1, 2, \dots$ and accept the first $x$ with $R(x, n)$; if none exists, the search runs forever. So Σ₁ = semi-decidable. Dually, a single universal quantifier gives Π₁ = co-semi-decidable. Concrete Σ₁ example: the halting set $K = \{e : \exists s\, [\varphi_e(e) \text{ halts within } s \text{ steps}]\}$ — the predicate “halts within $s$ steps” is decidable (simulate for $s$ steps), so $K$ is Σ₁.

Step 3 — Higher levels. Each further alternation raises the level. Concrete Σ₂ example: the set of machines that halt on every input, $\text{TOT} = \{e : \forall x\, \exists s\, [\varphi_e(x) \text{ halts within } s \text{ steps}]\}$. The innermost predicate is decidable, then ∃s, then ∀x: a Σ₂ definition. TOT is not Σ₁ (it is not semi-decidable), which is why the hierarchy does not collapse at level 1.

The nested-boxes diagram below places these examples: Σ₁ (semi-decidable, containing $K$) and Π₁ (co-semi-decidable, containing $\overline{K}$) overlap exactly in the decidable sets, and both sit strictly inside Σ₂, which contains TOT.

Authoritative sources

• H. Rogers, Jr., Theory of Recursive Functions and Effective Computability (1967)
• Stanford Encyclopedia of Philosophy: Computability and Complexity

Example problem. Place the set $\text{TOT} = \{e : \varphi_e \text{ is a total function}\}$ in the hierarchy, and argue that it is not Σ₁.

Problem. Show that the halting set $K = \{e : \varphi_e(e) \text{ halts}\}$ is Σ₁-complete: (i) $K$ is Σ₁, and (ii) every Σ₁ set many-one reduces to $K$.