1
$\begingroup$

This question has probably been asked elsewhere, but I cannot for the life of me find the answer. I understand as follows: set of primitive recursive functions is not enumerable by some primitive recursive function, but it is recursively enumerable (i.e. enumerable by some total recursive function). We can show the former via diagonalization, in much the same manner with which we can show that the set of total recursive functions is not recursively enumerable (hence, of course, not recursive either). The set of all recursive functions (i.e. both total and partial) is, however, recursively enumerable (but not recursive?).

My question is: Is the set of primrec functions recursive? Intuitively the problem with a recursive enumeration of all total functions is, well, deciding whether some function is defined for a particular input. But primrec functions take all the form of bounded for loops, so that shouldn't be a problem? (I.e. there is no issue wrt whether the function may or may not terminate, so perhaps one should be able to effectively enumerate/decide all primrec functions?)

$\endgroup$
8
  • 6
    $\begingroup$ How are we representing sets of functions here? Are you asking if the index set $\{e: \mbox{$\phi_e $ is equivalent to a p.r. function}\}$ is recursive? (If so, almost nothing of this sort is recursive, by Rice's theorem.) $\endgroup$ Commented Mar 27 at 4:55
  • 1
    $\begingroup$ What is true is there is a recursive set index $P$ such that $\{\phi_e : e \in P\}$ is the set of all primitive recursive functions (but there will still be $e \notin P$ such that $\phi_e$ is primitive recursive). To see why it's difficult to decide if an arbitrary program computes a primitive recursive function, think about a program like this: "take an input $n$. If there is an odd perfect number in $\{1, \dotsc, n\}$, then return $1$, else return $A(n, n)$" (can you use this idea to reduce to the halting problem..?) $\endgroup$ Commented Mar 27 at 10:31
  • $\begingroup$ @IzaakvanDongen I'm not too sure I fully follow (though I will attempt to). (What do you mean when you simultaneously say that $\{\phi_e : e \in P\}$ is the set of all primitive recursive functions, yet there are $\phi_e$ not in that set which are primitive recursive? Is that not contradictory?) My (it seems wrong) intuition for why the primitive recursive functions should be recursive is as follows: One "builds" the (primitive) recursive functions step by step, beginning off the "base" functions (zero, successor, projections) and then utilizing composition, primitive recursion [...] $\endgroup$ Commented Mar 31 at 19:22
  • 1
    $\begingroup$ The point that spaceisdarkgreen and I are making is that there is a distinction between a(n index of a) program ($e$) and the function it computes ($\phi_e$). There will always be multiple programs computing any recursive function. Strictly, it doesn't make sense to talk about whether a set of functions is recursive - you have to specify a representation/encoding of those functions, which is usually as programs/codes. $\endgroup$ Commented Apr 1 at 11:03
  • 2
    $\begingroup$ When you say "the set of primitive recursive functions", the definite article there makes the natural interpretation "the set of all programs that compute a primitive recursive function". This set is not recursive, because predicting the behaviour of an arbitrary program is hard (cf Rice's theorem, my odd perfect numbers example). In my comment, I interpreted your question charitably as "is there a recursive set of programs such that every primitive recursive function is computed by some program in the set", and the answer to that is yes for the reason you give. $\endgroup$ Commented Apr 1 at 11:04

0

Reset to default

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.