2

This is exercise 1.7.9 from Soare.

Define $$\psi_{\langle p + 1, q \rangle}(0) = p $$

$$\psi_{\langle p, q \rangle}(x) \simeq \phi_q(x) \textrm{ if }x > 0 $$

and let $\psi_{\langle 0, q\rangle}(0)$ be undefined.

I am to prove this is a surjection on PC, but not acceptable. The hint is to prove that this being acceptable implies the halting problem is decidable.

$\psi$ is surjective, because $\phi_n$ is equal to $\psi_{\langle\phi_n(0) + 1, n\rangle}$ or $\psi_{\langle 0, n \rangle}$ if $\phi_n(0)$ is undefined.

I am stuck on the second part. These are the thoughts I have on it:

If it is acceptable, it follows from the acceptable numbering theorem that there is a computable permutation $h$ such that $\psi_{h(e)} = \phi_e$. We know that $\phi_y$ is equal to some $\psi_e$ and that $\phi_y(x)$ converges precisely when $\psi_e(x)$ converges, so precisely when $\phi_{h^{-1}(e)}(x)$ does.

We can say that $h^{-1} = \phi_n$ for some $n$ as it is computable, but I fail to see how this is helpful.

user388557
  • 2,544

1 Answers1

3

Suppose I told you that $$\phi_e\simeq\psi_c.$$ "Unpairing" $c$ we get $\psi_c=\psi_{\langle i,j\rangle}$.

  • Note that I do mean literal equality - we're just saying $c=\langle i,j\rangle$. Moreover, we need not have $j=e$.

I claim that the value of $i$ tells us whether $\phi_e(0)$ is undefined; do you see why? HINT: for example, if $i=17$ then $\phi_e(0)\downarrow$ ...

Phrasing the above precisely, what we get is if there were a total computable map $p:\mathbb{N}\rightarrow\mathbb{N}$ satisfying $\phi_e\simeq\psi_{p(e)}$ for all $e\in\mathbb{N}$, the set $$\{e: \phi_e(0)\downarrow\}$$ would be computable. And this is a set whose Turing equivalence with the halting problem is easy to prove (if you haven't proved it already).

Noah Schweber
  • 245,398