Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
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 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 Answers 3

up vote 7 down vote accepted

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.

share|improve this answer
    
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

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.

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.