URM Computable Function is Recursive

From ProofWiki
Jump to navigation Jump to search

Theorem

Every URM computable function is recursive.


Proof

Let $f: \N^k \to \N$ be a URM computable function.

Then by hypothesis there is a URM program that 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$.


Consider the function $g: \N^k \to \N$ given by:

$\map g {n_1, n_2, \ldots, n_k} \approx \map {\mu t} {\tuple {\map {S_k} {e, n_1, n_2, \ldots, n_k, t} }_1 > \map \len e}$

where:

$\map \len e$ is the length of $e$
$\mu t$ is the minimization operation on $S_k$
$\approx$ denotes partial function equality
$\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}$
the number $\tuple {\map {S_k} {e, n_1, n_2, \ldots, n_k, t} }_1$ is the code number of the instruction about to be carried out at stage $t$.

So the inequality:

$\tuple {\map {S_k} {e, n_1, n_2, \ldots, n_k, t} }_1 > \map \len e$

expresses the fact that at stage $t$ the computation has halted.

So the value of $\map g {n_1, n_2, \ldots, n_k}$ is the state code of the first stage at which computation has halted, if there is one, and undefined otherwise.

Since the functions in this inequality, and the sign $>$ itself, are all primitive recursive, it follows that the inequality expresses a primitive recursive relation on $e, n_1, n_2, \ldots, n_k, t$.

Thus $g$ is a recursive function by definition, as it can be obtained by minimization on a recursive relation.


Now consider the function $h: \N^k \to \N$ given by:

$\map h {n_1, n_2, \ldots, n_k} \approx \map {S_k} {e, n_1, n_2, \ldots, n_k, \map g {n_1, n_2, \ldots, n_k} }$

This is recursive because it was obtained by substitution from known recursive functions.


Now $\map h {n_1, n_2, \ldots, n_k}$ is defined iff the computation halts, and it gives the value of the state code when it has halted.

The output of this computation, which gives the value of $f$, is the number in register $R_1$.

But the number in $R_1$ is the exponent of $p_2 = 3$ in the expression of the state code $\map h {n_1, n_2, \ldots, n_k}$ in the form $p_1^a p_2^{r_1} p_3^{r_2} \cdots p_{k + 1}^{r_k}$.

Thus the function $f$ is given by:

$\map f {n_1, n_2, \ldots, n_k} \approx \tuple {\map h {n_1, n_2, \ldots, n_k} }_2$.

It follows that $f$ is a recursive function, since it is obtained by substitution from known recursive functions.

$\blacksquare$


Attempt at Disproof

It is tempting to apply the same argument as in Not All URM Computable Functions are Primitive Recursive show that there exist recursive functions that are not URM computable.

However, that argument does not work here, as we show:


From Universal URM Computable Functions‎, we have a URM computable function $\Phi_1: \N^2 \to \N$ such that for each URM computable function $f: \N \to \N$ there exists a natural number $e$ such that:

$\forall n \in \N: \map f n \approx \map {\Phi_1} {e, n}$

Now suppose the function $g$ is obtained from $\Phi_1$ by putting:

$\map g n \approx \map {\Phi_1} {n, n} + 1$

Then $g$ is URM computable and so there exists $e_0 \in \N$ such that:

$\forall n \in \N: \map g n \approx \map {\Phi_1} {e_0, n}$

Hence

$\map g {e_0} \approx \map {\Phi_1} {e_0, e_0}$

whereas we have just constructed $g$ so that:

$\map g {e_0} \approx \map {\Phi_1} {e_0, e_0} + 1$

So this gives us:

$\map {\Phi_1} {e_0, e_0} \approx \map {\Phi_1} {e_0, e_0} + 1$

Have we just proved a contradiction?

No, because $\Phi_1$ is a partial function, and all this tells us is that either both sides are defined and equal, or neither side is defined.

The first is impossible, and the second just leads us to the innocuous conclusion that $\map {\Phi_1} {e_0, e_0}$ is not defined, rather than that there is a URM computable function which is not recursive.


Note

Putting all the above equations together, we note that:

$\map f {n_1, n_2, \ldots, n_k} \approx \tuple {\map {S_k} {e, n_1, n_2, \ldots, n_k, \map {\mu t} {\tuple {\map {S_k} {e, n_1, n_2, \ldots, n_k, t} }_1 > \map \len e} } }_2$

This works for every recursive function of $k$ variables.

The only thing that changes as we vary $f$ is the number $e$.

Thus the formula gives what is known as a normal form for recursive functions.

Hence, see Kleene's Normal Form Theorem.