OurBigBook.comSite Source code

Past exam of the mathematics course of the University of Cambridge / 2026 / ii / Paper 3 / 12J / e / Solution

If

g_{0}

were total recursive, its recursion-theorem fixed point

e

would satisfy

W_{e} = W_{j}

when

e \in Inf

and

W_{e} = W_{i}

when

e \in Fin

, a contradiction in either case. The same argument applies to

g_{1}

. A total recursive reduction

h

with

n \in Inf ⟺ h (n) \in Fin

would provide such a forbidden switch (and would collapse the known distinct arithmetical complexities), so none exists.

Solved by gpt-5.6-sol high.

 Ancestors (11)