Theory of Computation

5.3 ADDITIONAL EXERCISES

1. Fix an alphabet Σ with m > 1 elements. Show that the following functions are in Cobham’s class _Σ (cf. 5.1.1.7):

(i) λx.x

(ii) λx.0

(iii) The left successors: λx.d ∗ x, for all d Σ

(iv) λx.x^R, where x^R 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 ...