Halting problem and reductions

Why it exists

Earlier pages showed that some problems about machines are decidable (is a DFA's language empty?). This page proves the opposite: no algorithm can decide whether a given Turing machine accepts a given input, or whether it halts. This is the most famous negative result of computer science and a staple of GATE: which of these problems is undecidable, which is recognisable, what does a reduction prove.

Prerequisites

You need the notions of decider and recogniser and the theorem about a language and its complement (decidable and recognisable languages).

Precise definitions

Fix an encoding $\langle M \rangle$ of Turing machines as strings (TM variants). Then:

• $A_{TM} = \{\langle M, w \rangle : M \text{ is a Turing machine that accepts the string } w\}$ (the acceptance problem);
• $HALT_{TM} = \{\langle M, w \rangle : M \text{ halts on input } w\}$ (the halting problem; halting means accepting or rejecting, not looping).

A mapping (many-one) reduction from $A$ to $B$, written $A \le_m B$, is a computable function $f$ (computed by a machine that always halts) with

$w \in A \iff f(w) \in B \quad \text{for every } w.$

Reduction theorems. If $A \le_m B$ and $B$ is decidable then $A$ is decidable; if $A \le_m B$ and $B$ is recognisable then $A$ is recognisable. Contrapositive: if $A$ is undecidable and $A \le_m B$ then $B$ is undecidable. To prove a new problem undecidable, reduce a known undecidable problem to it.

How it works

$A_{TM}$ is recognisable

The universal machine $U$ on input $\langle M, w \rangle$ simulates $M$ on $w$ and accepts if $M$ accepts. If $M$ loops, $U$ loops; so $U$ recognises $A_{TM}$ but does not decide it. (A program that decodes the description and simulates agrees with direct simulation on all test strings.)

$A_{TM}$ is undecidable: diagonalisation

Idea. List all Turing machines $M_1, M_2, \ldots$ (possible, because a machine is a finite string: all strings can be listed by length and alphabetically, and for every size there are finitely many machines; with $k$ states and $g$ tape symbols there are exactly $(2kg + 1)^{kg}$ transition tables, if each entry is a move or missing: $25$ for $k = 1$, $g = 2$, found by enumeration) and the strings $s_1, s_2, \ldots$ in the same way. Make a table with a row for each machine and a column for each string; the entry is "accepts" or not. The diagonal machine $D$ accepts $s_i$ exactly when $M_i$ does not accept $s_i$. Then $D$ differs from every $M_i$ in the entry of column $i$, so $D$ is not in the list: the language of $D$ is recognised by no machine of the list. If $A_{TM}$ were decidable, $D$ could be built, and $D$ is a machine, so it is in the list: contradiction.

Here is the table for six real machines (accepts, rejects, or runs for more than $600$ moves without halting) on the first six strings, with the diagonal row computed by flipping the diagonal:

The last row differs from row $i$ at column $i$, for every $i$ (a machine that does not halt does not accept, so the flipped entry is "accepts").

The proof in words (Turing's argument). Suppose a machine $H$ decides $A_{TM}$. Build $D$: on input $\langle M \rangle$, run $H$ on $\langle M, \langle M \rangle \rangle$ and do the opposite (accept if $H$ rejects, reject if $H$ accepts). Run $D$ on its own description $\langle D \rangle$: $D$ accepts $\langle D \rangle$ iff $H$ says $D$ does not accept $\langle D \rangle$, iff $D$ does not accept $\langle D \rangle$. Contradiction. So no such $H$ exists.

A counting version. The set of Turing machines is countable (strings over a finite alphabet), the set of languages over $\{0, 1\}$ is uncountable (it has the size of the set of infinite 0-1 sequences, by Cantor's diagonal argument). So most languages are recognised by no machine at all; the undecidable problems are not rare curiosities.

The halting problem

$HALT_{TM}$ is undecidable because $A_{TM} \le_m HALT_{TM}$. Given $\langle M, w \rangle$ construct $\langle M', w \rangle$ where $M'$ is $M$ with every place where $M$ would halt and reject replaced by an endless loop (move right for ever). Then $M'$ halts on $w$ exactly when $M$ accepts $w$. A decider for $HALT_{TM}$ would therefore decide $A_{TM}$. The table checks the equivalence on six machines and four strings each:

For example the machine "reject every string" halts on every input but accepts none; its transformed version loops everywhere. $HALT_{TM}$ is recognisable (simulate and accept when the simulation halts).

Unrecognisable languages

$A_{TM}$ is recognisable and undecidable, so by the theorem of the previous page its complement $\overline{A_{TM}}$ is not recognisable. Likewise $\overline{HALT_{TM}}$ is not recognisable. These are the first examples of languages that no machine recognises in a natural way.

More undecidable problems by reduction

• $E_{TM} = \{\langle M \rangle : L(M) = \emptyset\}$ is undecidable: from $\langle M, w \rangle$ build $M_w$ that ignores its input, runs $M$ on $w$ and accepts if $M$ accepts. Then $L(M_w) \ne \emptyset$ iff $M$ accepts $w$ (this is the construction behind Rice's theorem). $E_{TM}$ is not recognisable but its complement (non-empty language) is recognisable: dovetail over all strings.
• $EQ_{TM}$ (do two machines recognise the same language) is undecidable: $E_{TM} \le_m EQ_{TM}$, comparing $M$ with a machine that rejects everything.
• $REGULAR_{TM}$ (is the language regular) is undecidable (a similar reduction, quoted).
• Post correspondence problem, equivalence of two context-free grammars, whether a grammar is ambiguous, Hilbert's tenth problem (integer roots of polynomials), and the validity of sentences in first-order logic are undecidable (quoted); the first is the usual starting point for proofs about grammars.

A map of the problems

Worked examples

Cheat box

Traps and GATE patterns

Connections

The construction of $M_w$ above is the key step of Rice's theorem (Rice's theorem); the distinction between recognisable and decidable comes from the previous page (decidable and recognisable languages); the universal machine and encoding come from the page on variants (TM variants).

PYQs

Consider the following problems. L(G) denotes the
language generated by a grammar G. L(M) denotes the
language
accepted
by
a
machine
M.
(I) For an unrestricted grammar G and a string w,
whether w∈L(G).
(II) Given a Turing machine M, whether L(M) is
regular.
(III)Given two grammar G1 and G2, whether L(G1) =
L(G2).
(IV) Given an NFA N, whether there is a deterministic
PDA P such that N and P accept the same language.
Which one of the following statement is correct?

Let L(R) be the language represented by regular
expression R. Let L(G) be the language generated by a
context free grammar G. Let L(M) be the language
accepted by a Turing machine M.
Which of the following decision problems are
undecidable?
I. Given a regular expression R and a string w, is w ∈
L(R)?
II. Given a context-free grammar G, is L(G) = ∅?
III. Given a context-free grammar G, is L(G) = Σ* for
some alphabet Σ?
IV. Given a Turing machine M and a string w, is w
∈L(M)?

Consider the following languages.
L1 = { ⟨M⟩ | M takes at least 2016 steps on some input },
L2 = { ⟨M⟩ | M takes at least 2016 steps on all inputs },
and
L3 = { ⟨M⟩ | M accepts ε },
Where for each Turing machine M, ⟨M⟩ denotes a specific
encoding of M.
Which one of the following is TRUE?

Let A≤mB denotes that language A is mapping reducible
(also known as many-to-one reducible) to language
B.Which one of the following is FALSE?

Which of the following is/are undecidable?
1. G is a CFG. Is L(G) = φ?
2. G is a CFG. Is L(G) = Σ*?
3. M is a Turing machine. Is L(M) regular?
4. A is a DFA and N is an NFA. Is L(A) = L(N)?

Consider three decision problems P1, P2 and P3. It is
known that P1 is decidable and P2 is undecidable.

Self-check

Revision card

References