Past exam of the mathematics course of the University of Cambridge / 2008 / iii / Paper 2 / 2

The primitive recursive functions are the smallest collection containing zero functions, successor $S(n)=n+1$, and coordinate projections, and closed under composition and primitive recursion. The recursion scheme forms $F$ from already constructed functions $G,H$ byConstants follow by composing successor with zero. Define addition, multiplication and exponentiation successively byAt each stage the initial and step functions are compositions of primitive recursive functions already available. Induction on $n$ gives $A(m,n)=m+n$, $M(m,n)=mn$, and $E(m,n)=m^n$, with the recursive convention $0^0=1$. Composition with the second projection now gives

A recursive function $f:{\mathbb{N}}^k\to \mathbb{N}$ is a total computable function: an algorithm halts on every input and returns the specified value. Equivalently it is an everywhere-defined member of the partial recursive functions, obtained from the initial zero, successor and projection functions by composition, primitive recursion and unbounded minimization. In minimization $\mu y[g(\mathbf{x},y)=0]$, the sequential search must find a zero after all earlier tests have been defined; otherwise the result is undefined. The Church–Turing thesis allows the algorithmic formulation here.

A recursively enumerable set $E\subseteq {\mathbb{N}}^k$ is the domain of a partial computable function. Thus an algorithm halts and accepts exactly on members of $E$, and may run forever on nonmembers. Equivalently an algorithm lists exactly its elements, allowing repetition and allowing an empty output for the empty set. To pass from a listing to a membership semidecision, wait for the input to appear. To pass back, use dovetailing on all inputs and list each whose recognizing computation halts. This differs from a recursive set, whose zero-one characteristic function is total recursive and decides both membership and nonmembership.

The halting problem asks whether program $e$ halts on input $x$, given effective codes for both. Suppose a total decision algorithm $H(e,x)$ returned one exactly when that computation halts. Construct a program $D$ which, on input $e$, computes $H(e,e)$ and then loops forever if the answer is one, but halts if it is zero. Let $d$ be the code of $D$. If $H(d,d)=1$, the specification of $D$ makes it diverge, while if $H(d,d)=0$ the same specification makes it halt. Both alternatives contradict correctness. Therefore the halting problem is $\boxed{\text{undecidable}}$. This is a diagonal argument, not merely the observation that individual simulations can run forever.

Let $K=\{e:\text{program }e\text{ halts on input }e\}$. Simulating the specified program semidecides membership, or dovetailing all simulations enumerates $K$, so $K$ is a recursively enumerable set. The same diagonal program rules out a total decision algorithm for $K$. Thus $\boxed{K\text{ is recursively enumerable but not recursive}}$. Encoding a pair $(e,x)$ also gives an enumerable nonrecursive set of all halting program-input pairs.