Questions tagged [combinatory-logic]

Combinatory logic, combinatorial calculi, and other questions about combinators and variable-free variants of the $\lambda$-calculus.

53 questions
Filter by
Sorted by
Tagged with
80 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 ...
• 1,434
29 views

Can a CL-term have multiple fixed points?

Given a CL term $E$, can there exist multiple non-equivalent fixed points for $E$? I think: any fixed point of $E$ can be expressed as $Y(E)$, this expression cannot reduce to multiple non-equivalent ...
• 1,434
52 views

254 views

What axioms can be added to $S,K$ combinator algebra without making it collapse into triviality?

My understanding is that if you start with the free magma on two generators (call them $S$ and $K$) and then take a quotient with respect to the usual $S$ and $K$ equivalence rules ($Sfgx = fx(gx)$ ...
• 91
83 views

• 540
659 views

Relation between Lambda calculus and SKI combinator calculus

I have played around with evaluation of Lambda terms in Lambda calculus and their counterparts using SKI combinators. While the results are extensionally equal (as they should be), there are striking ...
• 53
1 vote
192 views

Would this be considered a combinator

A combinator is a function that doesn't utilize free variables. E.g. $$\lambda a. \lambda b.a$$ However all of this works in an untyped environment. When working with types, let's say $nat$. can'...
• 1,257
143 views

Expressing I combinator and numerals via X combinator

So I understand that the X Combinator is defined as X = λx (x S) K I am also aware of definitions of S and K and I: S = XK <...
• 249
2k views

Why can't we formalize the lambda calculus in first order logic?

I'm reading through Hindley and Seldin's book about the lambda calculus and combinatory logic. In the book, the authors express that, though combinatory logic can be expressed as an equational theory ...
• 2,139
1 vote
299 views

The definition of the Church numerals in combinatory logic

Hindley & Seldin define ([1] Definition 4.2, p. 48) the Church numerals as follows: (I'm paraphrasing to save space. Here's the original page.) For every $n \in \{0,1,\dots\}$, the Church ...
• 11.6k
1 vote
465 views

How to prove the Church-Rosser theorem for combinatory logic

I need help proving the Church-Rosser theorem for combinatory logic. I will break down my post in three parts: part I will establish the notation required to state the Church-Rosser theorem as well as ...
• 11.6k
43 views

Number of unique items in a big set from small sample

We have a box with $m=1\,000\,000$ cards. Each card contains one word. The words are repeated so there is a relatively small number of $n$ unique words. $n$ is unknown. If we get a sample of $k=5000$ ...
• 21
1 vote
622 views

Equality in the untyped lambda calculus without extensionality

Raymond Turner (in p.66 of "Truth and Modality for Knowledge Representation") elaborates a combinatory logic, $PT$, whose language $L2$ is the following language of terms (together with a language of ...
• 31
163 views

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: ...
• 101
459 views

Can all computable numeric functions on church numerals in ski-combinator calculus be expressed using only completely evaluated terms?

Let a term in ski-combinator calculus be called "complete" if every primitive is partially applied (so all S's are applied to at most two arguments, all K's to at most 1, and all I's are not applied). ...
• 870
59 views

Rolling Dice Probability

A fair dice is rolled 3 times, The probability of the product of the three outcomes is a prime number is? The products which give a prime number I found out to be only 4. However for the total ...
• 307
1 vote
81 views

Consistency of the SKI calculus as unprovability of S = K

The exercise I'm dealing with asks me to show that by adding $S = K$ to the usual reduction rules for the SKI-calculus, one obtains an inconsistent equivalence. This must be done without using Böhm's ...
433 views

• 795
1 vote
153 views

Proof of B, C, K, W system

There is a B,C,K,W system. In particular, there is presented the following identity: $B = S (K S) K$ How to prove this statement?
• 237
331 views

Intuitively speaking, why was there a need to "eliminate" quantified variables in mathematical logic?

I'm trying to wrap my head around the understanding of lambda-calculus, from a math/computing/logic standpoint and am reading more about its very genesis. This has taken me to 1924 - Schonfinkel's ...
• 2,771
1k views

Fixed point combinator (Y) and fixed point equation

In Hindley (Lambda-Calculus and Combinators, an Introduction), Corollary 3.3.1 to the fixed-point theorem states: In $\lambda$ and CL: for every $Z$ and $n \ge 0$ the equation $$xy_1..y_n = Z$$ can ...
• 795
131 views

On a corollary of the Church-Rosser Theorem

In the proof of Corollary 1.41.5 from Hindley-Seldin, $\lambda$-Calculus and Combinators - An Introduction, If $a$ and $b$ are atoms and $aM_1...M_m =_\beta bN_1...N_n$ then $a = b$ and $m = n$ and ...
• 795
2k views

In what sense is the S-combinator "substitution"?

According to the Wikipedia page on SKI-combinator calculus, I is the identity function, K is the constant function, and S is "substitution". I understand the first two, but I don't see what S has to ...
• 870
1 vote
209 views

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 ...
• 271
208 views

Proof completion: if $Y$ is a closed term in strong nf, then $Yx$ weakly reduces to a strong nf $Z$

I am self-studying Hindley & Seldin's Lambda-Calculus and Combinators. I would appreciate some help with filling in a final detail for a proof for the following statement regarding combinatory ...
• 747
440 views

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 ...
• 271
162 views

Chaitin's constant for lambda calculus and combinatory logic

I have found some approximations of Chaitin's Constant for turing machines but I have not found approximations for others. I'd like to have a rough estimate or upper bound on it for lambda calculus ...
• 461
490 views

How to represent Smullyan's "Mockingbird" puzzles in (Homotopy) Type Theory?

(If you're unfamiliar with the puzzles from To Mock a Mockingbird, three pages tell you everything you should need.) Is it possible to solve the riddles in To Mock a Mockingbird in a "propositions as ...
• 291
763 views

Smullyan-To-Mock-a-Mockingbird, Find egocentric bird in L

Question (29, p. 81). Let me tell you the most surprising thing I know about larks: Suppose we are given that the forest contains a lark $L$ and we are not given any other information. From just this ...
• 159
1 vote
174 views

Why SKI when SK is complete

Why people talk about SKI calculus when S and K combinators can be used to create any other combinator including I?
• 2,420
557 views

Where to go after _To Mock A Mockingbird_?

So long ago I read Raymond Smullyan's delightful To Mock A Mockingbird, a gentle introduction to combinatory logic (representing combinators as 'birds' singing back and forth to each other). I fell ...
• 52.4k
Consider combinatory calculi that don't have tail reduction. So there may be combinators $x$, $y$ and $z$ such that $y\to z$ but $xy\nrightarrow xz$. We can still write every combinator as a ...