**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

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

Start Free Trial

No credit card required