Past exam of the mathematics course of the University of Cambridge / 2026 / ii / Paper 3 / 12J / a / Solution

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}$.