Past exam of the mathematics course of the University of Cambridge / 2020 / ii / Paper 1 / 12F / c

The function $g$ is not partial computable. It is defined on every input, so if a register machine with code $e$ computed it, then $f_{e,1}=g$ and in particular $f_{e,1}(e)$ would be defined. The first clause in the definition would givewhich is impossible. This is the usual diagonal argument behind the noncomputability of the diagonal halting set.

The function $h$ is also not partial computable. On every odd input it is defined, andbecause the value in the halting case is $f_{n,1}(n)+1\ge 1$. Thus a machine computing $h$ would decide diagonal halting for odd program indices simply by running $h(n)$ and testing whether its output is zero.

That restricted problem remains undecidable. By the padding lemma, an arbitrary machine can effectively be replaced by an equivalent machine having an odd code—for example by adding unreachable instructions until the chosen effective encoding has the required parity. This gives a computable reduction from unrestricted diagonal halting to diagonal halting on odd indices. A decider obtained from $h$ would therefore decide the full diagonal halting problem, a contradiction. Hence