The Least Known Field of Logic
What is combinatorial logic?
Let me first clarify that this hub is not about binary logic, which can also be called combinatorial logic. The combinatorial logic I'm talking about is a field that has declined in use ever since the invention of computers, which take care of tedious manual calculations that this branch of logic was created to abate. Therefore, it is no longer taught just anywhere, or really at all. Most of my math and computer science college professors had never even heard the term "lambda calculus" before, which is a more formal definition of combinatorial logic. Don't be scared and stop reading just because of the word calculus, because combinatorial logic has little, if anything, to do with mathematical calculus. Lambda calculus is really just a different notation for combinatorial logic, a more formal way to express it. Personally, I prefer the abstraction that is provided by working with the more general combinators in combinatorial logic (after which it is named).
So what is combinatorial logic? It is a field of logic, mathematics, and computer science. It blends all three together in a fascinating use of an idea called a combinator, which can be a boolean operation, a mathematical function, or a computer function, and it can even be all of them at once! If you like the little introduction I'm about to give you, you can read up more in-depth on the subject in Raymond Smullyan's book, "To Mock A Mockingbird." Note that said book is much different than the novel "To Kill A Mockingbird," which I have also read.
Smullyan's book is partly a study of intriguing logic puzzles involving fictional characters who embark on journeys into worlds whose laws of logic are interesting, sometimes ludicrous, but almost always humorous and fascinating. However, once you get to chapter 30, which is about halfway through the book, Smullyan delves into a thorough exploration of combinatorial logic. Though he doesn't actually touch on lambda calculus, he does derive some more formal procedural combinators towards the end of the book.
Just to set your mind at ease, I'm not going to go into great detail here. In fact I won't even cover any lambda calculus at all. This is just a brief overview of combinatorial logic. While Raymond Smullyan uses a rather clever conceptual analogy of birds and bird calls being the combinators in his book, I prefer the more professional, but less amusing, analogy of computer programs or functions.
N.B. Please note that the following mathematical combinators and their explanation is for understanding purposes only, and is an informal example because in formal combinatorial logic, numbers don't exist, at least not without lambda calculus and a few other tricks. So a function that adds some number 3 to x wouldn't normally exist in this field, it's just I'm using it anyway as an example to help you understand it better. My apologies if this greatly disturbs anyone!
Given a function F, you can apply an argument to it and get a result back. For instance:
Fx = x + 3
This is the definition of the function, which tells us that no matter what x we put in, we always get back x plus three. So, if we apply the value 4 to the function F, we get back 7:
F4 = 4 + 3 = 7
This is basic mathematical function theory, and combinatorial logic encompasses this concept. Suppose we have a program T (which is actually a combinator) that operates as follows on two other indistinct programs, which we will name x and y:
Txy = yx
So, really, the program T just exchanges whatever arguments you put into it. Also notice that the parentheses restore to the left, so writing Txy means you can infer that (Tx)y is the same thing. This is different than writing T(xy) which implies that y is applied to the function x first, and that result is then applied to T. To illustrate this difference, let's look at our function F from before, and add a new function, G.
Fx = x + 3
Gx = x5
This new program, G, takes whatever x you give it and applies the value 5 to it, since the 5 comes after x just like x comes after G.
Now, let's see what results if we apply F to G.
GF = F5 = 5 + 3 = 8
Did you follow that? Applying F to G means that G takes whatever x we gave it (in this case, F) and applies 5 to it. This gives us F5 (F with 5 applied to it). Then, applying 5 to F gives us 5 + 3, which is 8. I'll add that we really haven't used non-mathematical combinators yet, but now you get the idea.
In the last example, both F and G were combinators. That is, they could be applied to each other and then evaluated. The same is true for all combinators; you can apply them to each other and simplify to obtain a result. This simplification process in terms of lambda calculus is called beta reduction, which is the easiest form of reduction. It allows us to derive new combinators that behave differently than the ones we derived them from. For instance, let's delve into a few basic combinators for a moment.
Consider two combinators K and S such that:
Kxy = x
Sxyz = xz(yz)
For clarification, I will also show K and S with parentheses restored to the left:
(Kx)y = x
((Sx)y)z = (xz)(yz)
Now we're going to try and use these programs to derive a new program from them. Let's examine the properties of the program SKK.
SKKx = ?
To find out what this program does, we need only to apply any x to SKK and see what the result is. Let's set x to be KK and apply this x = KK to the program SKK and see what happens. If you get confused, refer back to the definitions of K and S to see how to evaluate this.
SKK(KK) = (((SK)K)(KK)) = K(KK)(K(KK)) = KK
What an interesting result. We applied KK to SKK and got exactly KK back. Let's see what happens when we apply a different x to SKK, such as SKS.
SKK((SK)S) = (((SK)K)((SK)S)) = K((SK)S)(K((SK)S)) = (SK)S
Incredible! The same thing happened! We got back exactly what we put in. Let's generalize this program SKK by evaluating it generically for all x:
SKKx = ((SK)K)x = Kx(Kx) = (Kx)(Kx) = x
So we have just derived a new program from SKK, such that for all x,
SKKx = x
So to simplify matters, we'll call this the identity program, I. So now we have:
Ix = x
for all x. I is actually the program SKK as we have seen, but since we already have enough programs to define it, we can simply write it as I from now on.
Raymond Smullyan's "Mockingbird"
Now we get into some really fun stuff. Let's imagine that there might be a program that, say, mimics the user (similar to the mockingbird in Smullyan's book). We'll call it the mimicking program. How would it do so?
Mx = xx
This means that no matter what x you apply to the program M, it simply gives you the same result that x would give you upon applying x to itself. For instance, take the program I from earlier. I's response to itself would be:
II = I
So M should mimic this response as if it were really the program I, right? This is shown below:
MI = II = I
Indeed, it does! But, is it possible to derive such a program M using only the programs S, K, and I that we have so far? If you want a little exercise to do for yourself, try it out and then come back and check your answer.
For now, I'll just assume you didn't and skip ahead to the answer.
But first I'll make you scroll down a bit that way you don't accidentally see the answer if you wanted to do the exercise.
Keep on scrolling...
You're nearly there.
Ha ha ha...
Okay, fine, I'll get on with it now.
The answer is, yes you can. Such a program would be SII. Let's examine why this would be (which really means, derive M by proving that SII = M for all x).
SIIx = Ix(Ix) = x(x) = xx
By golly, it does work! SIIx = xx is the exact same program as Mx = xx. Therefore, we have just derived M from S and I alone. Now, before I leave you, I have one more exercise for you, and I'm not going to post the answer here. Perhaps you can find it online somewhere, or try it yourself. But I will tell you that it can be done.
Here is the exercise--try to define the mimic program M in terms of S and K, without using I. Sound interesting? It's a rather lengthy program, I'll tell you that much, and there are quite a few parentheses. Whether or not you choose to try it, good luck, and may combinatorial logic serve you well whether you know about it or not. Ha ha ha ha ha.....no really. I'm serious.
Alright, I'll give the more interested readers one small hint. You can't define M in terms of I right? But isn't I itself defined in terms of S and K? So really, defining M in terms of S and K without I shouldn't be all that hard. Get the point? (In otherwords, maybe you could use the definition of I in terms of S and K in combination with the definition of M in terms of S and I). If I say more I might as well tell you the answer here and now...
Well, until the next hub, good day from Cybermouse. <:8()~
More by this Author
This is an interesting question to be sure, and one I hope to answer by the end of this hub. In order to answer it, I will briefly go over each section of instruments, and a few instruments in each section, explaining...
Are you among the select few who actually enjoy logic games (i.e. Sudoku) on a regular basis? I have found that most people who don't even enjoy logic games are aware of the Sudoku craze, or know of someone who enjoys...
This hub is a complete guide on the Guitar Hero series of games and the various levels of difficulty associated with each. It explains why the difficulty exists and all the different kinds of notes and crazy things to...