Past exam of the mathematics course of the University of Cambridge / 2020 / ii / Paper 1 / 12F (Automata and Formal Languages)

A register machine has finitely many natural-number registers, a finite set of labelled states, and instructions that increment a register, conditionally decrement and branch according to whether a register is zero, or halt. A program is a finite sequence of such labelled instructions, and a configuration records the current instruction together with every current register value.

Given $k$ inputs, place them in designated input registers and initialize the remaining registers to zero. The machine computes a partial computable function $f:{\mathbb{N}}^k\rightharpoonup \mathbb{N}$ when it halts with output $f(\mathbf{x})$ in the output register exactly for $\mathbf{x}\in \mathrm{dom}f$ and runs forever otherwise.

To encode a machine, encode every instruction by a natural number using effective encodings of its opcode, register number, and target labels. Encode the resulting finite sequence by a Gödel numbering, for example through iterated pairing or prime powers. Effective decoding gives an enumeration $(P_n)$ of machine programs, so the unary function computed by program code $n$ may be denoted $f_{n,1}$.

The partial recursive functions form the smallest class containing the zero function, successor function, and projection functions and closed under composition, primitive recursion, and unbounded minimization.

Fix a register machine $P$ with $k$ inputs. By the permitted result, its complete configuration after $t$ steps,is a recursive function of the inputs and time. The predicate $H(\mathbf{x},t)$ saying that this configuration is halted is therefore recursive. Its halting time is the partial recursive functionwhere unbounded minimization is undefined when no halting time exists. Extracting the output register from a configuration is recursive, sois partial recursive. Hence every partial computable function is partial recursive.

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