Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm currently reading Roger Penrose's book Shadows of the Mind, in which (at pp.72-77) he gives a simple, somewhat preliminary I guess, proof for Gödel's incompleteness theorem by using turing machines. However, I'm having trouble understanding the argument.

The argument

Suppose that we list all the possible computations that can be carried out on a certain input number, $n$

\begin{equation} \label{firstList} C_0(n), C_1(n), C_2(n), C_3(n), C_4(n), C_5(n), \ldots, \end{equation}

In other words; we're listing all the turing machines that can operate on a certain input number, $n$.

Now, further assume that we have some computational procedure, $A$, which tries to predict whether a certain turing machine will stop when working with a certain input number. This procedure won't always be able to discern if a certain turing machine stops when it's fed with a certain input number, but it is sound, meaning that it never will say that it stops if it doesn't.

So, formally, $A$ takes two inputs: $q$ and $n$. $q$ represents a certain turing machine and $n$ represents the input to this turing machine. $A$ signals that a certain turing machine will not stop by stopping itself. This then has the consequence that

\begin{equation} \text{If } A(q, n) \text{ stops, then } C_q(n) \text{ does not stop.} \end{equation}

Now, Cantor's diagonal slash is introduced, in which one always choses a $q$ and $n$ that are the same. This means that we can write

\begin{equation} \text{If } A(n, n) \text{ stops, then } C_n(n) \text{ does not stop.} \end{equation}

Penrose here states (I'm citing him because I'm not entirely sure what the essential components of these steps are)

We now notice that $A(n, n)$ depends upon just one number $n$, not two, so it must be one of the computations $C_0, C_1, C_2, C_3, \ldots$ (as applied to $n$), since this was supposed to be a listing of all the computations that can be performed on a single natural number $n$. Let us suppose that it is in fact $C_k$, so we have:

\begin{equation} A(n, n) = C_k(n) \end{equation}

Now examine the particular value n=k. [...] We have [from the equation above]:

\begin{equation} A(k, k) = C_k(k) \end{equation}

Now, substituting $n$ with $k$ in the statement before the quotes we get

\begin{equation} \text{If } A(k, k) \text{ stops, then } C_k(k) \text{ does not stop.} \end{equation}

By then taking advantage of $A(k, k) = C_k(k)$ above, we get

\begin{equation} \text{If } C_k(k) \text{ stops, then } C_k(k) \text{ does not stop.} \end{equation}

Penrose then states that (not important for my question but just providing some context for readers not familiar with what this proof leeds to)

From this, we must deduce that the computation $C_k(k)$ does not in fact stop. (For if it did then it does not, according to [the equation above]. But $A(k, k)$ cannot stop either, since by [one of the equations above], it is the same as C_k(k). Thus, our procedure $A$ is incapable of ascertaining that this particular computation $C_k(k))$ does not stop even though it does not.

Moreover, if we know that $A$ is sound, then we know that $C_k(k)$ does not stop. Thus, we know something that $A$ is unable to ascertain. It follows that $A$ cannot encapsulate our understanding.

What I don't get

Now, what I don't get here is why the diagonal slash is necessary for the argument. Why can't I just choose two numbers; one for the turing machine, $x$; and one for the input number, $y$; and then proclaim that $A(x, y)$ has to correspond to a certain computation, $C_x(y)$? From that point on I should be able to say that if $C_x(y)$ stops, then $C_x(y)$ does not stop. An important part of the argument seems to be that "$A(n, n)$ depends upon just one number $n$, not two", but I don't understand why.

share|improve this question
add comment

2 Answers

What you claim is that there must exist numbers $x,y$ such that $A(x,y)$ corresponds to $C_x(y)$. Why is that true? How would you choose $x,y$?

More poignantly, let $A(x,y)$ read its entire input and then stop. This can't match the behavior of $C_x(y)$ since that machine has $y$ on its input tape, while $A(x,y)$ has $x\#y$ on its input tape (where $\#$ separates inputs).

The trick is to use what you call "Cantor's diagonal slash", namely to consider a machine $B$ defined by $B(n) = A(n,n)$. This machine has some Gödel number $k$, i.e. $B(n)$ is the same as $C_k(n)$. Putting $n = k$, we get $C_k(k) = B(k) = A(k,k)$.

A more complicated trick that can be used is Kleene's recursion theorem, which can construct self-referential sentences. However, in this particular case we can avoid invoking the recursion theorem using "Cantor's diagonal slash".

share|improve this answer
add comment

The argument as presented misses some quantifiers: the statements about $q$ and $n$ are assumed to hold for all possible values for them. Notably the equation $A(n,n)=C_k(n)$ is supposed to hold for all $n$, which is achieved by choosing $k$ such that $C_k$ describes the computation of $A$ for equal arguments (it would have been more precise to say that $C_k$ is the machine that proceeds by doubling its argument and then "calling" the machine $A$ for the doubled argument; this is certainly within the realm of computation if the operation of $A$ is so, and therefore such an index $k$ exists). That the equation holds for all $n$ is essential, since it allows specialising $n$ to $k$ later.

Now if you say "there must exist numbers $x,y$ such that $A(x,y)$ corresponds to $C_x(y)$" then you are no longer claiming this works for all $x,y$ (which indeed would not be true) nor even that there is some $x$ such that it works for all $y$ (which is still false). Now you don't need to have it for more than one $(x,y)$ in your argument, since it concludes a contradiction directly. But your problem is that there is no reason (other than the one given in Penrose' proof, namely taking $(x,y)=(k,k)$ for the $k$ he constructs) for which even one such pair $x,y$ should exist. If you fix some $x_0$, then certainly there is a computation that takes an argument $y$, prefixes a constant $x_0$, and then calls the computation of $A$; however there is no reason to assume that this computation should happen to be the one performed by $C_{x_0}$, and not even that there should be any $x_0$ for which this coincidence takes place. The "diagonal slash" is precisely needed to establish the existence of one appropriate pair $(x,y)$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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