Questions tagged [combinatory-logic]

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

Filter by
Sorted by
Tagged with
1 vote
1 answer
62 views

How to count the ways to fill a pyramid in 2d [closed]

I am trying to count the ways to fill a 2D pyramid of base $n$. We have a base already placed of $n$ squares and we try to fill the pyramid with squares (we can place a square only if the two below ...
user avatar
  • 21
0 votes
1 answer
61 views

Line follower robot using max 8 NAND gates

So I have to figure out the logic for a line follower robot using at maximum 8 NAND gates (2 7400HC series NAND circuits). The robot has 3 sensors, which give 1 on a black surface and 0 on a white ...
user avatar
  • 1
0 votes
0 answers
49 views

Is it possible to do abstraction elimination on the strict fixed point combinator Z?

In lambda calculus, the strict fixed point combinator Z is given by: \f.(\x.f(\v.x(x)(v)))(\x.f(\v.x(x)(v))) Is it possible to eliminate all abstractions from the Z ...
user avatar
2 votes
1 answer
80 views

Missing parentheses in $s(k (s I I))(s(\lambda y. s(k y))(\lambda y. s I I)$ leads to interesting error in an nLab page. Need a double check.

I think I found an error in the nLab page on partial combinatory algebra in the Example combinators section: Finally, consider the classical construction of the fixed-point combinator, $Y = \lambda y....
user avatar
  • 1,059
1 vote
1 answer
68 views

Beta reducing $SS(SK)$ using SKI calculus

I have an expression to $\beta$-reduce and I managed to brute force it using the $\lambda$-calculus. I was wondering though, if I could make it in less steps, than what I did, using the $SKI$-calculus....
user avatar
  • 505
1 vote
1 answer
52 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 ...
user avatar
  • 305
0 votes
1 answer
17 views

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 ...
user avatar
  • 5,015
3 votes
1 answer
137 views

SKI Calculus prefix notation of odd/even number

I'm working on a homework with SKI calculus. I saw the hints in this very useful post. We basically defined SKI functions as: ...
user avatar
2 votes
1 answer
73 views

Proof for $\frac{b}{h}=\frac{c(c-1)}{k(k-1)}$, a combinatorial identity

Imagine we have $b$ teachers and $c$ students in a school such that each teacher teaches $k$ students, every two students have $h$ similar teachers. I'd like to prove that $$\frac{b}{h}\:=\:\frac{c(...
user avatar
  • 473
9 votes
2 answers
219 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)$ ...
user avatar
  • 91
2 votes
0 answers
72 views

An equation involving multisets

For multisets $A, B, C, A', B', C'$, if $A \uplus B \uplus \{B \uplus C\} \uplus \{A \uplus \{C\}\}$ = $A' \uplus B' \uplus \{B' \uplus C'\} \uplus \{A' \uplus \{C'\}\}$, must $A=A',B=B',C=C'$, where $...
user avatar
  • 509
4 votes
0 answers
102 views

Relationship between the semantics of simply typed lambda calculus and combinatory logic

The simply typed lambda calculus has a class of extremely intuitive models where each basic type $\sigma$ is modeled by some set $[\![\sigma]\!]$, and a complex type $\sigma\rightarrow\tau$ is then ...
user avatar
  • 137
1 vote
0 answers
54 views

number of surjective functions from X to Y where card(Y)=k < n =card(X) [duplicate]

Let $X=\{1,...,n\}$ and $Y=\{1,...,k\}$. If $n\gt\ k$ then the number of surjective functions $f:X\to Y$ $\;\;$is $\;\sum_{j=0}^{k-1} (-1)^j\binom{k}{j}(k-j)^n$ Here I show what I have done. I can'...
user avatar
0 votes
0 answers
164 views

Hindley and Seldin "Introduction to Combinators and Lambda calculus": Question about the solution to exercise 3.5.

The question is concerning the solution to exercise 3.5. In the exercise, they ask us to prove that any finite set of simultaneous equations $x_iy_1...y_n=Z_i$, where $1\leq i\leq k$, can be solved ...
user avatar
  • 13
0 votes
0 answers
36 views

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 ...
user avatar
  • 393
2 votes
1 answer
82 views

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 ...
user avatar
  • 393
3 votes
0 answers
422 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 ...
user avatar
  • 53
1 vote
1 answer
116 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'...
user avatar
  • 1,219
0 votes
0 answers
98 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 <...
user avatar
  • 209
25 votes
1 answer
1k 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 ...
user avatar
  • 1,939
1 vote
1 answer
234 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 ...
user avatar
  • 10.4k
1 vote
1 answer
360 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 ...
user avatar
  • 10.4k
2 votes
0 answers
42 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$ ...
user avatar
  • 21
1 vote
1 answer
448 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 ...
user avatar
  • 31
0 votes
1 answer
123 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: ...
user avatar
  • 101
5 votes
0 answers
435 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). ...
user avatar
  • 800
2 votes
1 answer
56 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 ...
user avatar
1 vote
0 answers
69 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 ...
user avatar
2 votes
2 answers
392 views

An exercise on combinatory logic

Can somebody help me with the following exercise? (1) Find a combinator $X$ such that $Xy = X$; (2) Find a combinator in normal form with the same property. Rules for reduction are $Ix > x$ $Kxy &...
user avatar
2 votes
1 answer
150 views

Hindley's "Introduction to combinatory logic", exercise 6 chapter 2.

Can somebody help me with the following exercise? Find a combinator X such that X = S(KK)(XS). Reduction rules are usual: IX reduces to X (identity combinator) KXY reduces to X SXYZ reduces to XZ(...
user avatar
0 votes
0 answers
59 views

What is this P4 correspond to in proposition as types?

I was reading "Proofs and Types", so there came across that any proposition can be converted to lambda form. So was trying out with Hilbert system's axioms P1. $A \rightarrow A $ P2. $A \rightarrow (...
user avatar
  • 725
1 vote
1 answer
85 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?
user avatar
  • 237
3 votes
1 answer
274 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 ...
user avatar
  • 2,543
6 votes
1 answer
815 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 ...
user avatar
  • 725
2 votes
1 answer
99 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 ...
user avatar
  • 725
6 votes
2 answers
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 ...
user avatar
  • 800
1 vote
1 answer
179 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 ...
user avatar
0 votes
1 answer
199 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 ...
user avatar
  • 737
6 votes
1 answer
337 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 ...
user avatar
2 votes
1 answer
137 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 ...
user avatar
  • 431
4 votes
1 answer
455 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 ...
user avatar
5 votes
1 answer
718 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 ...
user avatar
1 vote
1 answer
131 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?
user avatar
  • 2,304
19 votes
0 answers
501 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 ...
user avatar
5 votes
2 answers
225 views

Prove that all combinators must fulfill A x = x for some x, given that M x = x x and composability of any two combinators

I'm working through Raymond Smullyan's "To Mock a Mockingbird" and I'm stuck on the first problem in the combinatory logic section. I'd appreciate hints, but no spoilers please. The problem is ...
user avatar
4 votes
1 answer
148 views

combinatory basis for head reduction

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 ...
user avatar
3 votes
1 answer
4k views

Looping (ω) Combinator

Can someone explain this combinator? I understand $\lambda x. x$, but I don't understand $\lambda x. x x$ From what I've gathered, this means given x, return the application of x to x. I don't ...
user avatar
34 votes
3 answers
8k views

Can someone explain the Y Combinator?

The Y combinator is a concept in functional programming, borrowed from the lambda calculus. It is a fixed-point combinator. A fixed point combinator $G$ is a higher-order function (a functional, in ...
user avatar
  • 27.5k
1 vote
2 answers
2k views

Proving a combinator is a fixed point

Show that the term ZZ where Z is λz.λx. x(z z x) satisfies the requirement for fixed point combinators that ZZM =β M(ZZM).
user avatar