"Rice (like) Theorem" for primitive recursive functions?

Question

As primitive recursive (PR) functions seem to be so important (see for instance Kleene normal form Theorem) we may expect that many decision questions related to PR functions are undecidable.

(INPUT) A description of a PR function f (say by the usual definition or by a LOOP program),  

(QUESTION) Does the (mathematical) function f have the property P?

perhaps conjecture something like:

*Any non trivial (universally or existentially) quantified property of PR functions is undecidable.

Note. Example of such a nontrivial, quantified property
$P:\;\;\forall n [ (f(n)=0) \vee (f(n)>=5) ]$

Answer to "Is it clear that your example property is undecidable?" – Noah S 13 mins ago

Given a TM $M$ with index $e$ define f(n) that outputs 1 if the computation $M(0)$ halted in exactly $n$ steps, and outputs 0 otherwise. There is a PR such function $f$; P(f) holds iff the computation $M(0)$ does not halt.

Answer 1

This turns out there are (at least) two different interesting things you can say depending on how you interpret the question. Let $P$ be a subset of the set of primitive recursive functions. Then we can define the following:

1. Say $P$ is decidable if there is a recursive function, that given the code for a primitive recursive function returns $1$ if the function it codes is in $P$, and returns $0$ otherwise.

2. Say $P$ is primitive recursive decidable if there is a primitive recursive function, that given the code for a primitive recursive function returns $1$ if the function it codes is in $P$, and returns $0$ otherwise.

You can now say the following:

1. For primitive recursive decidable sets a result very similar to Rice's Theorem holds: any primitive recursive decidable set is either empty, or the set of all primitive recursive functions.

2. For decidable sets there definitely is not such a theorem. There are not only decidable sets that are non-trivial, but sets that are in some sense "strictly" existential. (This is somewhat surprising, and definitely would not be true, if you say, asked the same question for all total recursive functions)

Primitive Recursive Decidable

First of all note that there is no primitive recursive function $F$ such that given $e$ coding a primitive recursive function $F(e)=0$ when $\{e\}(e)=0$ and $F(e)=1$ when $\{e\}(e)\neq 0$, by a standard diagonalisation argument.

Now suppose that there is a non-trivial subset of primitive recursive functions that is primitive recursive decidable. Then there are primitive recursive functions $f$ and $g$, and a primitive recursive function $G$ such that if $e$ codes $f$, then $G(e)=0$ and if $e$ codes $g$, then $G(e)=1$. However, if we are given a primitive recursive function $e$, then we can convert it in a primitive recursive way to another primitive recursive function that is $f$ if $\{e\}(e)=0$, and $g$ otherwise. But this would allow us to construct the $F$ from the previous paragraph, giving a contradiction.

Decidable

There is a decidable predicate $P$ that is discontinuous. (That is, there is a primitive recursive $f$ such that $P(f)=0$, but for every $N$ there is a primitive recursive function $f'$ such that $f(n) = f'(n)$ for $n < N$, but $P(f') = 1$).

Proof: Let $e_n$ be a recursive enumeration of (codes for) the primitive recursive functions, and define $F(n) := \max_{n' \leq n}(\{e_{n'}\}(n)) + 1$. Note that we have defined $F$ so that it is recursive (although obviously not primitive recursive) and so that for every $e$ coding a primitive recursive function, and every $n > e$, $F(n) > \{e\}(n)$. Define $P$ so that $P(f) = 1$ if there is some $n \in \mathbb{N}$ such that $f(n) > F(n)$ and $P(f)=0$ otherwise. Note that $P$ is decidable, because if we are given $e$ coding a primitive recursive function, we know that for $n > e$, $\{e\}(n) < F(n)$, so we only have to check whether or not $\{e\}(n) \leq F(n)$ for all $n \leq e$, but we can just do this by brute force. Finally, to show $P$ is discontinuous, note that if $f$ is the constant $0$ function, then $P(f) = 0$, but we can easily find for any $N$ a primitive recursive $f'$ that is zero for $n < N$ such that $P(f') = 1$ (eg $f'(N) = F(N) + 1$, and $f'(n) = 0$ for $n \neq N$).

Answer 2

It happens that there do exist non-trivial universal properties that are decidable. An example of such a property is expressed in terms of what we could call ``primitive recursive Kolmogorov complexity''.

Definition. If $v=(v_0,\ldots,v_{n-1})$ is a sequence of natural numbers then let $K_{pr}(v)$ be the size of a shortest LOOP program computing a function $f$ extending $v$, i.e. satisfying $f(0)=v_0,\ldots,f(n-1)=v_{n-1}$.

Unlike the usual notions of Kolmogorov complexity, $K_{pr}$ is computable. However it is not primitive recursive.

For a function $f$, let $f|n$ be the finite sequence $(f(0),\ldots,f(n-1))$.

Claim. The property $$\forall n, K_{pr}(f|n)\leq n$$ is decidable, given a LOOP program for $f$.

Proof. Given a loop program $p$ for $f$, one has $K_{pr}(f|n)\leq |p|$ for all $n$. In order to check the property, one can only look at $n<|p|$. As $K_{pr}$ is computable, the property is decidable.

Observe that the property is not decidable if one is only given $f$ as oracle, as no finite prefix of $f$ is sufficient to ensure the property: for each finite sequence $v=(v_0,\ldots,v_{n-1})$ there is $v_n$ such that $K_{pr}(v_0,\ldots,v_n)>n+1$ hence no extension of $(v_0,\ldots,v_n)$ satisfies the property (the property is a closed subset of the Baire space that has empty interior).

More generally and for the same reasons, if $h:\mathbb{N}\to\mathbb{N}$ is a computable non-decreasing unbounded function then the property $P_h$ defined by $$f\in P_h\iff\forall n, K_{pr}(f|n)\leq h(n)$$ is decidable given a LOOP program for $f$ but not given $f$ as oracle. If $h(1)$ is sufficiently large then $P_h$ is non-empty as it contains all the functions computed by LOOP programs of size $\leq h(1)$.

An analog of Rice and Rice-Shapiro theorem.

So far, we know some basic properties that are decidable: extending a finite sequence $v$ (decidable given $f$), the property $P_h$ of having $h$-compressible prefixes (decidable given a LOOP program). Now, there is an analog of Rice and Rice-Shapiro theorems, stating that they form a ``subbasis'' (as in topology) of the semi-decidable properties: every semi-decidable property can be obtained as a union of finite intersections of these simple properties.

Theorem. Let $P$ be a property of primitive recursive function. The following are equivalent:

• $f\in P$ is semi-decidable given a LOOP program for $f$,
• $P$ is a computable disjunction of properties of the form $$ f\text{ extends $v$ and }\forall n, K_{pr}(f|n)\leq h(n). $$

The result is more general as it applies to any class of total computable functions that can be computably enumerated (for instance the polynomial-time computable functions, the provably total computable functions, etc.). All this can be found in the paper http://arxiv.org/abs/1503.05025.

Answer 3

Here is why one cannot get such a result under one reasonably definition of "nontrivial".

Let $g$ be a total recursive but not primitive recursive function. Consider the property $$ \varphi(f)\quad \Longleftrightarrow\quad f(0)=0 \vee (\forall n)(f(n)=g(n)) $$ This is a nontrivial quantified property in the sense that $$\{f\in \omega^{\omega}: \varphi(f)\}$$ is a $\Pi^0_1$ but not $\Delta^0_1$ subset of Baire space. However, it is a decidable property of primitive recursive functions since it is equivalent to $f(0)=0$.