# The halting problem at zero

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$$?

• This is not a topic with which I am very comfortable, but it appears to me that the argument is as follows. If $A=\{p:U(p,0)\text{ is defined}\}$ is solvable, there is a program that takes arbitrary input $q$, produces from it $p$ as described in the question if $q$ is in fact (the number of) a program, and determines whether $U(p,0)$ is defined. Since $U(p,0)=U(q,q)$, it is defined iff $U(q,q)$ is defined, and $\{q:U(q,q)\text{ is defined}\}$ is therefore solvable. But it isn’t, so neither is $A$. – Brian M. Scott May 22 at 3:57
• It seems the authors are using $m$-reducibility without mentioning this word. So the function $q\mapsto p$ is supposed to be the function from the definition of $m$-reducibility, I think. – user634426 May 23 at 4:23

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 ^_^

• Is it used here that the map $M\mapsto N$ is computable? If so, how is it used, and why is it computable? – user634426 May 22 at 14:49
• Yes! It's very important that $M \mapsto N$ is computable, as this ensures the assumed computability of $M$ implies the computability of $N$. As for why it is computable, pseudocode was provided, and that is enough by the Church-Turing thesis. – HallaSurvivor May 23 at 3:34
• But I thought computability of $M\mapsto N=N(M)$ means that there is a program that accepts $M$ and returns $N$. The pseudocode provided is not a code of such program, is it? It is a code that is defining $N$. Isn't that a different thing? – user634426 May 23 at 3:47
• The pseudocode refers to $M$, so it has to receive $M$ as input somehow. I'll edit my answer to make this more precise – HallaSurvivor May 23 at 15:39