4
$\begingroup$

If $g:\mathbb{N}\to\mathbb{N}$ is primitive recursive and $f:\mathbb{N}\to\mathbb{N}$ is computable such that $f(n) \leq g(n)$ for all $n\in \mathbb{N}$, does this imply that $f$ is primitive recursive?

$\endgroup$
12
$\begingroup$

No. Let $g$ be the constant function 1.

Let $\{h_n\}$ be a computable list of all primitive recursive functions and let $f_n(x)=\min(h_n(x),1)$.

So $\{f_n\}$ is a computable list of all primitive recursive functions bounded by 1.

Now let $F(n)=1-f_n(n)$. Then $F$ is another computable function bounded by 1, distinct from all the $f_n$, so $F$ is not primitive recursive.

| cite | improve this answer | |
$\endgroup$
9
$\begingroup$

No, as Bjørn explained in his answer, but it is a lower set in the class of functions with primitive recursive graphs. Specifically, if $f:\mathbb{N}^k\to\mathbb{N}$ is such that

  • The function $g:\mathbb{N}^{k+1}\to\{0,1\}$ such that $g(x_1,\ldots,x_k,y) = 1 \iff f(x_1,\ldots,x_k) = y$ is primitive recursive, and
  • There is a primitive recursive function $h:\mathbb{N}^k\to\mathbb{N}$ such that $f(x_1,\ldots,x_k) \leq h(x_1,\ldots,x_k)$,

then $f$ is primitive recursive.

The reason is that we can recover $f$ by bounded search: $$f(x_1,\ldots,x_k) = \mu y \leq h(x_1,\ldots,x_k)\,[g(x_1,\ldots,x_k,y) = 1].$$

Note that there are many functions that are not primitive recursive but whose graphs are primitive recursive, for example the Ackermann function has a primitive recursive graph. This fact is useful to show that the inverse Ackermann function is primitive recursive, for example.

| cite | improve this answer | |
$\endgroup$

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.