Math 558 – Homework #1

Due September 15, 2009

1. A real number α is said to be primitive recursive if the function f(n) = the nth digit of α is primitive recursive. A real number α is said to be algebraic if it is a root of a nonzero polynomial with integer coefficients. For example, \sqrt{2} is a real algebraic number, because it is a root of the polynomial x^{2} − 2.

Prove that all real algebraic numbers are primitive recursive.

2. We know that the Ackermann function is an example of a 1-place function which is recursive but not primitive recursive. Find an example of a 1-place predicate which is recursive but not primitive recursive.

3. Exhibit a register machine program showing that the function f(m, n) = m^{n} is computable. (Note that m^{0} = 1 for all m ∈ ℕ including m = 0. This convention makes the recursion easier.)