Is the set of primitive recursive functions (on $\mathbb{N}$) effectively enumerable?

438 Views Asked by At

My intuition says that the set of PR functions on $\mathbb{N}$ are not effectively enumerable. I'm trying to come up with a diagonal argument to show this.

Suppose that $f_1,f_2,...$ was an enumeration of all PR functions. Of course, I'd like to show that there is some $g$ which is not on the list. My problem is trying to make sure that $g$ is not on the list, while still making sure $g$ is PR. Would it be possible to say that

\begin{equation} g(n) := \sum_{j=1}^n\sum_{i=1}^n f_j(i) \end{equation}

I believe that this would make $g$ primitive recursive and different from all of the $f$'s on the list. (The double sum might be overkill...)

Questions

  1. Is this approach correct?

  2. If not, can someone give me a hint or advice?

1

There are 1 best solutions below

7
On BEST ANSWER

Your idea shows that the primitive recursive functions are not primitive recursively enumerable, in the sense that there is no p.r. function $h$ of two variables such that for every p.r. function $f$ of one variable, for some $n$ we have $$f(x)=h(n, x)$$ for all $x$. The proof is as you've indicated: if such an $h$ existed, then we could build a p.r. function dominating every p.r. function, which is clearly a contradiction.

However, you're claiming something much stronger! The issue is that the argument above crucially uses the assumption that the "enumerator" $h$ is primitive recursive, not just recursive. If all we know is that $h$ is recursive, then there is no reason to believe that the $g$ we build will be primitive recursive, only that it will be recursive. And if $g$ isn't necessarily primitive recursive, we don't get a contradiction from the fact that $g$ isn't one of the $f_i$s! Indeed, the primitive recursive functions are effectively enumerable, in the sense that there is a total recursive function $j$ of two variables such that for each primitive recursive function $f$ of one variable there is some $n$ with $$f(x)=j(n, x)$$ for all $x$.

Incidentally, this is not trivial to prove. What you need to do is show that there is a way to give every p.r. function a "code," so that $(i)$ we can uniformly recursively compute the value of a p.r. function on a given input from that input and a code for the p.r. function, and $(ii)$ the set of codes for p.r. functions is recursive. From $(i)$ and $(ii)$ we can produce a total recursive $j$ enumerating the p.r. functions in the above sense: let $j(n, x)$ be the value of the p.r. function corresponding to the $n$th p.r. code, on input $x$. Rigorously proving $(i)$ and $(ii)$ requires some work.


Going beyond this specific question, the general theme is:

Suppose $\Gamma$ is a "reasonable" class of total recursive functions. Then there is no $\Gamma$-enumeration of the functions in $\Gamma$.

For example, there is no recursive enumeration of the total recursive functions. Note that "total" here is crucial: we can recursively enumerate the partial recursive functions, in the sense that there is a partial recursive function $u$ of two variables such that for every partial recursive function $f$ of one variable, for some $n$ we have $$f(x)\cong u(n, x)$$ (where "$a\cong b$" means "either $a$ and $b$ are each undefined, or are each defined and equal). It's a good exercise to think about why we can't use diagonalization to derive a contradiction from this (and incidentally this failed diagonalization attempt will ultimately lead to the recursion theorem).