Dr. Thursday's Thursday Post

Life in Three Dimensions: Part II - The Doctor and the Dolls (or) Pronouns, Beer, Pyramids, and the "abbr."

Whatever was the man who built the pyramids, one feels that he must (to put it mildly) have been a clever man.
[GKC, William Blake 101]

I shall now resume my discussion of dimensions, but because you are almost certainly a "lit'ry" person I am going to have to explain the next step with quite a bit of care. Do not worry! Do not fear! It is not very complex, but it is very philosophical, and you will have some fun on the journey.

Our next step in our study is the very useful and fundamental trick of mathematics and computing called recursion. Recursion is nothing more than a very fancy use of the idea of a pronoun, but a sophisticated, nay, a magical and powerful pronoun - one which has lost its fear of crossing over into the realms of numbers, sets, functions and functionals, and all the complexities of (drum-roll) THE LEARNING which we call "Mathematics".

But perhaps you would rather find out about why computer scientists play with dolls. No, not the ones that say "Math is hard"! These kind.
You may have seen this beautiful Russian doll - it stars in a wonderful children's book called The Doll in the Window by Pamela Bianco. As you may know, this is made of wood, and there is a seam around the middle. If you twist carefully, it opens, and inside, you will find
another doll.

Similarly, the second doll has a seam, within which you will find...

a third doll. Not to prolong the tension, here is the whole family:

Now, these are my own - yes, now you can tell your friends that there really is a computer scientist who plays with dolls! But hang on for the punch line. It's not what you will expect. When I taught at the Unnamed School, they had a set in the department office, and once I sent a student there to borrow them to explain the SAME thing I am about to explain to you.

You see, there are several interesting things about these nesting dolls. First, the overall idea of a thing and another thing related to it, the same but somehow smaller - something defined in terms of itself - in the abstract, we call this recursion, and that is the topic for today. Second, there is something curious one may discover somewhere about the fifth or sixth doll - will the next one have a seam? Will there be yet another doll inside? Does it ever stop? And what would happen if it didn't?

You think this is NOT Chestertonian? Not only is it in a Chesterton book, but it is used in a rather horrifying lesson in theology by Father Brown: "there is this about such evil, that it opens door after door in hell, and always into smaller and smaller chambers." ["The Sign of the Broken Sword" in The Innocence of Father Brown] Hopefully, we won't go in the opposite direction today, which is the very same thing: "One went into larger and larger windowless rooms, rooms big with Babylonian perspective; but one never found the smallest window or a whisper of outer air." [GKC, Orthodoxy CW1:266] Indeed, I have a point in all this, if you are patient: "...for me all good things come to a point, swords for instance." [ibid.]

Some weeks back, a posting, or a comment, began to explore this line from Orthodoxy: "Poetry is sane because it floats easily in an infinite sea; reason seeks to cross the infinite sea, and so make it finite." [CW1:220] We are going to see two things here - one of them quite finite, like my eight dolls; the other is infinite, and yet limited, so we need not cross any infinite seas today. We'll do that next week, hee hee.

So! If you wish to find out more about dolls, beer, and pyramids, press here.
The doll, of course, is just an attractive starting point. I am not proposing to go into "recursion" as we do in computer science, but only to give you a rough, poetic idea about it, in order that I can show you something curious, and perhaps "artistic". Well - some may call it art, others just a pattern, but in order to talk about it, we need to grasp the idea behind (not inside) the dolls. So, let us begin with a pronoun.

The Apostles' Creed begins with the pronoun "I"; but it goes on to rather more important nouns and names.
[GKC, The Well and the Shallows CW3:350]

The pronoun, you may recall, is just a name for something or someone, which has the remarkable property of both linking and unlinking from person to person, and thing to thing - a magical kind of verbal mirror, which by reflection can show any chosen individual or individuals. It is a real time-saver - it permits real simplifications of what would be very complex ideas. (Though, as any magic, it has its risks. It is easy to forget what the REAL thing is to which the current reflection is to correspond!) But we are not going to play that kind of game - the kind where one has to provide hints in parentheses. Heaven knows I use them a lot - but then they are another kind of magic, for another kind of simplification - or simpleton.

Now, pronouns in math are nothing new - except perhaps for the term. Us math guys usually call such things "variables" - grade-school teachers, for some strange reason, call them "placeholders" which sounds like a thing at a restaurant. But after all, "x" is just as valid a pronoun in a statement like

x + y = 7

as "he" is in a statement like

He is reading a book by Chesterton.

In both cases, we are told something and we are also left wondering about something. (hee hee: which book?)

However, unless one has played with some of the "advanced" kinds of mathematics, one rarely encounters the very special form of "pronoun" I am about to describe. I have had to make up an example which I can explain quickly, but will tell you what you need to know, so if you DO know about functions and recursion, don't be too shocked I did not use the factorial! (hee hee) But! its! levity! is! just! a! little! too! much! for! the! present! (Sorry - "x!" is read "x factorial" in math.)

OK. Now that I have told you all this, let us talk about beer. Ah! In our day, unlike GKC's, some of us buy beer in cans. I am not going to argue about that; let us just take it as a given. Some of us have more money, and can buy it in bottles or kegs, or more time, and can brew our own. But unlike these other containers the beer can has the wonderful property of being fun to stack into pyramids. Just to clarify for those few of you who may have never done this, a beer can pyramid is made by placing two cans side by side, and one can centered above their point of contact. Usually, people that drink beer from cans drink one can at a time, and so they are forced to build their pyramids as the ancients did: starting at the bottom. (If you want to hear about the fools who build them starting at the top, you must wait for my book on Subsidiarity.)

When one builds a pyramid, one must calculate the requirements first - just as our Lord told us. (see Luke 14:28) Let us say we wish to have a nice small one, with just six cans across the bottom. That means we'll need six cans, and however many cans make a pyramid with five cans at the bottom. Remember we need to stagger the rows as we go up, so if we have six on the bottom, we can only have five in the next row up. Fine.

So to make the pyramid with five cans on the bottom, we need those five cans, and however many are needed to make a pyramid of four.

So to make the pyramid with four cans on the bottom, we need those four cans, and however many are needed to make a pyramid of three.

So to make the pyramid with three cans on the bottom, we need those three cans, and however many are needed to make a pyramid of two.

So to make the pyramid with two cans on the bottom, we need those two cans, and however many are needed to make a pyramid of one.

BUT A PYRAMID OF ONE CAN IS ONE CAN.

So that means I need one, and two, and three, and four, and five, and six cans, or 21 cans total. (Great - we could do it with one case, and have three left over to enjoy later.)

Now, remember how I told you about how a PRONOUN can simplify complicated ideas? Wouldn't it be nice if I could have written this six-pyramid explanation?

Let's say that P(n) is the pronoun we want. P(n) means "How many cans it takes to build a pyramid with n cans on the bottom row". Shorthand. OK, now here is the fun thing. We know TWO THINGS about our pronoun - and one thing we don't know - just like real pronouns.

FIRST THING: P(1) is 1. A pyramid with one can on the bottom requires one can.

SECOND THING: For any number bigger than one - call it "SHE" (just to bend the rules) we need THAT MANY cans, and ALSO however many cans it takes to make a pyramid of ONE LESS than "SHE". But we can say it like this:

P(she) = she + P(she-1)

Now, why on earth did I mention "abbr." in my title? Well, "abbr." is the ABBREVIATION for the word "abbreviation". This sounds like a joke, but is really just an instance of what we call a self-referential object. That is, an object which somehow contains itself. Every so often you will see someone on TV standing in front of a TV monitor, which is showing that picture. So on the TV you see (somewhat smaller) a person standing by a TV, and on that TV you see (even smaller) a person standing by a TV, etc... Maybe you have some of those Russian dolls? The big doll opens along its middle, and inside is another doll, very similar, but smaller. It also opens, and inside is another doll...

NOW YOU HAVE BEGUN TO UNDERSTAND WHAT WE CALL RECURSION: a function (or rule, or idea) which somehow contains itself within itself - like the dolls. In real-world computing, we use recursion for certain kinds of work - but we must (repeat MUST) always check to see that we know TWO THINGS, as we saw with our beer-can formula. We must have a "stopping point" (we call it the "terminating condition") which is simply defined. Like the smallest doll without a seam, or the pyramid of one can. And we also have the "recurring" rule, which uses the idea itself on a PORTION of the problem - remember how each time our pyramid is smaller by one? A doll-with-a-seam will have another doll inside. But sooner or later we shall hit our terminating condition - and get our answer. No infinite sea, remember?

Yes, the Beer Can formula which we have given above has a simpler form, in which the recursion has been taken out. It looks like this P(she) = she * (she+1) / 2. You can check this for six, because 6 times 7 divided by 2 is 21.

Ah. Fine. Nice. If you need help, you ought to ask. Because now we're going to ask a very hard question.

What if there is no terminating condition?

In the real world, we hit the limits of physics. If we make a TV picture depend on itself, sooner or later we get down to the resolution of the screen - the "graininess" or the pixels by which the picture is formed. If we make a sound depend on a sound, we usually call that feedback, and end up blowing out the amp. If we apply the idea to any physical idea, sooner or later we get down to something which does not divide - a living thing ends abruptly with cells, a material (chemical) thing with atoms. (We'll defer discussion of the atomic particles for the time being, except to note that whatever THEY are, they are NOT like the gross structures of our world, simply comprised of atoms.)

"But Doctor" - you moan, thoroughly confused and disgusted by the high mathematical jargon I have been spewing - "Is there anything at all Chestertonian in this 'self-referential' idea anyway?"

There sure is - at least two places:

There was a debating-club in Bedford Park, on which I first tried my crude ideas with even cruder rhetoric. It deserved better treatment. It was frightful fun. It was called the "I.D.K."; and an awful seal of secrecy was supposed to attach to the true meaning of the initials. Perhaps the Theosophists did really believe that it meant India's Divine Karma. Possibly the Socialists did interpret it as "Individualists Deserve Kicking". But it was a strict rule of the club that its members should profess ignorance of the meaning of its name; in the manner of the Know-Nothing movement in American politics. The stranger, the mere intruder into the sacred village, would ask, "But what does I.D.K. mean?"; and the initiate was expected to shrug his shoulders and say, "I don't know," in an offhand manner; in the hope that it would not be realised that, in a seeming refusal to reply, he had in fact replied. [GKC, Autobiography CW16:148]

And in "The Loyal Traitor" contained in GKC's Four Faultless Felons, we find "the word is One." While I can point out this has nothing to do with - er - let us say the Prologue of St. John's Gospel, I must, unfortunately, refrain from commenting further, lest I reveal too much of the mystery puzzle of that particular story.

But in mathematics, in the realm of ideas, what happens when we proceed into this strange infinite realm of never-ending recursion? Some kind of computational black hole of never-ending number? Well...

Stay tuned, and next time I will show you. Please stick with me here - the next chapter will give you something fun to do, and a result you can use in your Christmas decorating...