= Solution
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\operatorname{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}$.
Back to article page
