# 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$ | $Z \left({n}\right)$ |

which computes the zero function.

Its code number is $2^3 = 8$.

So we can define the recursive function $h$ as:

- $h \left({n}\right) = \begin{cases} 8 & : n = 0 \\ \mu z \left({z \in \operatorname{Tot} \text { and } h \left({n-1}\right) < z}\right) & : 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, $h \left({n}\right)$ 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 $h \left({n}\right)$ computes $f$.

Now we define the function $\Phi: \N^2 \to \N$ as:

- $\Phi \left({m, n}\right) = \Phi_1 \left({h \left({m}\right), n}\right)$

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 $\Phi \left({m, n}\right) = f \left({n}\right)$ for all $n \in \N$.

Now we use Cantor's Diagonal Argument.

It follows immediately that the function $g: \N \to \N$ given by:

- $g \left({n}\right) = \Phi \left({n, n}\right) + 1$

is also recursive.

Hence there is some number $m_0$ such that:

- $g \left({n}\right) = \Phi \left({m_0, n}\right)$

for all $n \in \N$.

In particular:

- $g \left({m_0}\right) = \Phi \left({m_0, m_0}\right)$.

But from the definition of $g$:

- $g \left({m_0}\right) = \Phi \left({m_0, m_0}\right) + 1$.

This contradiction arose because we assumed that $\operatorname{Tot}$ is recursive.

Hence the result.

$\blacksquare$