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

Table of contents
- Solution 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.

 Ancestors (10)

 View article source

 Discussion (0)

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version