Combinatory Logic

Combinatory logic is the logic of combinators, which are functions taking a combinator as an input and giving a combinator as an output. In other words, all you will ever get are more and more combinators. This may seem circular, but it turns out to be extremely useful. Raymond Smullyan provided a good metaphor for combinators in his book "To Mock a Mockingbird". He imagined a forest of birds.If you called out a bird's name to another bird, it would respond by calling out another bird's name. If a bird x hears a bird y, it calls out a bird xy. Also, xyz, for example, is taken to mean (xy)z. This is not necessarily the same as x(yz). Also, xy does not have to be the same as yx. Two birds are of primary importance. The first is the kestrel K. It is defined as Kxy = x. Thus, no matter what bird y you call out to Kx, it always replies with x. Also, there is a starling S. Essentially, Sxyz is always xz(yz). This is more complex but still important. With these two, any bird can be created.

Before we go on to make every possible bird, we must start small and create the identity bird I. This is the simplest possible bird. Ix = x. It just repeats what you said back to it. To make it, consider SKK. SKKx = Kx(Kx). However, no matter what you call to Kx, it replies with x. Thus SKKx is x so SKK = I.

As another example, there is a mockingbird M such that Mx = xx. M can be thought to mock the bird x. Incidentally, you must never mock a mockingbird. If you call out M to itself, you get MM. This reduces to MM, which reduces to MM, which reduces to MM... Uh oh. However, this mockingbird can be made using S, K, and I. Thus the system of combinators from S, K, and I is not consistent. It is still, however, very powerful. The mockingbird is SII. Thus SII(SII) is inconsistent.

It is actually the case that you can make any possible computable function using S and K. For example, you can build numbers and then a function which squares a number. Also, you can Godel code S, K, (, ), and = and have a function to calculate the Godel code. An example Godel code is S = 1, K = 2, ( = 3, ) = 4, "=" = 5. For example, since MM = S(SKK)(SKK)(S(SKK)(SKK)) the Godel code of MM is 131224312243131224312244.This function can construct the statement a = b for any a and b. What you can't do is create a function to tell whether this is true or false in general. If you could, Kurt Godel proved that there was an expression which is true if and only if it is false. The whole system would fall apart and it would be even worse than having MM.

In fact, you can construct any function. In effect, you could run programs. This means that you can actually run everything your home PC/tablet/laptop can or even a supercomputer can, just by using S and K. However, calculating strings of S and K is very, very slow. Don't throw out your computer. Combinatory logic is very similar to a Turing machine. You can run the universal Turing machine in combinatory logic and you can run combinatory logic on a universal Turing machine.

Related entries