1. Fix an alphabet Σ with m > 1 elements. Show that the following functions are in Cobham’s class Σ (cf. 22.214.171.124):
(iii) The left successors: λx.d ∗ x, for all d Σ
(iv) λx.xR, where xR is the number whose m-adic notation is the reverse of that of x.
2. Fix an alphabet Σ with m > 1 elements. Show that Cobham’s class Σ is closed under bounded left recursion on notation, that is, under the schema below, where the h, (gd)d Σ, and B are in Σ.
f (0, n) = h(n)f (d ∗ x,n)= gd(x,n, f(x, n)), for all d Σ| f (x,n)| ≤ |B(x,n)|
Hint. (iv) of the preceding exercise ...