So I'm trying to solve this problem(problem 8 from section 3.4) of the book Computability, Complexity and languages by Martin Davis:

Let k be some fixed number, let f be a function such that f(x + 1) < x + 1 for all x, and let

h(O) = k
h(t + 1) = g(h(f(t + 1)))

Show that if f and g belong to some PRC class C, then so does h.

I can't seem to find the way although there is a hint given in the book. Any tips or solves would be much appreciated!


1 Answer 1


This is an interesting exercise.

All variables are non-negative integers.

Since $f(x+1)\lt x+1$ for all $x$, for any fixed $x$, the sequence $x, f(x), f(f(x)), \cdots$ will reach $0$ at some term. Let the index of first $0$ in that sequence be $f'(x)$, i.e., $$f'(x)=\min_{t\le x}\left({(f^t)(x)=0}\right).$$ In particular, $f'(0)=0$ since $f^0(x)=x$.

Here is the simple critical observation, $$h(t)=\underbrace{g(\cdots g(k)\cdots)}_{f'(t)\text{ copies of } g},$$ i.e., $h(t)$ is the result of applying $g$ repeatedly $f'(t)$ times, starting at $k$.

The problem we have now is to prove the following two general facts.

  • Assuming $f(x+1)<x+1$, if $f$ is in primitive recursive class $\mathcal C$, so is $f'$.
  • For any functions $f_1$ and $f_2$ in $\mathcal C$, the function that maps $t$ to the result of apply $f_1$ repeated $f_2(t)$ times, starting at a fixed $k$ is also a function in $\mathcal C$.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.