Page 163 - Textos de Matemática Vol. 40

A note on the history of functional self-application 151
Such a binary operator is used explicitely in the applicative theories. There- fore, in applicative theories self-application of the form t t is, in fact, a diago- nalization over ·, the binary function symbol for application: ·(t, t) (or in infix notation: t · t).
Intherecursion-theoreticinterpretationofapplicativetheories,(ts)N reads as {tN }(sN ). From this perspective, self-application looses all mystery and it even fits with von Neumann’s computer model: A computer program, repre- sented in the computer by a string of 0s and 1s, i.e., by a binary number, is applied to an argument, which again is just a string of 0s and 1s, i.e., also just a binary number. Nothing prevents us from applying a function represented by a number n to the argument n itself, in the same way that in recursion theory the nth function in an enumeration of the partial recursive functions can be applied to the argument n, i.e., in Kleene notation: {n}(n). However, we cannot expect that these computer programs and function applications always return a natural number.
Self-application is crucial in the definition of the recursion operator (see the proof of Proposition 1.2.2). This operator was originally called paradoxical combinator by Curry and designated by Y. In the total setting one may give a definition slightly more simple as in the proof of Proposition 1.2.2, namely λf.(λx.f (x x)) (λx.f (x x)). However, both definitions contain two nested self- applications. It is worth mentioning that these nested self-applications resemble the proof of Kleene’s Second Recursion Theorem.58 (This relation is also dis- cussed in [Odi89, p. 155].) However, Curry constructed a (combinator version of the) Y combinator directly from a formalization of Russell’s paradox, see [CF58, Section 5G] (also in [Odi89, p. 81f]) and the letter of Curry to Scott from May 1st, 1979, [Sco80, p. 261].
A.8 Conclusion
We presented a previously unpublished paragraph of lecture notes from 1905 in which David Hilbert proposed a certain function, which we call Hilbert’s para- doxical function, as the common reason for different set-theoretical paradoxes. From a modern perspective Hilbert’s paradoxical function does not serve as a base for other paradoxes, but it just shares with them the use of self-reference— here in the special form of self-application—or diagonalization.59 Even Hilbert crossed out this paragraph during a later reuse of the lecture notes, and, as a matter of fact, the paragraph in question did not play any further role in the discussion of the paradoxes.
58For the historical relation of the λ-calculus and recursion theory, see [Kle81]. Although both were developed more or less in parallel, Stephen Kleene (1909–1994) does not give any indication that his proof of the Second Recursion Theorem was related to the discovery of the Y combinator.
59For a comprehensive—historical as well as mathematical—study of the relation of self- reference and paradoxes, cf. [Can0x].