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

Stephen G. Simpson

Due Monday, September 10, 2007

1. Let r be a positive real number. Prove that r is computable if and only if the number-theoretic function

f(n) = the nth decimal digit of r

is computable.

2. Consider the 2-place computable number-theoretic function f(x, y) = x + y. Exhibit three different indices of f.

(By an index of a partial recursive function, we mean the Gödel number of some program which computes the function.)

3. If f is a computable permutation of ℕ, prove that the inverse permutation f^{−1} is also computable.

(Here f^{−1}(y) = x if and only if f(x) = y. By a computable permutation of ℕ we mean a computable 1-place function f : ℕ → ℕ which maps ℕ one-to-one onto ℕ.)

4. Generalize the previous exercise as follows. Prove that if ψ is a 1-place partial recursive function which is one-to-one, then the inverse function ψ^{−1} is again partial recursive.

5. Consider the sets

K_{n} = {x ∈ ℕ | φ_{x}^{(1)}(x) ≃ n}

where n = 0, 1, 2, . . .. Show that the sets K_{0} and K_{1} are recursively inseparable. More generally, show that K_{m} and K_{n} are recursively inseparable for all m, n such that m ≠ n.

(Two sets A, B ⊆ ℕ are said to be recursively separable if there exists a recursive function f : ℕ → {0, 1} such that f(n) = 1 for all n ∈ A, and f(n) = 0 for all n ∈ B. Otherwise, A and B are said to be recursively inseparable.)

6. Let ψ(x) and θ(x) be 1-place partial recursive functions. We say that ψ is reducible to θ if there exists a 1-place total recursive function h(x) such that ψ(x) ≃ θ(h(x)) for all x ∈ ℕ. We refer to h(x) as a reduction function, and we say that h reduces ψ to θ. We say that θ is universal if all 1-place partial recursive functions are reducible to θ.

(a) Prove that the 1-place partial recursive function φ_{x}^{(1)}(x) is universal.

(b) Give some additional examples of 1-place partial recursive functions which are universal.

(c) Prove that if θ is universal then the domain of θ is not recursive. (The domain of θ is defined to be the set dom(θ) = {x | θ(x) ↓}.)

(d) Construct a 1-place partial recursive function θ which is universal via linear reduction functions. (This means that each 1-place partial recursive function is reducible to θ by means of a reduction function which is linear. We say that h(x) is linear if there exist constants a and b such that h(x) = ax + b for all x.)

7. (Extra Credit). Prove that any two universal partial recursive functions θ_{1} and θ_{2} are recursively isomorphic. This means that there exists a computable permutation of ℕ, call it f, such that

θ_{1}(x) ≃ y if and only if θ_{2}(f(x)) ≃ f(y)

for all x and y.