The procedure A can be viewed as a particular computation that,
when presented with (q,n) tries to ascertain whether the
computation
will never ultimately halt i.e
It is now perfectly legitimate to write
Now as we have listed all of the computations
, A(n,n)
must be one of these computations. Thus
i.e A(n,n) is identified with the computation
as A
now only depends on one argument n.
Now examine the particular n = k. From (3) we have
and from (2) we may write, with n=k,
But from (4) we had that
and thus from (5) we have
Thus we must deduce that
does not in fact stop, for if
it did stop it does not according to (6). Thus from (4) A(k,k)
cannot stop either. Thus A is incapable of ascertaining
that the specific computation (or algorithm)
does not stop even though it does not stop !
We have required that A is sound i.e always gives the correct answer.
It must follow that we know that
does not stop. Thus
we know something that A is unable to ascertain, namely
that
does not stop.