Where $x$ is a code number for a 1-place recursive function, define $h:\mathbb{N^2}\longmapsto\mathbb{N}$ as follows:
- $h(x,y)=1$ if $x$ is defined for $y$
- $h(x,y)=0$ if not.
This is problem 6.9 in Boolos, Burgess, and Jeffrey's Computability and Logic 5th Edition. In Burgess's student manual he invites the reader to consider the minimization of the 2-place function $g:\mathbb{N^2}\longmapsto\mathbb{N}$ defined as follows:
- $g(x,y)=|x-y|+y$
Burgess notes that $\mathrm{Mn}[g]$ is defined for $0$. Since $\mathrm{Mn}[g](0)=0$ but that, otherwise, for all $x>0$ it is undefined.
Given all of this, I tried to reason as follows:
- Suppose $n$ is the code number for $\mathrm{Mn}[g]$
- Then $h(n,0)=1$, as, per above, $\mathrm{Mn}[g]$ is defined for $0$
- But if we try to compute $h(n,1)$, we need to compute $\mathrm{Mn}[g](1)$ which we cannot since $\mathrm{Mn}[g]$ is not defined for $1$.
- As a result, $h(n,1)\neq0$, but rather $h(n,1)$ is undefined.
But this is where I am lost. I don't see how this would show that $h$ is not recursive. Also, I am not sure if my steps 1-4 above are on the right track at all.
I have found similar problems in the OLP's Computability chapter and in Leary and Kristiansen's Friendly Intro to Mathematical Logic. But their proofs that $h$ is not recursive follow a path involving Kleene's Normal Form Theorem and seem to basically attack the problem by showing that if $h$ were recursive then it would imply that a "diagonal" recursive function previously proved not to be computable would be computable. Hence, by reductio, $h$ cannot be recursive. But none of that material is at all present in Boolos, Burgess, Jeffrey text (at least for Chapters 1,2,6,or 7).
Thanks for any and all help.
This is basically the halting problem. Let $f = Mn[g]$ and define $T(x)=f(h(x,x))$. If $h$ is recursive, then $T$ is recursive, so it has a code number $m$. But then we have: $$T(m) \text{ is defined} \iff h(m,m) = 0 \iff T(m) \text{ is undefined}$$