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

Question

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!

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