Reductions, Rice's theorem and undecidable problems

The halting problem is the first undecidable problem, but it is far from the only one. Once we have one, reductions let us transfer undecidability to many others, much as lesson 10 will transfer NP-hardness. This lesson makes reductions precise, proves Rice's theorem, which says that every non-trivial question about the behavior of programs is undecidable, and then shows that undecidability is not confined to questions about machines. The Post Correspondence Problem, a simple puzzle about dominoes, is undecidable, and so are natural questions about context-free grammars, such as whether two grammars generate the same language. We end with Kolmogorov complexity, a measure of information content that cannot be computed.

Mapping reductions

A function \(f : \Sigma^* \to \Sigma^*\) is computable if some Turing machine, on every input w, halts with f(w) on its tape. Language A is mapping reducible to language B, written \(A \le_m B\), if there is a computable function f such that for every w, \(w \in A \iff f(w) \in B\). The function f translates instances of A into instances of B with the same answer. Theorem. If \(A \le_m B\) and B is decidable, then A is decidable: compute f(w) and run the decider for B. Contrapositively, if A is undecidable and \(A \le_m B\), then B is undecidable. Similarly, if \(A \le_m B\) and B is recognizable, so is A; so if A is not recognizable, neither is B. Note the direction: to prove B hard, reduce a known hard problem to B.

Here is a typical reduction. Let \(E_{\text{TM}} = \{\langle M \rangle : L(M) = \emptyset\}\). We show \(A_{\text{TM}} \le_m \overline{E_{\text{TM}}}\). Given \(\langle M, w \rangle\), let f output the description of a new machine \(M'\) that, on any input x, ignores x, runs M on w, and accepts if M accepts. If M accepts w, then \(M'\) accepts every string, so \(L(M') \ne \emptyset\). If M does not accept w, then \(M'\) accepts nothing. So \(\langle M, w \rangle \in A_{\text{TM}} \iff \langle M' \rangle \in \overline{E_{\text{TM}}}\). Computing f does not require running M; it only writes a program that would run M, which is a simple text transformation. Hence \(\overline{E_{\text{TM}}}\) is undecidable, and so is \(E_{\text{TM}}\), since a language is decidable exactly when its complement is.

# A mapping reduction from A_TM to the complement of E_TM, written as a program transformer.
# Given (M, w), build the source of M' that ignores its own input and runs M on w.
# Then: M accepts w  <=>  L(M') is non-empty (indeed L(M') = everything).
def reduction(machine_src, w):
    return f"""
def M_prime(x):
    # ignore x; run the original machine on the fixed input {w!r}
{chr(10).join('    ' + line for line in machine_src.strip().splitlines())}
    return M({w!r})
"""

M_src = """
def M(s):
    # accepts strings with an even number of 1s; loops forever on others
    while s.count("1") % 2 == 1:
        pass
    return True
"""
for w in ["1010", "111"]:
    out = reduction(M_src, w)
    print(f"--- reduction output for w = {w!r} ---")
    print(out.strip())
env = {}
exec(reduction(M_src, "1010"), env)
print("--- running M_prime from w = '1010' on a few inputs ---")
print([env["M_prime"](x) for x in ["", "0", "anything"]])
print("(for w = '111', M_prime would loop on every input, so its language is empty)")

--- reduction output for w = '1010' ---
def M_prime(x):
    # ignore x; run the original machine on the fixed input '1010'
    def M(s):
        # accepts strings with an even number of 1s; loops forever on others
        while s.count("1") % 2 == 1:
            pass
        return True
    return M('1010')
--- reduction output for w = '111' ---
def M_prime(x):
    # ignore x; run the original machine on the fixed input '111'
    def M(s):
        # accepts strings with an even number of 1s; loops forever on others
        while s.count("1") % 2 == 1:
            pass
        return True
    return M('111')
--- running M_prime from w = '1010' on a few inputs ---
[True, True, True]
(for w = '111', M_prime would loop on every input, so its language is empty)

Reductions also separate recognizability from co-recognizability. The reduction above shows \(A_{\text{TM}} \le_m \overline{E_{\text{TM}}}\), and therefore also \(\overline{A_{\text{TM}}} \le_m E_{\text{TM}}\), since the same f works for complements. Because \(\overline{A_{\text{TM}}}\) is not recognizable, neither is \(E_{\text{TM}}\). By contrast \(\overline{E_{\text{TM}}}\), non-emptiness, is recognizable by dovetailing, as lesson 8 showed. The equivalence problem \(EQ_{\text{TM}}\) is worse still: it is neither recognizable nor co-recognizable, which can be shown by reducing \(\overline{A_{\text{TM}}}\) to it and also to its complement. Reductions thus classify undecidable problems into finer degrees of unsolvability.

Rice's theorem

Many questions about programs ask about the language they recognize: does this program accept any string? Does it accept all strings? Is its language regular? Is it finite? Does it accept the string 'hello'? A property P of Turing machines is a semantic (or language) property if whenever \(L(M_1) = L(M_2)\), \(M_1\) and \(M_2\) either both have P or both lack it. It is non-trivial if some machine has it and some machine lacks it. Theorem (Rice, 1953). Every non-trivial semantic property of Turing machines is undecidable.

The proof is one reduction for all such properties. Suppose a decider R exists for a non-trivial semantic property P. Without loss of generality, machines whose language is empty lack P (otherwise work with the complement of P). Since P is non-trivial, some machine T has it. Reduce \(A_{\text{TM}}\) to P: given \(\langle M, w \rangle\), build \(M_w\) that, on input x, first runs M on w; if that accepts, it then runs T on x and accepts if T does. If M accepts w, then \(L(M_w) = L(T)\), which has P. If not, \(L(M_w) = \emptyset\), which lacks P. So R applied to \(M_w\) would decide \(A_{\text{TM}}\), which is impossible.

Rice's theorem explains why program analysis is hard. Whether a program ever outputs a secret, whether it is equivalent to a reference implementation, whether it terminates on all inputs, whether it ever divides by zero on some input: all are non-trivial semantic properties of programs, suitably phrased, and none can be decided exactly for all programs. The theorem does not apply to syntactic properties, such as whether the source has more than 100 lines or uses a goto, which are trivially decidable; nor to properties of a machine's running time bounded by an explicit number of steps; nor to questions about a fixed program. Static analyzers succeed in practice by approximating: they answer questions that are slightly different, and decidable, such as 'does every path in the control-flow graph satisfy the property?', accepting false alarms or missed cases in return.

The Post Correspondence Problem

Undecidability reaches problems with no visible connection to machines. An instance of the Post Correspondence Problem (PCP), introduced by Emil Post in 1946, is a finite collection of dominoes, each with a string on the top and a string on the bottom. A match is a non-empty sequence of dominoes, repetitions allowed, such that the concatenation of the tops equals the concatenation of the bottoms. PCP asks whether a given collection has a match. Theorem (Post, 1946). PCP is undecidable. The proof reduces \(A_{\text{TM}}\) to PCP by building dominoes that force any match to spell out an accepting computation history of M on w: the bottom strings run one configuration ahead of the tops, and the only way for the tops to catch up is to reach an accepting configuration, after which special dominoes let the strings close.

The program below runs a bounded breadth-first search for matches. It finds a match of five dominoes for a classic four-domino instance and finds none within its bound for another. That second result illustrates the asymmetry from lesson 8: PCP is recognizable, because a search over all sequences finds a match if one exists, but no search can confirm that none exists. Some small PCP instances are known whose shortest matches are extremely long, which is a practical hint of the underlying undecidability; it is known that PCP is decidable when the number of dominoes is at most 2, and undecidable already for 5 dominoes.

# Post Correspondence Problem: pick a sequence of dominoes so the tops and bottoms spell the same string.
# The general problem is undecidable; a bounded search can find solutions but never proves there are none.
from collections import deque

def solve(dominoes, max_len=12):
    # breadth-first over sequences; state = the unmatched overhang (which side, text)
    q = deque([((), "", "")])
    seen = set()
    while q:
        seq, top, bot = q.popleft()
        if seq and top == bot: return seq
        if len(seq) >= max_len: continue
        for i, (t, b) in enumerate(dominoes):
            nt, nb = top + t, bot + b
            k = min(len(nt), len(nb))
            if nt[:k] != nb[:k]: continue                  # prefixes must agree
            key = (nt[k:], nb[k:], len(seq) + 1 > 0)
            if (nt[k:], nb[k:]) in seen and seq: continue
            seen.add((nt[k:], nb[k:]))
            q.append((seq + (i,), nt, nb))
    return None

inst1 = [("b", "ca"), ("a", "ab"), ("ca", "a"), ("abc", "c")]
sol = solve(inst1)
print("instance 1:", inst1)
print("  solution (domino indices):", sol)
print("  top:   ", "".join(inst1[i][0] for i in sol))
print("  bottom:", "".join(inst1[i][1] for i in sol))
inst2 = [("ab", "aba"), ("bba", "aa"), ("aba", "bab")]
print("instance 2:", inst2)
print("  solution within 12 dominoes:", solve(inst2))
print("  (a failed bounded search is not a proof that no solution exists)")

instance 1: [('b', 'ca'), ('a', 'ab'), ('ca', 'a'), ('abc', 'c')]
  solution (domino indices): (1, 0, 2, 1, 3)
  top:    abcaaabc
  bottom: abcaaabc
instance 2: [('ab', 'aba'), ('bba', 'aa'), ('aba', 'bab')]
  solution within 12 dominoes: None
  (a failed bounded search is not a proof that no solution exists)

Undecidable problems about grammars

PCP is a convenient source for undecidability results about grammars, because grammars can generate sequences of dominoes. Given a PCP instance with dominoes \((t_i, b_i)\), build two grammars: \(G_T\) generates strings \(t_{i_1}t_{i_2}\cdots t_{i_k}\,\#\,i_k\cdots i_1\) recording the tops followed by the reversed index sequence, and \(G_B\) does the same for the bottoms. A match exists exactly when \(L(G_T) \cap L(G_B) \ne \emptyset\). So whether two CFGs generate intersecting languages is undecidable. With a little more work, using the fact that the complement of each such language is context-free, it follows that \(ALL_{\text{CFG}}\), whether a grammar generates every string, is undecidable, and hence so is \(EQ_{\text{CFG}}\): equivalence with a grammar for \(\Sigma^*\) would decide ALL. Ambiguity of CFGs is undecidable by a similar construction that combines \(G_T\) and \(G_B\) into one grammar, which is ambiguous exactly when a match exists.

A second route uses computation histories. An accepting computation history of M on w is the sequence of configurations \(C_1 \# C_2 \# \cdots \# C_k\), each following from the last by one step. The set of strings that are not accepting histories of M on w is context-free, even though the set of valid histories is not: a PDA can nondeterministically guess one place where the history is wrong, a bad start, a bad end, or two adjacent configurations that differ illegally, and checking a single local error needs only one stack. (Writing every second configuration reversed makes the comparison possible with a stack.) This grammar generates all strings exactly when M does not accept w, which reduces \(\overline{A_{\text{TM}}}\) to \(ALL_{\text{CFG}}\) and shows directly that ALL is not even recognizable.

Kolmogorov complexity

How much information does a string contain? The Kolmogorov complexity \(K(x)\) of a binary string x is the length of the shortest description of x, meaning the shortest input \(\langle M, w \rangle\) on which a fixed universal machine outputs x and halts. A string of a million 0s has tiny complexity, because 'print 0 a million times' is a short program; a typical string of a million random bits has complexity close to a million, because no description is much shorter than the string itself. The choice of universal machine changes K by at most an additive constant, which makes the measure robust. A simple counting argument shows that incompressible strings exist at every length: there are \(2^n\) strings of length n but only \(2^n - 1\) descriptions shorter than n.

Theorem. K is not computable. Suppose a program could compute K. Then a short program could search strings in shortlex order for the first x with \(K(x) > N\) and print it, for a large number N written into the program. That program has length about \(\log_2 N\) plus a constant, which is much less than N for large N, yet it describes x, contradicting \(K(x) > N\). This is a formal version of the Berry paradox, 'the smallest positive integer not definable in under sixty letters', which defines that integer in under sixty letters. Real compressors give computable upper bounds on K, and the program below shows the contrast between regular and random strings. It also shows how loose those bounds can be: the counter string is printed by a two-line program, so its complexity is tiny, yet a general-purpose compressor saves only about half its size, because it looks for repeated substrings rather than for the shortest program. Kolmogorov complexity connects computability to information theory, to randomness and to the foundations of statistical inference.

# Kolmogorov complexity is uncomputable, but compressed size gives an upper bound on it.
# Regular strings have short descriptions; random strings do not.
import random, zlib
random.seed(474)
n = 10_000
samples = {
    "all zeros":           "0" * n,
    "01 repeated":         "01" * (n // 2),
    "counter 0 1 2 3 ... written out": "".join(str(i) for i in range(3000))[:n],
    "random bits":         "".join(random.choice("01") for _ in range(n)),
    "random letters":      "".join(random.choice("abcdefghijklmnopqrstuvwxyz") for _ in range(n)),
}
for name, s in samples.items():
    c = len(zlib.compress(s.encode(), 9))
    print(f"{name:32s} length {len(s):6d}  compressed {c:5d} bytes  ({8 * c / len(s):.2f} bits per symbol)")
print("counting: there are 2^n bit strings of length n but fewer than 2^(n-10) descriptions")
print("shorter than n - 10 bits, so fewer than 1 in 1,000 strings compress by 10 bits or more.")

all zeros                        length  10000  compressed    34 bytes  (0.03 bits per symbol)
01 repeated                      length  10000  compressed    34 bytes  (0.03 bits per symbol)
counter 0 1 2 3 ... written out  length  10000  compressed  4918 bytes  (3.93 bits per symbol)
random bits                      length  10000  compressed  1706 bytes  (1.36 bits per symbol)
random letters                   length  10000  compressed  6257 bytes  (5.01 bits per symbol)
counting: there are 2^n bit strings of length n but fewer than 2^(n-10) descriptions
shorter than n - 10 bits, so fewer than 1 in 1,000 strings compress by 10 bits or more.

Worked examples