diagonalization
diagonalization A proof technique in recursive function theory that is used to prove the unsolvability of, for example, the halting problem. The proof assumes (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 G. 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, using the diagonal of the grid, that is not part of the original enumeration.
The technique was also used by J. Richard to generate a paradox about the namability of real numbers. This paradox (together with the “liar paradox” of antiquity) is reputed to have prompted K. Gödel to apply a similar technique of diagonalization in constructing a number-theory formula not provable in formal arithmetic. See Gödel's incompleteness theorems.
The technique was developed by G. 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, using the diagonal of the grid, that is not part of the original enumeration.
The technique was also used by J. Richard to generate a paradox about the namability of real numbers. This paradox (together with the “liar paradox” of antiquity) is reputed to have prompted K. Gödel to apply a similar technique of diagonalization in constructing a number-theory formula not provable in formal arithmetic. See Gödel's incompleteness theorems.
More From encyclopedia.com
Real Numbers , A real number is any number which can be represented by a point on the number line. The numbers 3.5, 0.003, 2/3, π, and are all real numbers.
The rea… Imaginary Number , Imaginary number
An imaginary number is the square root of a negative real number. (The square root of a number is a second number that, when multipl… Kurt Godel , Gödel, Kurt Friedrich
GöDEL, KURT FRIEDRICH
(b. Brünn, Moravia lsqbnow Brno, Czechoslovakiarsqb, 28 April 1906; d, Princeton,
mathe matical logic, se… Continuity , In the decades bracketing the turn of the twentieth century, the real number system was dubbed the arithmetic continuum because it was held that this… Random Numbers , History
Random numbers are numbers generated by a mechanism that produces irregularity, in a sense that will be made precise. There are four major us… Real , re·al1 / ˈrē(ə)l/ • adj. 1. actually existing as a thing or occurring in fact; not imagined or supposed: Julius Caesar was a real person a story draw…
You Might Also Like
NEARBY TERMS
diagonalization