Question: is the conjecture below true?

Consider decision problems in which the instance is (the PR index, definition, or LOOP program of) a primitive recursive function. Denote the PR function (with PR index $i$) by $\varphi_i$. Examples of PR problems (input $i$):

  • Problem P1 (decidable): let $n=\varphi_i(0)$. Are all integers $\varphi_i(1)$,..., $\varphi_i(n)$ prime?

  • Problem P2: (undecidable, see http://www.dcc.fc.up.pt/~acm/pr3.pdf): $\exists n:\varphi_i(n)=0$?

Conjecture. Looking to the program (index) is not more powerful than evaluating the function. In more detail:


The computational model $\langle$Turing machine M($i$) with the PR index $i$ of a PR function $\varphi_i$ as input$\rangle$ can not decide more properties than the (more restricted) model $\langle$Turing machine M$^f$ whose "input" is an oracle for computing $f(n)$ given $n$$\rangle$.

Definition (text from user aws). A property $P$ is decidable if there is a recursive function [computable, halting for all inputs] that, given the PR index $i$ of a PR function $\varphi_i$, returns 1 if the function $\varphi_i$ is in $P$, and returns 0 otherwise.


  1. The instance is a PR index ($\varphi_i$ is always PR), not a TM index. Say it represents a LOOP program, not a set of quadruples.

  2. There is some information that we can get by looking to the index of $f$. The maximum loop nesting of the LOOP program that defines $f$ allows us, in some cases, to establish a positive answer to to a question (property) like "$\exists n_0\forall n\geq n_0:f(n)\leq g(n)$?" (where $g$ is fixed and depends on that maximum nesting) is positive. But this is not sufficient to decide the property. Apparently this "semi-answer" cannot be obtained by the oracle machine $M^f$.

  3. In "Rice (like) Theorem" for primitive recursive functions? I posted a similar but more vague question (no conjectures). Excuse me if this problem is not appropriate to mathoverflow...

  • $\begingroup$ +1. This is a great question -- very subtle. You want to know essentially whether having the PR definition of a primitive recursive function gives you any extra information beyond the course of values of that function. $\endgroup$ Nov 26, 2014 at 17:08

2 Answers 2


Your conjecture is false. We can construct a recursive set $A$ such that if $\varphi_i = \varphi_j$, then $i \in A \iff j \in A$, but there is no Turing functional $\Gamma$ with $i \in A \iff \Gamma^{\varphi_i}(0)\!\!\downarrow$. This is a counterexample to your conjecture.

Let $(\Gamma_j)_{j \in \omega}$ be an enumeration of all Turing functionals.

We will build $A$ by keeping a collection of rules. These rules may change over time, but we will never change them in a way that contradicts what we have already defined of $A$. The ability to change these rules is the strength of using the index instead of the graph.

Basic rules will have the form: "any primitive recursive function that extends $\sigma$ is accepted/rejected", where $\sigma$ is some finite partial function. At stage $s$, we have two basic steps:

  • First, we consider $\varphi_s$. If there is already a rule that covers $\varphi_s$, we simply follow that rule. If there is not, we choose a number $k$ larger than any number mentioned in a rule so far and make the rule "any primitive recursive function that extends $\varphi_s\!\!\upharpoonright_k$ is accepted". Then we accept $\varphi_s$.
  • Then we check if there is any $\sigma$ with $|\sigma| < s$ and $\Gamma_{j,s}^\sigma(0)\!\!\downarrow$ for some $j < s$. If so, we choose some very large $n$ such that no $\varphi_i$ extends $\sigma*0^n*1$ for any $i \le s$. Then we add the rule "any primitive recursive function that extends $\sigma*0^n*1$ is rejected". This might contradict some of our earlier rules, though, so we remove any rule it contradicts. Then, for every $i \le s$ with $i \in A$, we add the rule "any primitive recursive function that extends $\varphi_i\!\!\upharpoonright_{|\sigma|+n+1}$ is accepted".

Now, there are a few things to check by induction:

  • Our rules are always consistent with each other, because we remove any contradictions.
  • If $i \in A$, then at every stage $s \ge i$, there is a rule saying that $i$ should be in $A$.
  • If $i \not \in A$, then at every stage $s \ge i$, there is a rule saying that $i$ should not be in $A$.

Then if $\varphi_i = \varphi_j$, suppose $i < j$. If $i \in A$, then at stage $j$, there is a rule saying $i \in A$. This same rule ensures that $j \in A$. Similarly if $i \not \in A$.

Edit: I forgot to mention the last point. Since $A$ is nonempty, any $\Gamma_j$ that hopes to describe $A$ must have some $\sigma$ such that $\Gamma_j^{\sigma}(0)\!\!\downarrow$. But then when we see such a $\sigma$, we will make a rule of the form "anything beginning with $\sigma*0^n*1$ is rejected". This rule never goes away (only positive rules are ever removed), and there is a primitive recursive function $\varphi_i$ beginning that way, so eventually we consider $\varphi_i$ and reject it, diagonalizing against $\Gamma_j$.

Edit2: I guess there's a more general phenomenon at work. Consider PR as a subspace of Baire space. A decision procedure that only considers the values of the function, without considering its index, can only decide a clopen set (in the subspace topology). On the other hand, using indices we can make a procedure that accepts a set which is neither open nor closed: assume that $\varphi_0 \neq \varphi_1$, declare $0 \in A$ and $1 \not \in A$, and then use a process like the above to make $\varphi_1$ an accumulation point of $A$ and $\varphi_0$ an accumulation point of the complement.

  • $\begingroup$ Dan, I am having some difficulty understanding your solution. At the very start, it seems that I consider $\varphi_0$, which is not covered by any rule (since none have yet been created), and so we create the rule that says any primitive recursive function beginning with $\varphi_0\upharpoonright 0$ is accepted. But since this is the empty function, it would seem to mean that all PR functions will be accepted, no? You do later change the rules, but you said "we will never change them in a way that contradicts what we have already defined of $A$." $\endgroup$ Nov 26, 2014 at 21:52
  • $\begingroup$ @JoelDavidHamkins, All PR functions will be accepted until we add a negative rule, at which point we'll remove that first rule. We don't make changes that contradict $A$, but we might make changes that contradict the earlier set of rules. As long as those contradictions don't change the elements we've already added to $A$, that's okay. $\endgroup$ Nov 26, 2014 at 22:31
  • $\begingroup$ Thanks for responding, but I still don't really understand it. It seems that you only add contrary rules when there is a $\sigma$ etc. that has not been "already dealt with," but it seems that everything is dealt with at stage $0$ as in my comment above, so this never happens. So why isn't $A$ everything? (Also, what is $\Gamma$? and what does it mean for a PR function to "begin with" a string?) I'm sorry for not understanding your argument... $\endgroup$ Nov 27, 2014 at 0:04
  • $\begingroup$ Sorry, I wasn't clear. When I said "not already dealt with", I was referring to $\Gamma_j$. $(\Gamma_j)_{j \in \omega}$ is intended to be a listing of all Turing functionals. We're using the second step to diagonalize against Turing functionals. For any function $f$ and string $\sigma$, $\sigma \prec f$ if $f(i) = \sigma(i)$ for all $i < |\sigma|$. That's what I meant by "begin with". It comes from thinking of functions as infinite sequences. $\endgroup$ Nov 27, 2014 at 0:17
  • $\begingroup$ I don't completely understand your construction. First a minor point, in step 2 what is $\Gamma^\sigma_{i,s}$ (with the pair (i,s) as subscript)? I think you are diagonalizing against ALL Turing functionals $\Gamma_0$, $\Gamma_1$,... But some of these functionals (with some PR functions as oracles) must be partial recursive functions. And it is not decidable if, say, $\Gamma^\sigma_j(0)$ converges (given $j$ and $\sigma$). But the construction of $A$ seems to depend on this halting problems (step 2), and so $A$ does not seem to be recursive. $\endgroup$ Dec 2, 2014 at 17:47

An analog of Rice and Rice-Shapiro theorem for primitive-recursive functions is now available. See https://mathoverflow.net/a/200312/69380


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.