Questions: Undecidable Problems: Beyond the Halting Problem

Question 1

The Post Correspondence Problem (PCP) is about matching string sequences from two lists. Why is its undecidability particularly significant?

• A. It shows that even problems about Turing machines are unsolvable in general
• B. It demonstrates undecidability in a purely string-matching puzzle with no programs or machines in its statement
• C. It proves that no practical string algorithms can exist for modern compilers
• D. It is a harder version of the Halting Problem that applies only to infinite alphabets

Answer: (B)

PCP involves no programs, machines, or computation — just lists of string pairs and the question of whether indices can be chosen so both concatenations match. Its undecidability shows that computational limits are not confined to problems about computation itself. The proof works by encoding Turing machine computation histories as PCP instances, but the problem statement is purely combinatorial. This is what makes it a powerful intermediate lemma: proving something reduces to PCP proves it's undecidable without mentioning Turing machines directly.

Question 2

A compiler engineer proposes building a tool that checks every context-free grammar in their language suite for ambiguity before release. This proposal is:

• A. Feasible — grammar ambiguity can be checked by parsing all strings up to some length
• B. Infeasible in general — grammar ambiguity is undecidable, so no algorithm can solve this for all grammars
• C. Feasible only for grammars with fewer than 100 production rules
• D. Infeasible because context-free grammars are not Turing-complete

Answer: (B)

Grammar ambiguity — whether some string has two distinct parse trees — is undecidable for context-free grammars, proved by reduction from PCP. No algorithm can correctly decide ambiguity for all grammars. Checking finite test inputs cannot work: a grammar might be unambiguous on all strings up to any given length yet ambiguous for some longer string. The common misconception is that exhaustive testing can serve as a decision procedure; for undecidable problems it cannot, regardless of how many cases are checked.

Question 3

Undecidability primarily arises in problems that are explicitly about programs and Turing machines. Natural mathematical problems — like solving polynomial equations — are generally decidable.

• T. True
• F. False

Answer: False

Hilbert's Tenth Problem — determining whether a polynomial Diophantine equation has integer solutions — is undecidable, despite being a purely number-theoretic question with no mention of programs or machines. The proof encodes Turing machine computation into Diophantine equations, showing that the set of solvable instances can represent any recursively enumerable set. Undecidability pervades mathematics; it appears in number theory, formal language theory, logic, and tiling problems — not just problems about computation.

Question 4

The membership problem for context-free grammars (given grammar G and string w, is w in L(G)?) is decidable, even though grammar ambiguity is not.

• T. True
• F. False

Answer: True

Decidability is not uniform across all questions about a class of objects. Whether a string belongs to a context-free language is decidable (e.g., by the CYK algorithm). But whether a context-free grammar is ambiguous is not decidable — there is no algorithm that can answer this for all grammars. This contrast illustrates that undecidability is fine-grained: even within simple computational classes, some questions are decidable and others are not.

Question 5

How is the undecidability of a new problem typically established, and why does this method work even for problems that seem to have nothing to do with computation?

Model answer: Undecidability is typically established by reduction: showing that if an algorithm existed for the new problem, it could be used to decide the Halting Problem (or another known undecidable problem). Reductions encode computation histories or machine behavior into instances of the new problem. This works even for non-computational problems — like Diophantine equations or grammar ambiguity — because any question powerful enough to capture the behavior of arbitrary computations inherits undecidability. The new problem doesn't need to look like a computing problem; it just needs to be expressive enough to simulate one.

The reduction method is the core proof technique: if problem B is undecidable and B reduces to A (any algorithm for A would solve B), then A is also undecidable. PCP, grammar ambiguity, and Hilbert's Tenth are all established this way. The surprising reach of undecidability comes from the fact that many natural mathematical structures — strings, polynomials, grammars — are expressive enough to encode arbitrary computation.