17

Inspired by the comments to this question, I wonder if someone can explain the history of the fixed point combinator (often called the Y combinator) in lambda calculus.

Where did it first appear? Was it directly inspired by the Arithmetic Fixed Point Theorem? The two are very similar in spirit.

Based on the dates of Church's introduction of lambda calculus and Goedel's incompleteness theorem, it seems to me the Arithmetic Fixed Point Theorem must have come first.

Community
  • 1
Dan Ramras
  • 8,498
  • 1
    I guess I should point out that Wikipedia attributes the Y combinator to Haskel Curry, but doesn't give a reference. – Dan Ramras Jul 14 '10 at 19:15
  • Dan, according to the paper by Cardone and Hindley I posted in my answer, that doesn’t seem to be the case. – Antonio E. Porreca Jul 14 '10 at 19:56
  • Well, not surprisingly, the history seems muddled at best. I can't see anything that supports the attribution (on http://en.wikipedia.org/wiki/Fixed_point_combinator) of the combinator Y = λf·(λx·f (x x)) (λx·f (x x)) to Curry. The book of Curry, Feys and Craig refers to a 1929 letter from Curry to Hilbert (in Section 5S), but it doesn't really sound like fixed point combinators were explicit in that letter. – Dan Ramras Jul 28 '10 at 21:40

3 Answers3

13

Although I don't have historical information, let me comment on the suggestion that the $Y$ combinator may have been inspired by the arithmetical fixed-point theorem. I think a more likely inspiration would be Russell's paradox. If you think of application (of functions to arguments) as analogous to membership in sets (i.e., think if $x(y)$ as analogous to $y\in x$), then the $Y$ combinator builds a fixed point $Yf$ for a function $f$ in the same way that Russell built a fixed-point for negation.

Andreas Blass
  • 72,290
10

The paper History of Lambda-calculus and combinatory logic by F. Cardone and J.R. Hindley is a good starting point for answering such a question, and many others (it has 38 pages of bibliography). There’s a brief account on fixed-point combinators on page 8, although it doesn’t seem to settle the question completely.

Mark Dominus
  • 103
Antonio E. Porreca
  • 1,155
  • 1
    Thanks for this link! Looks very interesting. It seems the history is a bit muddled, which I guess is not surprising. The discussion on p. 8 gives Turing credit for the earliest published fixed point combinator, and attributes the Y combinator, usually written $\lambda f.(\lambda x. f(xx))(\lambda x.f(xx))$, to Rosenbloom in 1950! But the earliest reference it suggests is a 1929 letter from Curry to Hilbert. I'll stop by the library later to see what Curry's book says about this letter (sadly, the book isn't in Google Books). – Dan Ramras Jul 14 '10 at 21:20
  • In Safari, those lambdas show up as subscripts... Weird. – Dan Ramras Jul 14 '10 at 22:12
6

Turing's 1937 paper (of just one page!) which defines $\Theta$, his own fixed point combinator, refers to a 1936 paper by Kleene in which a "function L with a property similar to the essential property of $\Theta$" is defined.

References: A M Turing, The P function in $\lambda$-K conversion, Journal of Symbolic Logic Vol 4 No 2 December 1937 p. 164

S C Kleene, $\lambda$ definability and recursiveness, Duke Mathematical Journal, Vol 2 1936 p. 346

Chris Stephenson
  • 61