Kleene normal form for the fixed machine coding

Since $T_k$ is a total Boolean predicate, test $z=0,1,2,\dots$ in order. If some witness exists this search reaches the least one after finitely many terminating tests; if none exists it never terminates. F1 then gives exactly the numerical function and domain of ${\phi }_e^{(k)}$. Since PR functions belong to the partial recursive class, composition of U with minimization of $1-[T_k]$ is partial recursive. Thus every machine function belongs to that class.

Here are finite tape routines for the converse. Store finitely many finite words in delimited zones, with marked versions of each symbol. To copy a zone, find its next unmarked symbol by a left-to-right sweep, mark it, carry that symbol in the finite control to the destination delimiter, append it, and return to the source; after its end delimiter is reached, unmark the source. To insert room, scan to the last occupied delimiter and shift the suffix right by one cell, working from right to left while carrying one symbol. Erasing and testing an empty zone are sweeps to its delimiter. Binary increment scans rightward to the last digit, changes trailing ones to zero and the preceding zero to one, inserting a leading one if necessary. Zero testing compares with the one-letter zero word. Each sweep terminates on a finite zone; its cases concern a finite alphabet, so each description expands to finitely many states and transitions. Distinct control-state tags prevent interference. A left-edge flag prevents a sweep going below zero. If a routine uses a stationary move, store logical cells at even physical positions: a stationary action is right-left, a right move is right-right and a left move is left-left, with right-left for a clamped left move at zero. Delay a requested halt to the end of the two-transition action. This gives the stipulated left/right-only one-tape model.

Parse and copy the tuple inputs by these routines. Zero writes the single zero numeral, successor applies binary increment, and a projection copies its designated input numeral. For a composition $h(g_1(\mathbf{a}),\dots ,g_r(\mathbf{a}))$, keep the original tuple, run the $g_i$ sequentially on copies, save each canonical result, form their tuple and run $h$. To invoke a compiled machine without allowing its tape to destroy stored arguments, simulate its finite configuration in a separate zone using F3, retaining the calling zones outside that encoded tape. Copy its final output back only after a valid numeric halt; on invalid output or malformed code enter an endless rightward walk. Interpreter code and finite program constants can be inserted with renamed states and finite literal-writing chains. All required subcalls terminate exactly when their represented functions are defined. Thus the composition is strict in every inner argument, including when the outer function happens to ignore an argument.

For primitive recursion, retain $\mathbf{a}$ and the target $y$. Run $g(\mathbf{a})$, then for $j=0,\dots ,y-1$ run $h(\mathbf{a},j,z)$ where $z$ is the previous result, increment $j$ and replace $z$. At $y=0$ there are no calls to h. If any required call diverges, the entire computation diverges. Otherwise the loop makes exactly $y$ calls and its successive stored values satisfy the recursion equations, so it computes their strict partial interpretation. Nullary g is a constant routine on the empty stored argument list; it needs no arity-zero numeric evaluator.

For minimization, start $j=0$, run the compiled $g(\mathbf{a},j)$, output j on zero, and increment and repeat on nonzero. An undefined call blocks forever; it is not bypassed by dovetailing. Consequently termination at z occurs exactly under the minimization condition in the Statement. Each finite derivation of a partial recursive function now produces a finite program: process its tree from leaves to root using the preceding compilation constructions. The process is effective, since renaming a finite list of states, writing a literal constant, combining finite tables and encoding a table are finite scans with the explicit routines of step 1.2.

The programs thus built erase scratch, write the canonical output at the left edge, and halt only on a defined value; the internal simulation keeps scratch outside each simulated tape. They therefore compute the represented partial functions with precisely the required domains. Conversely step 1.1 covers every valid machine and assigns the empty domain to malformed or invalid-output indices. This proves the normal form and both inclusions of classes, including functions undefined everywhere. No complexity bound on the compiler or search is asserted.