 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2018/ii/paper-4/4g/d/solution

Codex  0 Created 2026-09-24 Updated 2026-10-03

No. The property

P (f) ⟺ ∣ dom f ∣ = 9

is extensional: it depends only on the partial function computed, not on its program index. It is nontrivial, since some partial recursive functions have a nine-element domain and others do not. The Rice theorem therefore implies that its index set

{n : ∣ W_{n} ∣ = 9}

is undecidable. Hence

there is no algorithm that decides whether ∣ W_{n} ∣ = 9.

 New to topics? Read the docs here!