patternMinor
Basis sets for combinator calculus
Viewed 0 times
basiscalculuscombinatorforsets
Problem
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 basis, which has the same property. There must be an infinite number of such bases, but I don't know of any others.
I am aware that there are a number of single-combinator bases, such as the Iota combinator and the various others constructed/reviewed by Fokker. However, these are "improper" combinators, meaning that they are expressed in terms of other combinators rather than pure abstractions.1 For the purposes of this question I'm interested only in basis sets composed of proper combinators.
Does there also exist a study of the other possible basis sets? Ideal would be something along the lines of Wolfram's study of various other models of computation, in which the various combinations are studied systematically. In particular, I'm interested in whether simple examples of the following things are known:
Any other information about other possible bases for combinatory logic besides S, K and B, C, K, W would be really helpful.
As a broader point, I'm interested in the study of the combinatory calculus as a purely mechanical system, i.e. as a set of transformation rules on binary trees with labelled nodes, which need not be given any particular semantic interpretation. Any pointers towards resources that take this approach would be greatly appreciated. (To Mock a Mockingbird takes this approach but gives an incomplete presentation, whereas Barendregt's the Lambda Calculus is very much tied to semantics, making it hard for me to extract the purely mechanical aspects that I'm interested in.)
1To be prec
I am aware that there are a number of single-combinator bases, such as the Iota combinator and the various others constructed/reviewed by Fokker. However, these are "improper" combinators, meaning that they are expressed in terms of other combinators rather than pure abstractions.1 For the purposes of this question I'm interested only in basis sets composed of proper combinators.
Does there also exist a study of the other possible basis sets? Ideal would be something along the lines of Wolfram's study of various other models of computation, in which the various combinations are studied systematically. In particular, I'm interested in whether simple examples of the following things are known:
- A minimal basis set that includes the I combinator. (I'm using "minimal" to mean that if you remove any member it stops being a basis, so the SKI basis would not count.)
- A minimal basis set that includes the Y combinator, or the $\omega$ combinator (aka mockingbird)
Any other information about other possible bases for combinatory logic besides S, K and B, C, K, W would be really helpful.
As a broader point, I'm interested in the study of the combinatory calculus as a purely mechanical system, i.e. as a set of transformation rules on binary trees with labelled nodes, which need not be given any particular semantic interpretation. Any pointers towards resources that take this approach would be greatly appreciated. (To Mock a Mockingbird takes this approach but gives an incomplete presentation, whereas Barendregt's the Lambda Calculus is very much tied to semantics, making it hard for me to extract the purely mechanical aspects that I'm interested in.)
1To be prec
Solution
It's easy to make other bases by switching out the combinators from one basis with ones that do something similar. For example, starting with BCKW, you can switch $C$ for $T = (\lambda x y. y x)$ (since both switch terms around) and $W$ for $\omega = (\lambda x. x x)$ (since both duplicate things). You know this is still a basis because you can recover $C$ and $W$ from it: $C = B(T(B B T))(B B T)$ and $W = C(B \omega(B B T))$.
Context
StackExchange Computer Science Q#57507, answer score: 2
Revisions (0)
No revisions yet.