A ("Rice-like") conjecture about the decidability of primitive recursive (PR) problems

Question

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:

---

Conjecture

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.

Notes.

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

Answer 1

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.

Answer 2

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