Proof of Impossibility - Richard's Paradox

Richard's Paradox

This profound paradox presented by Jules Richard in 1905 informed the work of Kurt Gödel (cf Nagel and Newman p. 60ff) and Alan Turing. A succinct definition is found in Principia Mathematica:

"Richard's paradox... is as follows. Consider all decimals that can be defined by means of a finite number of words ; let E be the class of such decimals. Then E has terms; hence its members can be ordered as the 1st, 2nd, 3rd, ... Let N be a number defined as follows ; If the nth figure in the nth decimal is p, let the nth figure in N be p+1 (or 0, if p = 9). Then N is different from all the members of E, since, whatever finite value n may have, the nth figure in N is different from the nth figure in the nth of the decimals composing E, and therefore N is different from the nth decimal. Nevertheless we have defined N in a finite number of words and therefore N ought to be a member of E. Thus N both is and is not a member of E" (Principia Mathematica, 2nd edition 1927, p. 61).

Kurt Gödel considered his proof to be "an analogy" of Richard's paradox (he called it "Richard's antinomy") (Gödel in Undecidable, p. 9). See more below about Gödel's proof.

Alan Turing constructed this paradox with a machine and proved that this machine could not answer a simple question: will this machine be able to determine if any machine (including itself) will become trapped in an unproductive "infinite loop" (i.e. it fails to continue its computation of the diagonal number).