Past exam of the mathematics course of the University of Cambridge / 2019 / ii / Paper 2 / 4H (Automata and Formal Languages)

A recursive set $E\subseteq {\mathbb{N}}_0$ has an indicator function computed by a register machine that halts on every input. A recursively enumerable set is the exact halting set of some register machine; equivalently, it is the domain of a partial computable function.

If $E$ is recursive, its decider immediately gives machines that halt exactly on $E$ and on ${\mathbb{N}}_0\setminus E$, so both sets are recursively enumerable. Conversely, suppose machines $M_E$ and $M_{E^c}$ recognize the two sets. On input $x$, use dovetailing to run one step of $M_E(x)$ and one step of $M_{E^c}(x)$ alternately. Exactly one must eventually halt. Return one if $M_E$ halts first and zero if $M_{E^c}$ halts first. This is a total decider for $E$, so $E$ is recursive.

Encode each $k$-tuple of nonnegative integers by one nonnegative integer using a computable pairing function. Define a unary partial procedure $P$ on input $m$ as follows: use dovetailing on the computations of $f_{n,k}$ over all encoded $k$-tuples, and halt as soon as one of them halts with output $m$. ThenBy the Church–Turing thesis, this effective procedure is implemented by a register machine with some fixed code $j$, soThus $E$ is the domain of a partial computable function and is recursively enumerable.

The function is the predecessor function. It has the primitive recursion definitionThe initial function is the zero function and the recursion step is a projection function, both of which are primitive recursive functions. Closure under primitive recursion therefore proves that $f$ is primitive recursive.