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?

  • 4
    $\begingroup$ $\mathbb{N}$ is a computable set, as is the empty set, but there are uncountably many subsets of $\mathbb{N}$ that are not computable. $\endgroup$ – Matt Samuel Dec 12 '15 at 16:33
  • 1
    $\begingroup$ The hard part is being able to tell whether one of the partial recursive functions is a total recursive function. Despite there being uncomputable sets of integers, you can list every integer. The problem is knowing whether that integer lies in a particular set. $\endgroup$ – Matt Samuel Dec 12 '15 at 16:39

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).

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.