7
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Is it clear that your example property is undecidable? $\endgroup$ – Noah Schweber Jan 22 '14 at 18:34
  • $\begingroup$ Given a TM M with index e define a PR function f(n) that outputs 1 if the computation M(0) halts in exactly n steps, and outputs 0 otherwise. The property P(f) holds iff the computation M(0) does not halt. $\endgroup$ – Armando Matos Jan 24 '14 at 11:26
  • $\begingroup$ You can do this for a very restrictive form of "nontrivial universally quantified property" $ \forall x P(x, f(x))$ where $P$ is some two-variable predicate such that there exists a primitive recursive function $f_1$ with this property and a primitive recursive function $f_2$ such that $P(x,f_2(x))$ is false for infinitely many $x$. Build a function $f_3$ that switches between $f_1$ and $f_2$ depending on some other undecidable problem. This also works with the dual notion for existentially quantified property. $\endgroup$ – Will Sawin Jan 26 '14 at 1:10
7
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Very interesting! 2 questions: $\endgroup$ – Armando Matos Jan 27 '14 at 9:03
  • $\begingroup$ 1) Isn't PR decidable very weak? It can't even answer if $f(0)=0$, where $f$ is the input function. 2) What is the relationship between the existence of discontinuous predicates and Rice-like PR theorems? $\endgroup$ – Armando Matos Jan 27 '14 at 9:09
  • $\begingroup$ Yes, PR decidable is very weak, but I feel this is similar to decidable for partial recursive functions by the usual Rice's theorem. I mentioned the discontinuous example mostly just because I found it surprising, but there's a couple of things I can say. $\endgroup$ – aws Jan 27 '14 at 10:49
  • $\begingroup$ In the question you asked about properties that use quantifiers in a non trivial way, and I feel the discontinous predicate is such a property, but it is still decidable. (If you were given the function as input, as an oracle say, rather than a code for the PR program, then you would have to "evaluate the function on every input" to decide if it satisfied the property. In particular it would no longer be decidable) $\endgroup$ – aws Jan 27 '14 at 10:49
  • $\begingroup$ Also, for total recursive functions one can show that every decidable set is clopen as a subset of Baire space, which I guess is in a similar format to (the contrapositive of) Rice's theorem. But by the example this is not true for PR functions. $\endgroup$ – aws Jan 27 '14 at 10:50
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ $K_{pr}$ can be seen as an approximation from above to the normal Kolmogorov complexity for strings. Is it known how good this approximation is in the worst/best/average case? $\endgroup$ – Martin Berger Mar 19 '17 at 21:15
  • 1
    $\begingroup$ Time-bounded versions of Kolmogorov complexity have been studied there and there. You fix some time bound, i.e. some function $t:\mathbb{N}\to\mathbb{N}$ like $t(n)=n^2$ or $e^n$. Then for a binary string you define $K^t(x)$ as the size of a shortest program computing $x$ in time at most $t(|x|)$. Under reasonable assumptions on $t$, one can prove that $K^t$ coincides with normal Kolmogorov complexity for infinitely many $x$'s. The same kind argument probably implies the same result for $K_{pr}$. $\endgroup$ – Mathieu Hoyrup Mar 21 '17 at 8:31
  • 1
    $\begingroup$ Approximating Kolmogorov complexity in the average case is not really relevant, because it has a trivial computable approximation which is good on average, but is not informative: the length of the string! For a binary string $x$ of length $n$, $K(x)\leq n$ and $K(x)$ is close to $n$ by a constant $c$ for $x$ in a set of measure $1-2^{-c}$ (this is for plain complexity, but there are similar bounds for other notions of Kolmogorov complexity, like prefix-free or monotone complexity). $\endgroup$ – Mathieu Hoyrup Mar 21 '17 at 8:42
  • $\begingroup$ Thanks. Why the restriction to of coincidence merely for infinitely many $x$? What goes wrong in the other cases? $\endgroup$ – Martin Berger Mar 21 '17 at 13:25
  • 2
    $\begingroup$ Kolmogorov complexity $K(x)$ is not a computable function, so coincidence cannot happen everywhere. If $K$ was computable, you could produce strings of large complexity using a simple algorithm, so those strings would be compressible, contradiction! Precisely, if $K(x)\geq f(x)$ for computable $f$ and all $x$, then for each $k$ you can write a program of size roughly $log(k)+c$ bits ($c$ does not depend on $k$) that outputs the first string $x$ such that $f(x)\geq k$. This $x$ has complexity at most the size of this program, $log(k)+c$, but at least $f(x)\geq k$. Contradiction for large $k$! $\endgroup$ – Mathieu Hoyrup Mar 22 '17 at 14:59
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ An alternative definition of "nontrivial" is that it does not coincide with a $\Delta^0_1$ set on the primitive recursive functions. But then, of course, it is by definition undecidable. $\endgroup$ – Bjørn Kjos-Hanssen Jan 22 '14 at 19:30
  • 1
    $\begingroup$ This is an interesting answer. In an eventual "Rice Theorem for PR functions" we have to clarify what a "quantified, nontrivial question" is. For instance, the following "$\exists n : f(0)=1+n$" is not such question because it is quantified and nontrivial, but decidable. $\endgroup$ – Armando Matos Jan 24 '14 at 10:01
  • $\begingroup$ That one is $\Delta^0_1$ in Baire space: $\{f:f(0)\ge 1\}$ $\endgroup$ – Bjørn Kjos-Hanssen Jan 24 '14 at 18:18

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.