In order for A to apply to computations generally, we shall need a way of coding all the different computations C{n} so that A can use this coding for its action. All the possible different computations C can in fact be listed, say as
C0, C1, C2, C3, C4, C5,...,
and we can refer to Cq as the qth computation. When such a computation is applied to a particular number n, we shall write
C0{n}, C1{n}, C2{n}, C3{n}, C4{n}, C5{n},....
We can take this ordering as being given, say, as some kind of numerical ordering of computer programs. {To be explicit, we could, if desired, take this ordering as being provided by the Turing-machine numbering given in ENM, so that then the computation Cq{n} is the action of the qth Turing machine Tq acting on n.} One technical thing that is important here is that this listing is computable, i.e. there is a single computation Cx that gives us Cq when it is presented with q, or, more precisely, the computation Cx acts on the pair of numbers q, n {i.e. q followed by n} to give Cq{n}.
The procedure A can now be thought of as a particular computation that, when presented with the pair of numbers q,n, tries to ascertain that the computation Cq{n} will never ultimately halt. Thus, when the computation A terminates, we shall have a demonstration that Cq{n} does not halt. Although, as stated earlier, we are shortly going to try to imagine that A might be a formalization of all the procedures that are available to human mathematicians for validly deciding that computations never will halt, it is not at all necessary for us to think of A in this way just now. A is just any sound set of computational rules for ascertaining that some computations Cq{n} do not ever halt. Being dependent upon the two numbers q and n, the computation that A performs can be written A{q,n}, and we have:
{H} If A{q,n} stops, then Cq{n} does not stop.
Now let us consider the particular statements {H} for which q is put equal to n. This may seem an odd thing to do, but it is perfectly legitimate. {This is the first step in the powerful 'diagonal slash', a procedure discovered by the highly original and influential nineteenth-century Danish/Russian/German mathematician Georg Cantor, central to the arguments of both Godel and Turing.}
With q equal to n, we now have:
{I} If A{n,n} stops, then Cn{n} does not stop.
We now notice that A{n,n} depends upon just one number n, not two, so it must be one of the computations C0,C1,C2,C3,...{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 Ck, so we have:
{J} A{n,n} = Ck{n}
Now examine the particular value n=k. {This is the second part of Cantor's diagonal slash!} We have, from {J},
{K} A{k,k} = Ck{k}
and, from {I}, with n=k:
{L} If A{k,k} stops, then Ck{k} does not stop.
Substituting {K} in {L}, we find:
{M} If Ck{k} stops, then Ck{k} does not stop.
From this, we must deduce that the computation Ck{k} does not in fact stop. {For if it did then it does not, according to {M}! But A{k,k} cannot stop either, since by {K}, it is the same as Ck{k}. Thus, our procedure A is incapable of ascertaining that this particular computation Ck{k} does not stop even though it does not.
Moreover, if we know that A is sound, then we know that Ck{k} does not stop. Thus, we know something that A is unable to ascertain. It follows that A cannot encapsulate our understanding.
C0, C1, C2, C3, C4, C5,...,
and we can refer to Cq as the qth computation. When such a computation is applied to a particular number n, we shall write
C0{n}, C1{n}, C2{n}, C3{n}, C4{n}, C5{n},....
We can take this ordering as being given, say, as some kind of numerical ordering of computer programs. {To be explicit, we could, if desired, take this ordering as being provided by the Turing-machine numbering given in ENM, so that then the computation Cq{n} is the action of the qth Turing machine Tq acting on n.} One technical thing that is important here is that this listing is computable, i.e. there is a single computation Cx that gives us Cq when it is presented with q, or, more precisely, the computation Cx acts on the pair of numbers q, n {i.e. q followed by n} to give Cq{n}.
The procedure A can now be thought of as a particular computation that, when presented with the pair of numbers q,n, tries to ascertain that the computation Cq{n} will never ultimately halt. Thus, when the computation A terminates, we shall have a demonstration that Cq{n} does not halt. Although, as stated earlier, we are shortly going to try to imagine that A might be a formalization of all the procedures that are available to human mathematicians for validly deciding that computations never will halt, it is not at all necessary for us to think of A in this way just now. A is just any sound set of computational rules for ascertaining that some computations Cq{n} do not ever halt. Being dependent upon the two numbers q and n, the computation that A performs can be written A{q,n}, and we have:
{H} If A{q,n} stops, then Cq{n} does not stop.
Now let us consider the particular statements {H} for which q is put equal to n. This may seem an odd thing to do, but it is perfectly legitimate. {This is the first step in the powerful 'diagonal slash', a procedure discovered by the highly original and influential nineteenth-century Danish/Russian/German mathematician Georg Cantor, central to the arguments of both Godel and Turing.}
With q equal to n, we now have:
{I} If A{n,n} stops, then Cn{n} does not stop.
We now notice that A{n,n} depends upon just one number n, not two, so it must be one of the computations C0,C1,C2,C3,...{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 Ck, so we have:
{J} A{n,n} = Ck{n}
Now examine the particular value n=k. {This is the second part of Cantor's diagonal slash!} We have, from {J},
{K} A{k,k} = Ck{k}
and, from {I}, with n=k:
{L} If A{k,k} stops, then Ck{k} does not stop.
Substituting {K} in {L}, we find:
{M} If Ck{k} stops, then Ck{k} does not stop.
From this, we must deduce that the computation Ck{k} does not in fact stop. {For if it did then it does not, according to {M}! But A{k,k} cannot stop either, since by {K}, it is the same as Ck{k}. Thus, our procedure A is incapable of ascertaining that this particular computation Ck{k} does not stop even though it does not.
Moreover, if we know that A is sound, then we know that Ck{k} does not stop. Thus, we know something that A is unable to ascertain. It follows that A cannot encapsulate our understanding.
( Roger Penrose )
[ Shadows of the Mind: A Search ]
www.QuoteSweet.com