Computability, Unsolvability, Randomness Math 497A: Homework #1

Stephen G. Simpson

Due Tuesday, September 4, 2007

1. Exhibit a register machine program which computes the exponential function, exp(x, y) = x^{y}. Remember that the variables x and y range over ℕ, the set of natural numbers. Note that x^{0} = 1 for all x, even for x = 0.

2. Exhibit a register machine program which computes the function

Rem(y, x) = the remainder of y on division by x.

For example, Rem(17,5)=2.

3. Assume that P (x, y, z) is a 3-place predicate which is computable. Consider the 2-place partial function ψ(x, y) defined as follows:

ψ(x, y) ≃ the least z such that P (x, y, z) holds, if such a z exists. If such a z does not exist, then ψ(x, y) is undefined.

Use register machine programs to prove that the function ψ is computable. (More precisely, ψ is partial recursive.)

Hint: Since P is a computable predicate, we may assume that we have a program P which computes the characteristic function of P. Show how to embed P (or perhaps a variant of P) into a larger program, call it Q, such that Q computes ψ. The idea of Q is that, given x and y, Q(x, y) searches sequentially through the integers z = 0, z = 1, z = 2, …, to find the first z such that P (x, y, z) holds. In particular, Q will have the property that, for all x and y, Q(x, y) eventually halts if and only if P (x, y, z) holds for some z.

4. Use the results of Problems 2 and 3 to prove that the 2-place function LCM(x, y) = the least common multiple of x and y is computable. Deduce that the 2-place function GCD(x, y) = the greatest common divisor of x and y, is also computable.

5. (Approximating the square root of 2.) Consider successive rational approximations of \sqrt{2} given by Newton’s method:

x_{0} = 1, x_{n+1} = x_{n} − \frac{f(x_{n})}{f′(x_{n})}

where f(x) = x^{2} − 2. The first few values are x_{0} = 1, x_{1} = 3/2, x_{2} = 17/12, x_{3} = 577/408. Let a(n) and b(n) respectively be the numerator and denominator of x_{n}. Thus a(n) and b(n) are 1-place number-theoretic functions. The first few values are a(0) = b(0) = 1, a(1) = 3, b(1) = 2, a(3) = 17, b(3) = 12, a(3) = 577, b(3) = 408. Use primitive recursion to prove that the functions a(n) and b(n) are computable.

6. A positive real number r is said to be computable if there exist computable sequences of positive integers a_{n}, b_{n}, n = 0, 1, 2, …, such that

r = lim_{n→∞} \frac{a_{n}}{b_{n}}

and in addition

|r − \frac{a_{n}}{b_{n}} | < \frac{1}{2^{n}}

for all n ∈ ℕ. Give a convincing argument that all of the standard examples of positive real numbers including \sqrt{2} = 1.41421 ⋯, e = 2.71828 ⋯, π = 3.14159 ⋯, etc., are computable.

7. Prove that the sum, product, and quotient of two computable positive real numbers are computable.