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 entriesTuring machines
|Home • Contact|