Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [combinatory-algebra]

The tag has no usage guidance.

0
votes
0answers
17 views

Semi universal proper combinator

It is known that the two combinators S and K defined by Sxyz=xz(yz), Kxy=x, generate all other possible combinators. It is also known that no single proper combinator (combinator that can be defined ...
5
votes
0answers
193 views

Proper full submodels of full models of type theory

Let $N$ be the standard full model of the simply typed lambda calculus with infinite base type $o$ and let $X$ be an infinite and coinfinite subset of $N(o)$. I want to know if there's a full ...
1
vote
1answer
167 views

combinator SSS(SS)SS is not strongly normalizing. Why?

I highly speculate that combinator SSS(SS)SS is not strongly normalizing. What is the argument for the non strong normalization?
23
votes
6answers
35k views

Difference between a 'calculus' and an 'algebra'

What is really the conceptual difference between a calculus and an algebra. Eg. Is SKI combinator calculus really a calculus? A friend claims that free variables are fundamental for a calculus, and ...