Math 597B – Homework #1

February 2, 2007

Definitions: For A, B ⊆ ℕ we say A ≤_{m} B (A is many-one reducible to B) if there

exists a computable function f : ℕ → ℕ such that ∀x (x ∈ A ⇔ f(x) ∈ B). We say A ≡_{m} B (A is many-one equivalent to B) if A ≤_{m} B and B ≤_{m} A. Define A ⊕ B = {2x | x ∈ A} ∪ {2x + 1 | x ∈ B}.

1. (a) Show that ≤_{m} is reflexive and transitive.

(b) Show that ≡_{m} is an equivalence relation.

(c) Show that ⊕ acts as a least upper bound operator for ≤_{m}. That is, A ⊕ B ≤_{m} C if and only if A ≤_{m} C and B ≤_{m} C.

2. Define

(a) K = {x | φ_{x}^{(1)}(x) ↓}, diagonal halting problem.

(b) H = {x | φ_{x}^{(1)}(0) ↓}, the halting problem.

(c) G = {3^{x}5^{y}7^{z} | φ_{x}^{(1)}(y) ≃ z}.

(d) E = {x | φ_{x}^{(1)} is the empty function}.

(e) R = {3^{x}5^{y} | y ∈ range(φ_{x}^{(1)})}.

Show that H ≡_{m} K ≡_{m} G ≡_{m} \overline{E} ≡_{m} R.

Here we are writing \overline{A} = ℕ \ A = the complement of A.

3. (Rice’s Theorem) Let P be the class of 1-place partial computable functions. For any subclass C ⊆ P, define I_{C} = {x | φ_{x}^{(1)} ∈ C}. This is called an index set. Prove that I_{C} is always noncomputable, except in the trivial cases C = ∅ and C = P.

4. Write a register machine program which computes the exponential function, i.e., the 2-place number-theoretic function exp(x, y) = x^{y}. Note that x^{0} = 1 for all x.