O'Reilly logo

Theory of Computation by George Tourlakis

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

5.3 ADDITIONAL EXERCISES

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

(i) λx.x

(ii) λx.0

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

(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 ImagesΣ is closed under bounded left recursion on notation, that is, under the schema below, where the h, (gd)d ImagesΣ, and B are in ImagesΣ.

f (0, Imagesn) = h(Imagesn)f (dx,Imagesn)= gd(x,Imagesn, f(x, n)), for all d Σ| f (x,n)| ≤ |B(x,n)|

Hint. (iv) of the preceding exercise ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required