Set of Total Functions is Not Recursive

From ProofWiki
Jump to navigation Jump to search

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:

$\Phi_1$ and $h$ are both recursive
The program coded by $m$ halts for all inputs $n$.

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$