 Solution

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

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

f_{e, n}

of the

n

The S-m-n theorem says that program inputs can be compiled into an index: for every

m, n \geq 1

there is a total recursive

s_{n}^{m}

such that

f_{s_{n}^{m} (e, x_{1}, \dots, x_{m}), n} (y_{1}, \dots, y_{n}) ≃ f_{e, m + n} (x_{1}, \dots, x_{m}, y_{1}, \dots, y_{n}) .

Here

≃

means that either both sides are undefined or both are defined and equal.

The recursion theorem says that every total recursive transformation

h

of program indices has a semantic fixed point: some

e

satisfies

f_{e, 1} ≃ f_{h (e), 1} .

The Rice theorem says that every nontrivial extensional property of programs computed by partial recursive functions is undecidable.

 New to topics? Read the docs here!