Math 558 – Homework #2

Due October 5, 2009

Solutions

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)}}.

Solution. By the Parametrization Theorem, let f(m) be a primitive recursive function such that φ_{f(m)}^{(1)}(n) ≃ 1 + 0 · φ_{m}^{(1)}(0) for all m, n.

Recall that H is the Halting Problem, H = {m | φ_{m}^{(1)}(0) ↓}. For all m ∈ H we have f(m) ∈ T, f(m) ∉ E, f(m) ∉ F, and f(m) ∈ O. Also, for all m ∉ H we have f(m) ∉ T, f(m) ∈ E, f(m) ∈ F, and f(m) ∉ O. Thus f reduces H to T, E^{c}, F^{c}, and O. Since H is nonrecursive, it follows that T, E, F, O are nonrecursive.

Fix i such that i ∈ E, i.e., φ_{i}^{(1)}(n) ↑ for all n. Then E is reducible to I via the primitive recursive function j ↦ 3^{i}5^{j}. Since E is nonrecursive, it follows that I is nonrecursive.

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}.

Solution. First we generalize the Parametrization Theorem, as follows.

Lemma. Given a k + l-place partial recursive function ψ, we can find a k-place primitive recursive function f such that

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

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

Proof. Let ψ be a k + l-place partial recursive function. By the Parametrization Theorem, let f^{∗} be a 1-place primitive recursive function such that

φ_{f^{∗}(m)}^{(l)}(n_{1}, …, n_{l}) ≃ ψ((m)_{1}, …, (m)_{k}, n_{1}, …, n_{l})

for all m, n_{1}, …, n_{l}. The idea here is that m encodes the finite sequence (m)_{1}, …, (m)_{k} via prime power coding. Letting

f(m_{1}, …, m_{k}) = f^{∗}(p_{1}^{m_{1}} · · · · · p_{k}^{m_{k}})

we see that f is a k-place primitive recursive function and

φ_{f(m_{1},...,m_{k})}^{(l)}(n_{1}, …, n_{l}) ≃ φ_{f^{∗}(p_{1}^{m_{1}}·····p_{k}^{m_{k}})}^{(l)}(n_{1}, …, n_{l})
≃ ψ^{∗}(p_{1}^{m_{1}} · · · · · p_{k}^{m_{k}}, n_{1}, …, n_{l})
≃ ψ(m_{1}, …, m_{k}, n_{1}, …, n_{l})

for all m_{1}, …, m_{k}, n_{1}, …, n_{l}. This proves the lemma.

Now, to prove our theorem, we imitate the proof of the Recursion Theorem. Let θ be a k + l + 1-place partial recursive function. By our lemma, let g be a k + 1-place primitive recursive function such that

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

for all e, m_{1}, …, m_{k}, n_{1}, …, n_{l}. By the Parametrization Theorem, let d be a 1-place primitive recursive function such that

φ_{d(u)}^{(l)}(n_{1}, …, n_{l}) ≃ φ_{φ_{u}^{(1)}(u)}^{(l)}(n_{1}, …, n_{l})

for all u, n_{1}, …, n_{l}. By our lemma, let h be a k-place primitive recursive function such that

φ_{h(m_{1},...,m_{k})}^{(1)}(u) ≃ g(d(u), m_{1}, …, m_{k})

for all m_{1}, …, m_{k}, u. Finally, letting

f(m_{1}, …, m_{k}) = d(h(m_{1}, …, m_{k}))

we see that f is a k-place primitive recursive function and

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

for all m_{1}, …, m_{k}, n_{1}, …, n_{l}. This proves the theorem.

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}.

Solution. Let H_{2} be the Halting Problem for register machine programs which use only R_{1} and R_{2}. In other words, H_{2} = {#(P) | P uses only R_{1} and R_{2} and P(0) eventually halts}. We shall show that H, the Halting Problem for arbitrary register machine programs, is reducible to H_{2}. Since H is nonrecursive, it will follow that H_{2} is nonrecursive.

As a special case of Exercise 1.5.10 in the lecture notes, let R be a register machine program using only R_{1} and R_{2} which computes the 1-place partial recursive function 3^{n} ↦ 5^{φ_{n}^{(1)}(0)}. In particular R(3^{n}) eventually halts if and only if φ_{n}^{(1)}(0) ↓, i.e., n ∈ H. If I_{1}, …, I_{l} are the instructions of R, let R^{∗} be R with the instructions renumbered as I_{2}, …, I_{l+1}. For each n let R_{n}^{∗} be the program

[figure: I_{1}; I_{l+2}; …; I_{l+3^{n}}; I_{2} ⋯ I_{l+1}; start; R_{1}^{+}; R_{1}^{+}; …; R_{1}^{+}; R^{∗}; stop]

which is like R but with 3^{n} hard-coded as the input. Thus R_{n}^{∗}(0) eventually halts if and only if R(3^{n}) eventually halts, i.e., n ∈ H. As in the proof of the Parametrization Theorem (see the lecture notes, Theorem 1.7.10), we can show that f(n) = #(R_{n}^{∗}) is primitive recursive as a function of n. Thus f reduces H to H_{2}, Q.E.D.