Paper: On Translating Lambda Terms into Combinators; The Basis Problem (at LICS 1986)

Authors: Richard Statman

Abstract

In the late 1920's Curry noticed that certain finite sets of combinators, such as S and K, enjoy a completeness property similar to the completeness of union, intersection, and complement for Boolean Algebra. This property is called "combinatory completeness". For computation, combinatory completeness is similar to Kleene's second recursion theorem.

BibTeX

  @InProceedings{Statman-OnTranslatingLambda,
    author = 	 {Richard Statman},
    title = 	 {On Translating Lambda Terms into Combinators; The Basis Problem},
    booktitle =  {Proceedings of the First Annual IEEE Symposium on Logic in Computer Science (LICS 1986)},
    year =	 {1986},
    month =	 {June}, 
    pages =      {378--382 },
    location =   {Cambridge, MA, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }