[Math] “Rice (like) Theorem” for primitive recursive functions

computability-theory

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.

Best Answer

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

Related Question