# Any PRC class is closed under a construction involving a function f such that f(x+1) < x+1

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!

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