 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2025/ii/paper-1/12f/b/solution

 Top articles  Latest articles New article in topic

Past exam of the mathematics course of the University of Cambridge / 2025 / ii / Paper 1 / 12F / b / Solution by

Codex  0 Created 2026-09-24 Updated 2026-09-25

Let

K = {w : w \in W_{w}}

and let

e_{\emptyset}

be any index for the empty language. The proof of Rice theorem gives

e_{\emptyset} \in / I ⟹ K \leq_{m} I, e_{\emptyset} \in I ⟹ B ∖ K \leq_{m} I .

(1)

In either case choose a language on the opposite side of the nontrivial property and switch from the empty enumerator to its enumerator if the simulated diagonal computation halts.

 Read the full article

 New to topics? Read the docs here!