Kleene's Normal Form Theorem

== Theorem ==
For each integer $k \ge 1$, there exists:
:a primitive recursive $k + 1$-ary relation $T_k$
:a primitive recursive function $U: \N \to \N$
such that a partial function $f: \N^k \to \N$ is recursive , for some $e \in \N$ and all $\tuple {n_1, n_2, \ldots, n_k} \in \N^k$:
:$\map f {n_1, n_2, \ldots, n_k} \approx \map U {\mu z \ \map {T_k} {e, n_1, n_2, \ldots, n_k, z} }$
== Proof ==
See the proof of URM Computable Function is Recursive for an explanation of the symbols used here.
=== Necessary Condition ===
Suppose $e = \map \gamma P$ codes a URM program $P$ which computes $f$.
Suppose the computation using $P$ with input $\tuple {n_1, n_2, \ldots, n_k}$ halts at stage $t_0$ with output $q$.
Let $t > t_0$, that is, we "wait till after $P$ has finished".
Then $\map f {n_1, n_2, \ldots, n_k} = q$.
Since $P$ has halted at stage $t_0$:
:$\paren {\map {S_k} {e, n_1, n_2, \ldots, n_k, t} }_1 > \map \len e$
where:
:$\map {S_k} {e, n_1, n_2, \ldots, n_k, t}$ is the state code at stage $t$ of the computation of $P$ with input $\tuple {n_1, n_2, \ldots, n_k}$
:$ \map \len e$ is the length of $e$
:the number $\paren {\map {S_k} {e, n_1, n_2, \ldots, n_k, t} }_1$ is the value of the instruction pointer to the instruction about to be carried out at stage $t$
:$\tuple z_j$ is the prime exponent function.
Since the output is $q$:
:$\paren {\map {S_k} {e, n_1, n_2, \ldots, n_k, t} }_2 = q$
Let us put $z_0 = 2^q 3^{t_0}$.
Then:
:$\tuple {z_0}_2 = t_0$ and $\tuple {z_0}_1 = q$
Thus:
:$\paren {\map {S_k} {e, n_1, n_2, \ldots, n_k, \tuple {z_0}_2} }_1 > \map \len e$
and
:$\tuple {z_0}_1 = \paren {\map {S_k} {e, n_1, n_2, \ldots, n_k, \tuple z_2} }_2$
Now $z_0$ is the smallest integer with these properties, because $\tuple {z_0}_2 = t_0$ is the stage at which $P$ halts.
Thus we have:
:$\map f {n_1, n_2, \ldots, n_k} = q = \tuple {z_0}_1$
Now we let $\map {T_k} {e, n_1, n_2, \ldots, n_k, z}$ be the relation defined as:
Then $T_k$ is a primitive recursive $k + 1$-ary relation.
Also, we can take $U: \N \to \N$ to be the primitive recursive function given by $\map U z = \tuple z_1$.
=== Sufficient Condition ===
Now let $f$ be a recursive function.
Then by Recursive Function is URM Computable, there exists some URM program which computes $f$.
Let $P$ be the URM program with the smallest code number that computes $f$.
Let $e = \map \gamma P$ be the code number of $P$.
Suppose $\map f {n_1, n_2, \ldots, n_k}$ is defined.
Then from the above, we deduce that $\mu z \ \map {T_k} {e, n_1, n_2, \ldots, n_k, z}$ is defined.
Let $z_0 = \mu z \ \map {T_k} {e, n_1, n_2, \ldots, n_k, z}$.
Then:
:$\tuple {z_0}_1 = \map f {n_1, n_2, \ldots, n_k}$
That is:
:$\map U {z_0} = \map f {n_1, n_2, \ldots, n_k}$
Hence:
:$\map f {n_1, n_2, \ldots, n_k} = \map U {\mu z \ \map {T_k} {e, n_1, n_2, \ldots, n_k, z} }$
as required.
On the other hand, suppose $\map f {n_1, n_2, \ldots, n_k}$ is undefined.
Then the computation using $P$ with input $\tuple {n_1, n_2, \ldots, n_k}$ does not halt.
So there is no $z$ such that $\map {T_k} {e, n_1, n_2, \ldots, n_k, z}$.
So $\map U {\mu z \ \map {T_k} {e, n_1, n_2, \ldots, n_k, z} }$ is undefined.
Thus:
:$\map f {n_1, n_2, \ldots, n_k} \approx \map U {\mu z \ \map {T_k} {e, n_1, n_2, \ldots, n_k, z} }$
as defined in partial function equality.
Category:Recursion Theory