Questions tagged [combinatory-logic]
Combinatory logic, combinatorial calculi, and other questions about combinators and variable-free variants of the $\lambda$-calculus.
54 questions
2 votes
1 answer
76 views
Lambda calculus, $M$ does (doesn't) have a normal form. Find $MI$ that doesn't (does) have a normal form. [closed]
I'm trying to construct terms $M_1$, $M_2$ such that $M_1$ has a normal form, but $M_1I$ doesn't. $M_2$ doesn't have a normal form, but $M_2I$ does. This is somewhat related to these two questions, $...
- 125
7 votes
4 answers
710 views
Defining the Y combinator in terms of S, K and I
We know that the Y-combinator is defined as: $$\text{Y}:=\lambda f.(\lambda x.f(xx))(\lambda x.f(xx))$$ Wikipedia says :$$\text{Y}:=\text{S(K(SII))(S(S(KS)K)(K(SII)))}$$ Now the question is: What ...
- 2,363
4 votes
1 answer
176 views
Checking equivalence of combinatorial terms.
Due to some context, I have reason to believe that S(K(SII)) and SSI are actually equivalent CL terms. This is my attempt at a proof (assuming a and b to be arbitrary CL terms): $$\text{S(K(SII))ab = ...
- 2,363
1 vote
1 answer
95 views
Combinatory Logic Problem With Partial Reductions
I'm working through Bacon's Philosophical Introduction to Higher Order Logic. I am looking for help on the following problem: Exercise 3.17 Calculate the following, assuming that $\wedge : t \to t \...
- 43
2 votes
1 answer
152 views
SKI combinatory calculus, $M$ doesn't have a normal form. Find $(M S)$ that has a normal form
The problem is related to a similar question about lambda calculus. This question is about SKI combinatory calculus. I want to find a term $M$ without a normal form that will yield a term with a ...
- 131
-2 votes
1 answer
102 views
How to show beta equivalence of property of Y combinator
How to show that $\underline{Y}f =_{\beta} f(\underline{Y}f)$ where $\underline{Y}$ is the usual Y combinator? Thanks.
- 297
3 votes
2 answers
527 views
SKI combinator calculus of `2 = λf.λx.f(f x)`
EDIT: refactored this question into a slightly different, but related one: Rules for converting lambda calculus expressions to SKI combinator calculus expression? Which rule(s) is/are incorrect? ...
- 1,637
2 votes
1 answer
140 views
Doesn't lambda K-calculus include lambda I-calculus?
To mock a mockingbird, chapter 18: From just S and K you can derive any combinatorial bird whatsoever! Same book, chapter 19 […] with just the two birds J and I, we would ultimately get the same ...
- 321