Combinatory logic, combinatorial calculi, and other questions about combinators and variable-free variants of the $\lambda$-calculus.
Questions tagged [combinatory-logic]
53 questions
7
votes
1 answer
Is there a proof of (non)existence of a proper universal combinator?
It is a well-known fact that all combinators can be derived from the two fundamental combinators K and S. It seems only natural to also ask whether there is a single universal combinator, but I can’t find much information on the topic. The only…
user287393
- 271
- 1
- 5
2
votes
1 answer
How to define halting status in combinatory logic
We all know that combinatory logic can be used to express programs, for example:
$S(K(SI))K\alpha\beta \rightarrow K(SI)\alpha(K\alpha)\beta
\rightarrow SI(K\alpha)\beta
\rightarrow I\beta(K\alpha\beta)
…
Mountain
- 540
1
vote
1 answer
What is the precise statement of Craig's theorem?
I'm interested writing a proof of Craig's theorem. After several attempts I realized that there are several possible ways to state the theorem, each with subtle but important differences.
Here's one statement I came up with:
"If a system of…
user287393
- 271
- 1
- 5
0
votes
1 answer
Nondeterminism In Modeling Computation with SKI-combinators
Consider two terms of the SKI-combinator calculus $\alpha$ and $\beta$ such that the following derivations are valid.
$\alpha \rightarrow \alpha_1$
$\beta \rightarrow \beta_1$
Then we have two valid derivations for the term $(\alpha \beta)$. We…
Mark
- 5,696
0
votes
0 answers
Could we define an arity of a term in combinatory logic and consider some inference rule?
In computer science, we know a function has an arity. And we noticed the similarity between function and a term in combinatory logic, so could we define the arity of a term in combinatory logic? And also could we consider some inference rules?
By…
Mountain
- 540
0
votes
1 answer
Combinatory logic - Evaluation exercise (abstraction and weak reduction)
I am going through the book "Lambda-Calculus and Combinators: An Introduction".
I am trying to solve the following exercise: evaluation of $[x,y,z].xzy$
The result should be, according to solutions:…
metaphori
- 101
- 2