Set of Total Functions is Not Recursive
Theorem
The set $\operatorname{Tot}$ of natural numbers which code URM programs which compute total functions of one variable is not recursive.
Proof
We perform a proof by Cantor's Diagonal Argument.
Suppose the contrary, that $\operatorname{Tot}$ is a recursive set.
First we define a recursive function $h$ which enumerates the code numbers of URM programs which compute total functions of one variable.
The program of this sort with the smallest code is:
Line | Command | |
---|---|---|
$1$ | $\map Z n$ |
which computes the zero function.
Its code number is $2^3 = 8$.
So we can define the recursive function $h$ as:
- $\map h n = \begin{cases} 8 & : n = 0 \\ \map {\mu z} {z \in \operatorname{Tot} \text { and } \map h {n - 1} < z} & : n > 0 \end{cases}$
where $\mu z$ is the minimization operation.
As there are infinitely many URM programs which compute a total function of one variable, $\map h n$ is always defined.
More importantly, if $f: \N \to \N$ is a total recursive function, there is some $m \in \N$ such that the URM program with code number $\map h n$ computes $f$.
Now we define the function $\Phi: \N^2 \to \N$ as:
- $\map \Phi {m, n} = \map {\Phi_1} {\map h m, n}$
where $\Phi_1$ is the universal URM computable function of one variable.
Then $\Phi$ is a total recursive function, because:
It has the property that if $f: \N \to \N$ is a total recursive function, there is some $m \in \N$ such that $\map \Phi {m, n} = \map f n$ for all $n \in \N$.
Now we use Cantor's Diagonal Argument.
It follows immediately that the function $g: \N \to \N$ given by:
- $\map g n = \map \Phi {n, n} + 1$
is also recursive.
Hence there is some number $m_0$ such that:
- $\map g n = \map \Phi {m_0, n}$
for all $n \in \N$.
In particular:
- $\map g {m_0} = \map \Phi {m_0, m_0}$
But from the definition of $g$:
- $\map g {m_0} = \map \Phi {m_0, m_0} + 1$
This contradiction arose because we assumed that $\operatorname{Tot}$ is recursive.
Hence the result.
$\blacksquare$