- Assume, to the contrary, that we have an algorithm,
\(H\),
that terminates in a finite number of steps for all
\(A \in \mathcal{A}\) and \(D \in \mathcal{D}\) and
returns \(T\) if \(A \in \mathcal{A}\)
halts for all \(D \in \mathcal{D}\) and \(F\) otherwise.
- Now, observe that since an algorithm, \(A\), is just
a sequence of characters it can be thought of as data. That
is, \(\mathcal{A} \subsetset \mathcal{D}\).
- Given this, we know that \(H(A, A)\) will correctly
return either \(T\) or \(F\) in
a finite number of steps.
- Now, we construct the following algorithm, \(G\):
algorithm G(A)
{
if (H(A, A))
{
while (true); // Loop forever
}
else
{
return true;
}
}
- Now consider \(G(G)\); there are two possible
outcomes. In the one case, \(G(G)\), terminates in a
finite number of steps which means that \(H(G,G)\)
must have returned \(F\) (which is incorrect). In
the other case, \(G(G)\) loops forever which means
that \(H(G,G)\) must have
returned \(T\) (which is incorrect).
- Hence, we have a contradiction (i.e., \(H\) was assumed
to produce the correct result in a finite number of
steps but does not).
