Recursive Enumeration of Total Recursive Functions vs Partial Recursive Functions

1.1k Views Asked by At

We have:

Primitive Recursive $\subseteq$ Total Recursive Functions $\subseteq$ Partial Recursive Functions

There are three points that appear at odds with eachother:

1) The primitive recursive functions are often called a recursively enumerable subset of the total recursive functions, hence the primitive recursive functions are r.e.

2) We know by the enumeration theorem that the Partial Recursive Functions can be encoded and given an effective enumeration. Where $[[e]]^{(n)}$ means the $n$-ary partial recursive function encoded by $e$ (defined for all $e \in \mathbb{N} $) we have:

$ [[1]]^{(n)}, [[2]]^{(n)},, [[3]]^{(n)},, ...$

Hence the partial functions are recursively enumerable.

3) I keep reading that the Total Recursive Functions are not r.e. It seems odd that the Total Recursive Functions, being sandwiched between two r.e. sets (the primitive recursive and partial recursive functions), are not r.e.

?) It appears a little bit contradictory to me: By generating an effective enumeration of all Partial Recursive Functions, because Total Recursive Functions are a subset of that enumeration, we have also enumerated all Total Recursive Functions and hence the Total Recursive Functions are recursively enumerable. What am I getting wrong here?

1

There are 1 best solutions below

4
On

The task is not to enumerate the (indices for the) total recursive functions - the problem is to enumerate the total recursive functions, and nothing else.

If I enumerate the partial recursive functions, then I've enumerated the total recursive functions + a bunch of "junk" - and that's not good enough!

Basically, there's two ways I could fail: I could fail to enumerate some total recursive function, or I could incorrectly enumerate some non-total recursive function. A straightforward diagonalization argument (see below) shows that you can't avoid both mistakes simultaneously: certainly we could get no false negatives (by enumerating all the partial recursive functions), or no false positives (by enumerating just the primitive recursive functions), but we can't do better than that.


Here's that diagonal argument mentioned above - I notice from your question it's not clear if you've seen the argument before, or only the statement (I work just with unary functions, for simplicity):

Suppose $\{e_i: i\in\omega\}$ is a recursive list of (indices of) total recursive functions. (When I say "recursive list," I mean there is some total computable $f$ such that $f(i)=e_i$; there are many other equivalent ways to say this.)

Then consider the function $$g(n)=1+\varphi_{e_n}(n)$$ (where $\varphi_k$ denotes the $k$th partial recursive function). Since my list was recursive, $g$ is recursive, and clearly $g$ is total; but also clearly $g\not=\varphi_{e_n}$, that is, $g$ isn't on my list.

What I've shown is that, if I avoid false positives (that is, I only enumerate total functions), then I have to have a false negative (that is, there's some total function I miss).