Basics of Computability Theory
Exercise 1 Give one concrete example for each of the Basic Functions (The zero, successor, identity or projection functions).
Exercise 2 Define Composition (f o g)(x) for functions f (x) = x × 2 and g(x) = x3 - 2.
Exercise 3 Give concrete examples of all primitive recursions schema for arithmetical functions on inputs m, n of your choice.
Exercise 4 Consider the Exponentiation function xy. Explain Minimization applied to Exponentiation: is it regular? i.e. is there for every input x to exponentiation a value of y such that xy = 0? Is it undefined?
Exercise 5 Give an example of a partial arithmetical function.