The halting problem at zero

Question

Consider the set $\{p:U(p,0)\text{ is defined}\}$ where $U$ is a universal function. I'm trying to understand the following sketch of proof of the fact that this set is not solvable.

The first claim is that from a program $q$ one cooks up a program $p$ so that $U(p,0)=U(q,q)$. I'm already lost at this point, what is $q$? Is it a variable? So is the author saying "define a function $G: N\to N, q\mapsto G(q)=p$ so that $U(p,0)=U(q,q)$? Or is something else going on?

The proof proceeds by clarifying how to do this. The program $p$ is defined as follows:

• const. $q= ....;$

• return $U(q,q)$

So this program, regarless of the input, just runs the program that computes $U$ on the pair $(q,q)$, resulting in $U(q,q)$ (if it's defined; if not, I guess it will work forever). But I don't understand how it follows that $U(p,0)=U(q,q)$. We only know that $U(q,q)$ is the result of the application of the program $p$ on any argument.

Further, it is said that passing from $q$ to $p$ is a computable operation. Assuming that we know what $q$ is (that was my first question above), why is it computable and why do we care about it?

Finally, it is said that we know that it's not decidable if $U(q,q)$ is defined, and therefore it is not decidable if $U(p,0)$ is defined. This looks too vague to me, maybe because I don't understand why we care about this correspondence $q\mapsto p$. Why not $p\mapsto q$?

Answer 1

Here is an elaborated version of the argument:

We want to show that no program can tell us if $\{p ~|~ U(p,0) \}$. Phrased somewhat more mundanely, we want to show that no program meets the following specification:

• Take as input a description of a program $p$
• Return YES if and only if $p(0)$ halts

Now, how do we show that no such program exists?

Towards a contradiction, assume we had such a program $M$. That is, $M$ is a program meeting the above specification. Then consider the following program $N$ (which I'll write in some kind of python):

def N(p):

  # we define a new program q
  def q(n):
    return p(p)

  # and then call M on this new program q
  return M(q)

Now, what does $N$ do?

Well $N(p)$ is yes iff $M(q)$ is yes iff $q(0)$ halts iff $p(p)$ halts.

And now we see the issue! We know that $N$ cannot exist! To go back to the language of your question, $N$ decides the set $\{q ~|~ U(q,q) \}$, which we know is undecidable. So we can contradict the existence of $M$.

---

Edit:

One way to see that $M \mapsto N$ is computable is to rewrite the code for $N$ as below. Most people don't do this, because the code for $N$ refers to $M$, and so this kind of conversion is "obvious" once you've done a few examples.

def MToN(M):
  # We define a new program N
  def N(p):
    # We define a new program q
    def q(n):
      return p(p)
    # and then call M on this new program q
    return M(q)

  # so this is a program that turns M into N
  return N

---

I hope this helps ^_^