# Questions tagged [combinatory-logic]

For questions about logical systems defined via the application and term-rewriting of combinators. These systems often have a close connection to the lambda calculus.

23 questions
0answers
43 views

### Does a Turing complete set of invertible combinators exist?

We'll say that a combinator A is invertible if there exists A' s.t. A'(Ax) = A(A'x) = x For example, Sxyz = xz(yz) is clearly invertible in this sense because we ...
1answer
48 views

### Find a lambda term satisfying two equations

I'm just looking for the general idea on how to approach the following problem: Find a term $\Delta=\lambda x.xUV$ such that: $\Delta\Delta=K$ $\Delta K=S$ (it's a system of 2 equations, I didn't ...
0answers
19 views

### Combinatory Logic formula obtained from lambda term, proof?

I translated the following $\lambda$-term: $z(\lambda b.ba)(tt)(\lambda y.y)$ in the following CL formula: $z(CIa)(tt)I$ through the Markov algorithm. Now I'd like to prove the translation was ...
0answers
26 views

### Job shop scheduling with events that should be completed simultaneously

I'm working on a scheduling algorithm that schedules a set of events with an event duration to a set of agents with various working times. However, some events require more than one agent to be ...
0answers
65 views

### Combinatory logic equivalent to System F

Simply typed lambda calculus has a combinatory logic equivalent with the same expressive power without the need of defining names via lambda abstraction. Is there a formalism as powerful as System F ...
1answer
51 views

### Is there a combinator that introduces brackets to a combinatory logic expression using just B?

Suppose I have the expression $abcdef$ and I want a combinator $X$ that does this: $Xabcdef=a(bcd)(ef)$. Is it possible to express $X$ using just the $B$ combinator, defined by $Babc=a(bc)$? Is ...
0answers
73 views

3answers
2k views

### What is the purpose of the SKI combinator calculus(or even lambda calculus)? What are some real life examples of its use?

I understand what it is, but I don't see how it is any use for algorithms or anything. Maybe I am missing something. I need someone to give me an example of how it can be used so I can understand it ...
0answers
40 views

### Computing the index in a structured way

I want to map the various combinations to an unique index: For a given $n$ and $r$, we would have $\binom{n}{r}$ arrangement for values:$[0,\dots,n)$: Ex: For n = 6, r = 3 [012, 013, 014, 015, ..., ...
1answer
337 views

### Iota combinator and implicational propositional calculus

There is are two esoteric languages with minimally functionally complete operators, iota and jot, that are closely related to SK combinators. I'm attempting to understand the relationship between ...
1answer
35 views

### “Archiving” byte sequence into human-readable set of chars

Ok, lets assume we have sequence of 1000 bytes. So the possible number of value variations is 2^100. Is there a way to "index" each variation with letters and decimal numbers (A-Z, 0-9), having as ...
1answer
262 views

### Are combinatory logic terms always larger?

So there is an algorithm to convert lambda calculus terms to combinatory logic using SK combinators. It produces things that explode in size. I would like to know more about this explosion in size. I ...
1answer
139 views

### Smallest non-halting unlambda program

Is sii`sii the smallest Unlambda program that doesn't halt? In other words, what is the smallest non-terminating combinator term in SKI augmented with $C$ (...
2answers
274 views

### Combinatory interpretation of lambda calculus

According to Peter Selinger, The Lambda Calculus is Algebraic (PDF). Early in this article he says: The combinatory interpretation of the lambda calculus is known to be imperfect, because it does ...