# 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.

63 questions
Filter by
Sorted by
Tagged with
15 views

### How to write a Y-combinator implementation in javascript that does not exceed maximum stack size

TL;DR: Why applying a javascript implementation of a factorial function with a lazy Y combinator fails with "Maximum call stack size exceeded"? Here is the code: ...
17 views

### Short SK combinator expression with long reduction / Busy Beaver for SK combinators

Question (short and simple version): Can anyone suggest a very short SK combinator expression with a ridiculously long, but still terminating, reduction path (ignoring loops)? Question (longer version)...
• 111
48 views

### Relation between NOT gate and negative numbers 2's complement

The steps to get a number in 2's complement are simple: Flip the bits (Using NOT) Add +1 (afaik this step is done to eliminate the duplicate 0) Recently I've seen an ALU design that can operate ...
• 101
86 views

### Is there a 2SAT encoding for a NAND gate

I am trying to encode some circuit checking algorithms, but encountered difficulty creating a 2SAT representation for a NAND circuit. Is there a proof that this is not possible?
94 views

### Book references for combinatory logic as applied in Haskell?

I am looking for book references on combinatory logic. Is there a book focused on how combinatory logic is applied in the context of pure functional languages like Haskell? I found "Combinators: ...
• 259
1 vote
175 views

### Iterating over combinations of 4 timestamps from 2 timelines *efficiently*

I need help in finding a more performant algorithm. I have two timelines in the form of two indexed lists where each element is a floating-point value that represents seconds. The values in each list ...
• 11
1 vote
57 views

### K in SKI combinator calculus: why doesn't it take one parameter since it ignores its second?

In the SKI combinator calculus, Kxy returns the constant function which always returns x. Since y is always ignored, why not just define K as having a single parameter, namely, x? What is the purpose ...
• 179
33 views

### optimization problem about capacitated vehicle routing problem

I have an optimization problem. The problem consists initially of the presence of several trucks, each one having different maximum capacities. There are also multiple customer orders, each with a ...
1 vote
63 views

### Must the evaluation strategy for a language be specified in order to apply the Church-Rosser Theorem?

The Church-Rosser Theorem [0] states that the Lambda Calculus (LC) is confluent: between a source expression S and target expression T, the latter in normal form, for any given P, a sequence of ...
• 39
58 views

### Is there any algorithm to find all unique pairs of People with age equal to a given number in less than O(n²)

I have a problem where I have to find all the pairs of a list of People where the sum of their age is equal to a given number under time complexity less than O(N²) ...
1 vote
301 views

### Combinational logic check if bits is prime

I wonder if there's Digital Logic Circuit (using combinatorial logic gates) that check if number is prime or not. For example given input fixed 8-bit that will produce 1-bit output. 00000101 will ...
97 views

### Why do combinators look this way?

Out of curiosity, why do combinators look this way? For example, why is $K = \lambda x y \to x$ and why is it called $K$? Why is it not $\lambda x y f m \to f m x$? These are just arbitrary letters, I ...
153 views

### How, if possible, can we efficiently compute with lazy data structures in 𝜆-calculus?

In Haskell, we can use the following code to define fibonacci numbers, fibs = 1 : 1 : zipWith (+) fibs (tail fibs) And its time complexity is linear. I cannot find ...
• 63
71 views

### What are the fixed-points of the Y combinator?

Since the Y combinator itself is a function (albeit a higher-order one), I was wondering what the fixed-points of Y itself are.
• 131
335 views

### What benefits are obtained by allowing the occurrence of free variables and open terms in lambda calculus?

Because of the existence of free variables in lambda calculus, the evaluation of open terms (at least as outlined here) is more complicated relative to the evaluation of closed terms since the ...
• 111
78 views

• 395
6k views

### How does the Y combinator exemplify "Lambda calculus inconsistency"?

On the Wikipedia page for Fixed Point Combinators is written the rather mysterious text The Y combinator is an example of what makes the Lambda calculus inconsistent. So it should be regarded with ...
• 1,710
2k views

### Why are combinators important in lambda calculus?

I just recently learned a little about the lambda calculus, from the brief intro in the text Programming Language Pragmatics and this outstanding 4-video sequence from Adam Doupé. Basically I learned ...
• 495
1 vote
95 views

### Trouble Replicating Proof of The Lambda Calculus Fixed Point Theorem

From pg. 35 of Lambda Calculus and Combinators An Introduction: Corollary 3.3.1 in $\lambda$ and $CL$: for every $Z$ and $n \ge 0$, the equation $$xy_1 \ldots y_n = Z$$ can be solved ...
• 285
1 vote
23 views

### How to interpret scoped variables next to each other within Lambda Terms and CL-terms?

In both the lambda calculus ($\lambda$-calculus) and Combinatory Logic (CL), we have the notion of function application. For example: \begin{array} & \left( \lambda x . x \right) y = y & \...
• 285
107 views

### Understanding A Recursive Definition of CL-Terms in Combinatory Logic

From page 26 of Lambda-Calculus and Combinators: Definition 2.18 (Abstraction) For every CL-term $M$ and every variable $x$, a CL-term called $[x].M$ is defined by induction on $M$, thus: (a)...
• 285
734 views

### Simplest complete combinator basis pair for flat expressions

In Chris Okasaki's paper "Flattening Combinators: Surviving Without Parentheses" he shows that two combinators are both sufficient and necessary as a basis to encode Turing-complete expressions ...
34 views

### The range of functions defined by pure lambda terms

Consider a full set-theoretic model of the simply typed $\lambda$-calculus with infinite base types. Say that an element in this model is pure if it is the semantic value of some closed pure term in ...
• 230
207 views

### When can you "invert" an equation in the lambda calculus

Suppose that $M$ is a full model of the simply typed lambda calculus. Suppose each base type is infinite. Now suppose that $f$ and $g$ are two functions in $M$ (not necessarily in the same domain) ...
• 230
1k views

### Basis sets for combinator calculus

It is well known that the S and K combinators form a basis set for combinator calculus, in the sense that all other combinators can be expressed in terms of them. There is also Curry's B, C, K, W ...
• 976
281 views

### What functions can combinator calculus expressions compute?

A combinator expression (let's say in the SK basis) can be thought of as a function that maps combinator calculus expressions to combinator calculus expressions. That is, one can think of an ...
• 976
436 views

### Combinator equivalent to eta conversion

In lambda calculus, one can prove that two expressions compute the same function if they are equivalent under both beta reduction and eta conversion, where eta conversion consists of eta reduction,  ...
• 976
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, ..., ...