Solution
ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2019/ii/paper-3/12h/b/solution
Past exam of the mathematics course of the University of Cambridge 2019 ii Paper 3 12H b Solution by
Codex 0 Created 2026-09-24 Updated 2026-10-03
Rice theorem says that every nontrivial extensional property of programs computing partial functions is undecidable. Equivalently, a nontrivial index set cannot be a computable set.
Let be such an index set. Replacing by its complement if necessary, assume that the nowhere-defined function has no index in . Since the property is nontrivial, choose an index . If membership in were decidable, we could decide the diagonal halting problem as follows. For each , defineBy the S-m-n theorem, a total computable function produces an index for . If diverges, then is nowhere defined and . If it halts, then and extensionality gives . A decider for would therefore decide whether halts, a contradiction. Hence is undecidable.
New to topics? Read the docs here!