A proof technique in recursive function theory that is used to
Prove the unsolvability of the halting problem: in the establishment of this it
is assumed (for the sake of argument) that there is an effective procedure for
testing whether programs terminate. Under this assumption the method of diagonalization
allows a contradiction to be derived. From this it is deduced that there is no
such effective procedure.
The technique was developed by Cantor to prove that the cardinality of the real
numbers is greater than the cardinality of the integers. In this application the
real numbers are enumerated in the form of a grid. A real number is then
constructed along the diagonal of the grid that is not pan of the original
enumeration.
