# Is the set of total recursive functions countable?

There are many reasons to hold that the set of total recursive functions is countable, and among them the two following seem to me to be very powerful and sound :

• The set of total recursive functions is a strict subset of the set of partial recursive functions, which is countable.
• A total recursive function can be calculated by an algorithm. Since algorithms are made of a finite number of symbols, the set of all possible algorithms is countable. Thus, the set of total recursive functions is itself countable.

However, it seems to me that the following argument is proving that the set of total recursive functions is not countable (but I think we have to accept the axiom of choice for countable sets) :

1) Suppose that the set of total recursive functions is countable. Then there exist a bijection between this set and the set of natural numbers. Consider such a bijection $h$ from $\mathbb N$ into the set of total recursive functions : through $h$, you can enumerate the set of total recursive functions as following : for all $n$ and all total recursive function $f$, $h(n) = f_n$ (the $n$-th function in the enumeration is thus the image of $n$ by $h$). Here it's worth noting that we do not suppose that this enumeration is recursive, because $h$ itself is not total recursive. So we have an enumeration of total recursive functions, and, in spite of the fact that this enumeration is not recursive, for all $n$, $f_n$ is well defined.

2) We build a set of functions $\{k_i\mid i\in\mathbb N\}$, such that for all $i\in\mathbb N$, $k_i(n) = 1$ if $n = i$, and $0$ otherwise. Clearly, all the $k_i$ are recursive.

3) Now consider the following function $g$ defined this way : $$g(x) = f_n(n) +1 \text { iff } k_n(x) = 1$$

So the function will look like this :

$$g(0) = f_0(0) + 1$$ (since $k_0(0) = 1$, and for all integer $i\neq 0$, $k_i(0) = 0$)

$$g(1) = f_1(1) + 1$$ (same reasoning)

And so on...

This function looks very much like the famous diagonal function used to prove that the set of total recursive functions is not recursively enumerable, except that in this case $g$ is defined by conditions, and all the functions used in the definition (the $f_n$ and the $k_n$, and the successor function) are also recursive : so it looks like (but this is a very unclear point to me, and I'm aware that the whole argument lays on that very point) $g$ is a total recursive function, even though the enumeration is not recursive. But then obviously a contradiction arises, for if $g$ is recursive, then there exists an integer $n$ such that $g = f_n$, and thus, for $g(n)$, since $k_n(n) = 1$, $g(n) = f_n(n) = f_n(n) + 1$

Since our only hypothesis is that the set of total recursive functions is countable, and given the fact that we are lead to a contradiction, we should therefore conclude that the set of total recursive functions is not countable. Now, as you have certainly remarked, the whole problem lies in the question whether $g$ is recursive even though the enumeration of the total recursive functions is not : but again, since it's defined by conditions and using only recursive functions, I have trouble to see exactly why it can't be recursive (maybe a formal answer, showing that a rigorous definition of $g$ uses a recursive enumeration of the set of total recursive functions would do the job very well).

-
In this sentence: "for all $h$ and all total recursive function $f$, $h(n) = f_n$ (the $n$-th function in the enumeration is thus the image of $n$ by $h$)" you never use $f$, you just use $f_n$. Do you mean that $h(n)=f$ for some $n$? –  Thomas Andrews May 26 '12 at 20:50
There is yet another confusion in your post: in the definition of $g(x)$, the number $n$ comes out of the blue. Since the condition $k_n(x)=1$ is just another way of saying $n=x$, it is clear that this condition is satisfied for exactly one $n$, so why not say simply "$g(x)=f_x(x)+1$" ? Since you explcitly admit that the enumeration of the $f_n$, that is the function that assigns $f_n$ to $n$, is not recursive, how can you say that every function that goes into the definition of $g$ is recursive? –  Marc van Leeuwen May 26 '12 at 21:15

Why do you think that $g$ is total recursive? That's a pretty huge leap.

I'm not sure why you think that defining $g$ as:

$$g(x) = f_x(x)+1$$

Is any different than:

$$g(x) = f_n(n)+1\text{ iff } k_n(x)=1$$

Since $k_n(x)=1$ exactly when $x=n$. The $k_i$ seem to be used to obfuscate. They don't make the definition of $g$ any more recursive, because $n\to f_n$ is still not recursive.

The only way to show that a function is recursive is to show a way to compute it. In particular, you can't use $f_x(x)$ to compute it, because the function $h(n,i)=f_n(i)$ is not recursive. Unless you can show a way to compute $g$ without reference to $f_n$ you have not show that $g$ is recursive.

Yes, if we could write infinite computer programs/Turing machines, or whatever, then your code for defining $g(0)=f_0(0)+1$, $g(1)=f_1(1)+1$, etc. would be allowed. But if you could write infinite programs, you could come up with any function $\mathbb N\to\mathbb N$, and your statement that there are only countably many recursive functions would be false.

Computability and recursive functions are about starting with finite definitions of functions. You have to completely tell me how to compute the function with a finite program. You have not done so.

Let's say that you have any function, $H:\mathbb N\to\mathbb N$.

By your reasoning, we could define:

$$G(x) = H(n)\text { iff } k_n(x)=1$$

Because we can define:

$$G(0) = H(0)$$ $$G(1) = H(1)$$ $$...$$

That's patently absurd - this is not a "method" for computing $G$, it's just a statement that $G=H$. If you don't know how to compute $H$, we certainly don't know how to compute $G$. But that's essentially your argument.

-

The error in the proof is that you did not show that $g$ is computable. You need to remember that at the beginning, there is a listing of partial computable functions $\Phi_e$.

Let $\Phi_e$ be a listing of all partial computable functions. Your $h$ is a function such that $\Phi_{h(n)}$ is computable for all $n$. And if $\Phi_m$ is total, there exists a $n$ such that $h(n) = m$. That is, $h$ is a listing of all the total computable functions. You defined $f_n$ as $h(n)$ which is some listing of all total computable functions. $h$ is not a computable function by the usual computability theory argument.

Then you defined $g(x) = f_n(n) + 1$ if and only if $k_n(x) = 1$.

Just because $k_n(x) = 1$ can be computably determined does not mean $g$ is computable if the listing $f_n$ is not computable. Imagine trying to compute $g(x)$. You need to ask if $k_n(x) = 1$, which is fine. If indeed $k_n(x) = 1$, then you need to compute $f_n(n)$. In order to compute $f_n(n)$, your need to compute $\Phi_{h(n)}(n)$. But $h$ is not computable.

The essence of the argument is that the computation of $g$ does not depend only on the computable function $k_n$ but also the listing of total computable functions $h$, which you must be noncomputable.

-

You have not shown that the two variable function function $w(i,n)=f_i(n)$ is recursive, and indeed it cannot be. That's where the argument breaks down.

The argument for countability that you give at the beginning is a bit informal, but correct.

-
I think you're mistaken here. This $w$ is just the Dirac $\delta$ (equality test), which is certainly recursive. –  Marc van Leeuwen May 26 '12 at 21:25
@MarcvanLeeuwen: Thanks, fixed. –  André Nicolas May 26 '12 at 22:03
More than that diract functions are computable, you want then to be uniformly computable. Let $K$ be the halting problem. For example, $f_n$ is the constant function $0$ if $n \notin K$ or $f_n$ is the constant function $1$ if $n \in K$. Each $f_n$ is computable since each $f_n$ is is just a constant $0$ or $1$. However, it is not uniformly computable in the sense that the function $g(n,m) = f_n(m)$ is computable. –  William May 26 '12 at 22:12