Past exam of the mathematics course of the University of Cambridge / 2026 / ii / Paper 3 / 12J (Automata and Formal Languages)

A register machine has finitely many natural-number registers and labelled increment, conditional decrement/jump, and halt instructions. Starting with the input in designated registers, instructions determine a partial computation. Encode the finite instruction list by a standard effective Gödel coding, giving each machine an index in $\mathbb{N}$.

For machine index $m$, $f_{m,k}$ is the partial $k$-ary function computed by that machine under the fixed coding, and $W_m$ is its halting domain (equivalently the r.e. set enumerated by machine $m$, under the course convention).

Kleene's recursion theorem says that for every total recursive map $f$ on program indices there is an index $e$ with the same partial function as program $f(e)$.

Take $i$ to index a machine halting on every input, so $W_i=\mathbb{N}$, and $j$ to index a machine halting on no input, so $W_j=\varnothing$.

If $g_0$ were total recursive, its recursion-theorem fixed point $e$ would satisfy $W_e=W_j$ when $e\in \mathrm{Inf}$ and $W_e=W_i$ when $e\in \mathrm{Fin}$, a contradiction in either case. The same argument applies to $g_1$. A total recursive reduction $h$ with $n\in \mathrm{Inf}⟺h(n)\in \mathrm{Fin}$ would provide such a forbidden switch (and would collapse the known distinct arithmetical complexities), so none exists.