1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Brian M. Scott May 22 at 3:57
  • $\begingroup$ 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. $\endgroup$ – user634426 May 23 at 4:23
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Is it used here that the map $M\mapsto N$ is computable? If so, how is it used, and why is it computable? $\endgroup$ – user634426 May 22 at 14:49
  • 1
    $\begingroup$ 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. $\endgroup$ – HallaSurvivor May 23 at 3:34
  • $\begingroup$ 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? $\endgroup$ – user634426 May 23 at 3:47
  • $\begingroup$ The pseudocode refers to $M$, so it has to receive $M$ as input somehow. I'll edit my answer to make this more precise $\endgroup$ – HallaSurvivor May 23 at 15:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.