Math 558 – Homework #2

Due October 5, 2009

1. Prove that the following sets are not recursive.

(a) T = {e | φ_{e}^{(1)} is total}.

(b) E = {e | φ_{e}^{(1)} is empty}.

(c) F = {e | dom(φ_{e}^{(1)}) is finite}.

(d) O = {e | 1 ∈ rng(φ_{e}^{(1)})}.

(e) I = {3^{i}5^{j} | φ_{i}^{(1)} = φ_{j}^{(1)}}.

2. Prove the following theorem, which generalizes both the Parametrization Theorem and the Recursion Theorem.

Theorem. Let θ(e, m_{1}, …, m_{k}, n_{1}, …, n_{l}) be a k + l + 1-place partial recursive function. Then, we can find a k-place primitive recursive function f(m_{1}, …, m_{k}) such that

φ_{f(m_{1},...,m_{k})}^{(l)}(n_{1}, …, n_{l}) ≃ θ(f(m_{1}, …, m_{k}), m_{1}, …, m_{k}, n_{1}, …, n_{l})

for all m_{1}, …, m_{k}, n_{1}, …, n_{l}.

3. We know that the Halting Problem is unsolvable. In other words, the set of Gödel numbers of register machine programs which eventually halt is nonrecursive. Prove the same result for register machine programs using only two registers, R_{1} and R_{2}.