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$ $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:

  • $\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 $\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$