17
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ I guess I should point out that Wikipedia attributes the Y combinator to Haskel Curry, but doesn't give a reference. $\endgroup$
    – Dan Ramras
    Commented Jul 14, 2010 at 19:15
  • $\begingroup$ Dan, according to the paper by Cardone and Hindley I posted in my answer, that doesn’t seem to be the case. $\endgroup$
    – Antonio E. Porreca
    Commented Jul 14, 2010 at 19:56
  • $\begingroup$ Well, not surprisingly, the history seems muddled at best. I can't see anything that supports the attribution (on 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. $\endgroup$
    – Dan Ramras
    Commented Jul 28, 2010 at 21:40

3 Answers 3

Reset to default
10
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ 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). $\endgroup$
    – Dan Ramras
    Commented Jul 14, 2010 at 21:20
  • $\begingroup$ In Safari, those lambdas show up as subscripts... Weird. $\endgroup$
    – Dan Ramras
    Commented Jul 14, 2010 at 22:12
12
$\begingroup$

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.

Improve this answer
$\endgroup$
6
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .