Turing's Proof - Richard's Paradox

Richard's Paradox

In 1905 Jules Richard presented this profound paradox. Alan Turing's first proof constructs this paradox with his so-called computing machine and proves that this machine cannot answer a simple question: will this machine be able to determine if any computing machine (including itself) will become trapped in an unproductive "infinite loop" (i.e. it fails to continue its computation of the diagonal number).

A succinct definition of Richard's paradox is found in Whitehead and Russell's 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).

Read more about this topic:  Turing's Proof

Famous quotes containing the words richard and/or paradox:

    If thee thy brittle beauty so deceives,
    Know then the thing that swells thee is thy bane;
    For the same beauty doth, in bloody leaves.
    The sentence of thy early death contain.
    —Sir Richard Fanshawe (1608–1666)

    The conclusion suggested by these arguments might be called the paradox of theorizing. It asserts that if the terms and the general principles of a scientific theory serve their purpose, i. e., if they establish the definite connections among observable phenomena, then they can be dispensed with since any chain of laws and interpretive statements establishing such a connection should then be replaceable by a law which directly links observational antecedents to observational consequents.
    —C.G. (Carl Gustav)