Thursday, October 18, 2007

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...

9 comments:

  1. Dear Dr. Thursday,

    If my question makes sense maybe i understood some of what you said.

    Is this subject in anyway analogical to "deja vu all over again, but somewhat attenuated with each "re-occurance"?"

    richard, looking for a linguistic liniment to unstrain my brain...
    ;-)

    ReplyDelete
  2. Dear Dr. Thursday,

    If my question makes sense maybe i understood some of what you said.

    Is this subject in anyway analogical to "deja vu all over again, but somewhat attenuated with each "re-occurance"?"

    richard, looking for a linguistic liniment to unstrain my brain...
    ;-)

    ReplyDelete
  3. Thanks, Richard - yes, that's a nice slangy way of putting it. There are many other ways of coming at the idea - "nesting" or repetition is used in certain forms of art or music, though usually of a "simple" character... otherwise the pattern would get lost. And for the moment I am trying to explain an idea, so that we can look at something quite a bit more complex, yet having a pattern. Concentrate on the dolls - keeping the idea that while you are unpacking them, you really do not know HOW MANY MORE there really are. Another point which is not so easy to tell about is the idea that when you open a doll you would find two inside, both with seams, and so on... again the idea is NOT to look at the repetition, but the scheme by which the pattern repeats (e.g. when a doll has a seam, you open it, and deal with what's inside.) That' all I want for now. Next time we'll take a real example you can try at home.

    Another example in words, which I was going to use (but did not) in my book on Subsidiarity is the children's ditty "The House that Jack Built", where each successive verse contains the preceding ones (we're then going from little to big). Again note that the verse is made by sticking on clauses ("THat beat the dog, THAT barked at the cat, THAT chased the rat, THAT ate the malt") to an ever-growing sentence THAT Jack built. Hee hee.

    But as I think of it, "deja vu all over again" is perhaps a handy "literary" parallel one might use to model recursion... sort of a verbal (or numerical) "Groundhog Day" - though that is far closer to another, rather different kind of computing problem (What we call "Newton's method" is one - er - approximation, hee hee.)

    Some of this does just sound like a fancy form of repetition - which is in some sense all that recursion is. Remember that I am purposely omitting the REAL (theoretical) stuff. I do give it away in the line "P(she)=she+P(she-1)" but we are not going into that at all. The stuff that comes next week is more like the repetition of baking cookies, but a kind of nightmarish form, where each time you take a tray out of the oven, instead of having (say) a dozen finished cookies, you have 12 trays of unbaked cookies to be put back...

    If you or some reader cares to concoct a "recursive" story or other literary work, I will be very interested in reading it... if I have time. Hee hee.

    thanks, Richard!

    --Dr. Thursday

    PS I forgot! Actually there IS a recursive book, which is one of my favourites. It is Michael Ende's The Neverending Story. I cannot explain further without spoiling it - but you ought to read it, it's great. (N.B. but NOT the movies which are only loosely based on the book.)

    ReplyDelete
  4. Did you merely post twice, or is that a recursive example of a comment? Hee hee. Good one!

    --Dr. T.

    ReplyDelete
  5. Because the idea is so important to what comes next, I will give yet another example: "How to eat soup recursively" (I'll assume you have your own spoon.)

    * * * *

    To Eat a Bowl of Soup:

    You are given a bowl containing some soup.

    If there is just one spoonful of soup in the bowl, swallow that. You are done.

    Otherwise, take out ONE spoonful of soup, and swallow that. Then Eat the Bowl of Soup [that remains].

    * * * *

    You see, the instructions USE the instructions.

    --Dr. T.

    ReplyDelete
  6. Bottles of shampoo often carry instructions ending with the words 'rinse and repeat.' Followed literally, these instructions would oblige the user to shampoo his hair over and over again without ever stopping. (A ploy by the marketing division to boost sales?)

    ReplyDelete
  7. OK, Thursday, I'm not sure what you're driving at. Are you being recursive or merely discursive in your discourse?

    C. S. Lewis pointed out that one of the big differences between men and women is that women often have no antecedents for their pronouns. How often my wife is in the other room and says to me, "What should I do with this?" I am usually tempted to reply, "Put it there."

    There was a word problem in an Old Farmer's Almanac that used to keep me up nights. It went like this ... The addresses of the houses to the left of Jack's house total the addresses of the houses to the right of his house. What is Jack's address and how many houses are on his street?

    I assumed that the writers of this puzzle wanted us to assume that the houses on Jack's street were all numbered with consecutive positive integers and were not all even on one side and all odd on the other; I assumed this just to simplify the problem. However, once the first answer, "Jack's house is #6 and there are 8 houses on the block [1 through 5 totalling 15 and 7 plus 8 totalling 15)" rolled out, it became obvious that there were, indeed, infinite answers to this problem. I once figured out the next two answers. I don't recall them, but it's something like, "Jack's house is 35 and there are 49 houses on the street," and "Jack's house is 1156 and there are 1260 houses on the street", or something like that.

    These are of course factorial problems, or triangular / pyramid problems. But I couldn't for the life of me figure the pattern that could be used to determine the infinite answers. What was the formula?

    That's the amazing thing about formulas or pronouns, they apply adequately to so many different things, and they fit the pattern!

    And of course, there's Zeno's Paradox (I believe it's called), the conundrum that you can never get anywhere because to get from point A to point B you have to first hit A.5, and to get to A.5, you have to first get to A.25, and so on. Therefore there has to be a doll with no seam. If the recursion were limitless, we'd never be able to bridge the gap between particles and waves, between the pattern and the formula that contains it, between the shackled reason of the madman and the unfettered reason of the poet.

    Is THIS what you're driving at????

    ReplyDelete
  8. By the way ... "Jack's Address" problem is a problem of "squaring the triangle".

    If a number factorial has a whole square root, then that square root is the answer to the address problem. (8! = 36 / Jack's street has 8 houses, and his is #6, the square root of 36. Likewise 49! = 1225. Jack's street has 49 houses, and his is #35, the square root of 1225). But the pattern of when a factorial has a whole square root is indecipherable. The dolls that are inside the other dolls are odd and appear at unusual intervals, they are SURPRISING.

    A factorial with a whole square root is, indeed, a triangle that can become a square.

    ReplyDelete
  9. Oh, my. I did not really intend this go delve that deep into number theory and its delights... it's like a snack, it's tasty, and it makes you want to eat more, but it only goes so far... though God knows I rely on number theory at work, as most of us do, even if we don't really know it!

    Ahem. Just a quick correction. You don't mean factorial. You mean the sum from one to n of the integers. Factorial is the product.

    Now, there are whole realms of puzzles (actually, real problems) which have "infinite" answers. They often come up as such little thought puzzles as you indicated. One branch of such things is called "Diophantine Equations" in which all the numbers must be whole (integers). Your house-numbering puzzle is indeed such an equation, for it is the solution for m and k positive integers where

    (m-1)m/2 = km+k(k+1)/2

    using the non-recursive formula for the beer-can pyramid I gave in the original posting. (Jack lives at m, there are m+k houses.)

    But it is rather clever of you to point out that this is INDEED a case of "squaring the triangle"... you ought to send that in. (Where, I do not know, but you ought to. Hee hee)

    Yes, Zeno - and his paradox. This is of course the place where the famous rebuttal comes in:

    Zeno posits: "Since (his argument about the infinite number of halfway points omitted), motion is NOT possible. Shall we discuss it?"
    Scholastic rebuts: "Solvitur ambulando."

    Hee hee. That is, he replies "Let it be solved walking." You can read the Latin as "while walking" or "by walking"... It is of course the case we shall see tomorrow, when we cross the infinite sea without going mad.... since (1) it's not infinite and (2) you're holding tight to a poetic view of things and of course (3) you have a sense of humor.

    It will be fun; now I have a day's work ahead of me, and then I must prepare the posting... please have with you a good-size piece of plain white paper, a ruler, a pencil (and eraser), and preferably a compass (the circle-drawing kind, not the north-pointing kind)... That is, if you wish to try it yourself - butI'm NOT crossing any infinite sea without my trusty compass! hee hee

    --Dr. Thursday

    ReplyDelete

Join our FaceBook fan page today!