The FSA - One of the Secret Treasures of Life

Ah, yes - today is the Kalends of July, and also a Thursday. Those of you who are audacious travellers are no doubt busy climbing Sneffels, or, perhaps, already descending into its depths. But I don't know how you could be reading this if you are. Perhaps when you return. Ahem.

Last time I wandered at great length down the middle of the road, trying to suggest an idea about "middle" - and thereby suggest Grammar as a fundamental Problem-Solving Skill. Unfortunately some readers will most likely think I am making a very complex figure of speech from the so-called "Three Ways" (or Trivium) which puts Grammar together with Rhetoric and something else - oh, yeah, Logic - as the first things one ought to learn. Dumb, sir - very dumb. There are other things which must precede these as I shall show... Ahem! But I have no time to debate such trivia today. There are larger things to do, and we ought to be doing them while we can.

Doing what? you ask.

Well - to put it simply, doing automata theory in a Chesterton blogg.

I have been pondering this matter for a little - I've told you I have other things going on, and time seems to vanish past my fingertips - but the thing strikes me as so poetic that I must do it. In fact, the answer struck me as I was searching GKC for a motif-phrase for the next episode of my Saga. I found something, it was quite good, and in fact you can blame it for my resolve to proceed with this topic. Here it is:

"There are two Christian virtues," said Hope with dogmatic emphasis, "the first is unselfishness, and the other is cheerfulness."
[GKC "Wine Of Cana" in CW14:562]

I was told long ago that I think of myself as "God's Gift to Computer Science" - and that is true. We are God's gifts, after all - so we ought to strive to live so as to be worth of that position. But do I keep my knowledge of finite state machines to myself, gloating that I know about them, and YOU don't? Horrors, no! How can I be a Doctor and not teach? (Latin docere = to teach) Or do I find automata dull and boring - and lightyears away from usefulness? Of course not! I like this subject very much, and I wish others to know it and delight in it.

Well - come on, Doctor (you moan) Do you expect the Common Man to prove the Pumping Lemma? Or demonstrate the algorithm to convert a non-deterministic automaton into a deterministic one? No. Hardly. But I told you previously about my friend who said he "knew" 20 or 30 computer languages, and proceeded to list their names. I may be a tech, and only by courtesy a "literary man" since I read GKC. But I know a little about language (English, I mean) and about grammar, and about literature. I can tell the difference between a verb and an essay, or a dependent clause and a metaphor - I even can distinguish a superlative adjective from dramatis personae. If you, O reader, can grasp why Hamlet is not a preposition, and why one cannot conjugate a sonnet, why should you not have a small sense of the far more splendid - and in fact primordial distinctions between sets and variables and functions - or have some insight into the grand device we call a "mathematical object"? Especially when I assure you that all these things are very easy to grasp - simple enough for children to handle, and much less dangerous than certain forms of literature - and that these ideas, as mathematical as they may be, are the strong and elegant foundations - the basement jammed full of utilities - water, heat, lighting and building support - on which most other intellectual work is built.

Oh yes - the Three Ways start in one place - and that place is mathematical. Yet, it is thoroughly literary as well, as you shall see.

Now, my poor distressed and fearful reader, you bring Chesterton against me. I shall quote him for you:

It is certainly time that someone protested, apart altogether from the merits of this particular play, against the absurd assumption which seems to exist in the minds of many people, that any good novel not only may be, but must be, put upon the stage. That a good novel should make a good play is not only rare, it is intrinsically unlikely. If it is a good novel it will probably make a bad play. We should see this at a glance in connection with any other two forms of art. Anybody can see that if a thing is a good sonnet it will probably be a bad song. Anybody can see that if a thing is a good three-volume novel it will probably be a bad epic in twelve books. We all realise that if a thing is a good wall-paper the chances are that it will be a rather loud waistcoat. Nobody proposes to adapt carpets into curtains. Yet all this is in no way more essentially false or foolish than the perpetual assumption that the art of fiction is akin to the art of drama, and that therefore the merits of the former will provide material for the latter.
[GKC ILN June 30 1906 CW27:222-3]

You are right - but I am not doing this. I am not proposing to "mathematize" Hamlet - or Chesterton. I am trying, very poorly, to convey a grand truth from my world by using terms from yours. The Literary Man uses terms to describe and distinguish various kinds of writing and their even more varied components - even though the elements of writing are just a mere handful of things, as simple as the tiles upon a Scrabble Board. But from these profoundly mystical and powerful keys we humans have built so many incredible things - the Psalms, the Divine Comedy, The Phantom Tollbooth - Sherlock Holmes - all made from letters, with a handful of things like punctuation and judicious use of space. A very large part of the art of writing is knowing your medium - your tools. You may not know the name of this pigment or that oddly shaped brush, just as you may not know what a "synecdoche" or a "dependent clause" is - even while you are using them.

That is my point. You can begin to have a basic knowledge of automata - and once you have it, you will begin to see more of even the world of literature.

It will also help immunize you against Stupidity - against claiming powers for a computer which the computer does not have, and cannot have, whether in our present day or at any future time. It will keep you from bringing the wrong measure when you wish to understand something - against applying "reason" to things which are "patterns" or "intelligence" to "computation". You will have some sense of what the computer really is - and it is a very simple thing inside, even though it is large and powerful and useful in some sense, it is small and weak and exceedingly dull in others. Sort of like this:

Who will deny that height, or the appearance of height, is one of the effects of architecture? Who has not read or said or felt that some wall seemed too enormous for any mortals to have made, that some domes seemed to occupy heaven, or that some spire seemed to strike him out of the sky? But who, on the other hand, ever said that his sonnet was printed higher up on the page than somebody else's sonnet? Who ever either praised or disliked a piece of verse according to its vertical longitude? Who ever said, "My sonnet occupied five volumes of the Times, but you should see it pasted all in one piece"? Who ever said, "I have written the tallest triolet on earth"?
[GKC ILN Jul 11 1914 CW30:125]

Did you note the hilarious pons asinorum there? Oh... you didn't. Gosh, and here I thought you were the literary man.

A sonnet is always only 14 lines long, so it's not really possible to have it occupy five volumes of a newspaper. And, in case you didn't know, a pons asinorum is a trick question for some field or specialization which will sound impossibly complex to an outsider but is trivially simple to even a beginner in the field.

So - you see, I am trying to build a very goofy looking simile - and yet it is not goofy at all. Since all our human language is finite, to study Language is to study Automata Theory - and vice versa. And the nice thing is that as you learn more about your own language, you will also learn a little about computers, and begin to realize their proper place in the world.

In order to begin, I must give you some tools. These tools are well-known in my own world, but will probably not make any sense to you literary people. However, you already have very similar tools, and use them constantly - you just don't know they come from my world. Let us start with the very famous little thing called the VARIABLE. Please note I am NOT going to give FORMAL precise statements today. This is just a introduction. We don't lecture on the rhyme schemes of sonnets (versus triolets for example) when we are just beginning to address poetry in the general sense - versus prose, or versus a sentence, or the parts of speech. And with the term "variable" we are at the level of "parts of speech". (Actually I wonder what the generic word is for the other structures within language - what is the general term for "sentence" and "verb" and "essay" and "paragraph" and "phrase" and....? Maybe something like "logoid"? Hmmm, another research problem.)

People get scared with this term "variable" as they get scared with some other words we use. I find it rather sad:

Because I could not bear to make
An Algebraist cry
I gazed with interest at X
And never thought of Why.
[GKC from "True Sympathy or Prevention Of Cruelty To Teachers" CW10:486]

The funny thing about the "variable" in math is this. It has just the same power and use as the word "pronoun" in grammar - and we all know how powerful they are! A pronoun is a name - well, maybe a nickname - for something else. But then that's all WORDS are. "Cow" is not a cow - it is a word that stands for the bovine creature that gives milk, the mystic progenitor of cheese. "It" is an incredibly powerful word, it stands for one thing in one place, and something else in another place - it's tricky that way, even sometimes two different things in the same sentence - but it makes sense when we use it that way. For math people, X is not a number (yes, I know it meant 10 for the Romans!) A variable is like a pronoun: X stands for a number. But for our purposes today, X might also stand for other things - and is far more like a pronoun than the silly term "place-holder" the grade-school teachers use.

Variables, it might be said, are the angelic pronouns. For the pronouns of human language typically vary depending on who is speaking (or writing) - maybe we OUGHT to call them variables, since they vary! I know very little Vietnamese, but I do know that the word for "I" depends on who you are in relation to who you are speaking with: a child calls himself con (son) when he addresses his father, but "anh" (older brother) when he addresses his younger sister - if you don't know the person you call yourself "tôi" (servant), as courtesy demands you honor others - which is why they call the unknown stranger ông (grandfather) or bà (grandmother) regardless of their actual ages, for it is the height of honor to refer to someone as old. (Oh yes.)

A pronoun, after all, is really just a verbal trick of finger-pointing - you indicate who or what you mean by pointing, and we have agreed to let certain sounds (or symbols) stand for the gesture. It permits us to hold onto the things we are talking about - even though the hold is a very loose one. A variable is like a pronoun - it is a way of holding onto something loosely, as if by an angelic glance. And that is the idea I wish you to have. We want to understand that a variable is somehow like a kind of pointer. It points to something. When GKC's Algebraist uses it, as most high school students will grasp, it points to a number. But for us today, it may point to something different.

But what? In order to answer that, we need the second tool. If this "variable" is a kind of pronoun - something that stands for a noun - then we need our box full of nouns. I rather like the word "box" (meaning a carton or container, not the act of fist-fighting) but that isn't the tech term we use. We use one of the most over-loaded words in English - the word "set" - in its sense of "a collection of items". This word "set" has a nasty name, something vaguely despised, almost dated. It is like a "lava lamp" or "tie-dying" or "disco" - people always think of it as "modern" math. But they forget the word "modern" is NOT modern - it was invented in the Middle Ages. And the word "set" is not modern either, even if modern math rather tainted it for too many casual readers. I could try to give a technical explanation but that may be too annoying. Besides, the idea is simple very simple - and you all know what Chesterton said about that sort of thing:

The more simple an idea is, the more it is fertile in variations.
[GKC ILN Dec 14 1907 CW27:607]

You know how some grade school teachers "simplify" the word "variable" to "place-holder". We could "simplify" the word "set" to something even grade school teachers might possibly know: the term "box".

A set is a box. In other words, it's a thing which holds OTHER THINGS.

And these boxes are very awesome boxes. They're like computers - that is, they are MAGIC boxes, because you can produce multiple copies of the things inside them - and do stuff with them.

They are also magic because they can contain the most amazing things. And if you know even a little about computers, you may already grasp this idea - the strange truth that one of the things that a box can contain is ANOTHER box. (In today's computers, a directory can itself contain another directory... but there are other sorts of containing which can go on... er... another time I will tell you a scary secret about this idea, but not today.)

A set is a container for other things, which could themselves be containers. I know that sounds either overwhelmingly simple, or trivially complex - but all you need to think about is moving cartons into which you put several shoeboxes, which contain matchboxes and little candy boxes and stuff like that... Maybe you collect stamps, or tiny shells, or sequins, or pebbles. Or maybe we're talking about one of those COOL Christmas presents like the old "Erector Sets" with lots of metal parts and nuts-and-bolts and wheels and axles and motors - it all came in a really neat box with lots of little indentations where everything fit...

But I have run out of time. I will have to proceed further next time.

Just so you will have a little more to read, I will give you the motivating quote from which I drew today's title. This excerpt will also give you a very good Chestertonian introduction into automata theory - which is really just a very simple and fun game... but I shall let you ponder this until next week.

The ordinary poetic description of the first dreams of life is a description of mere longing for larger and larger horizons. The imagination is supposed to work towards the infinite; though in that sense the infinite is the opposite of the imagination. For the imagination deals with an image. And an image is in its nature a thing that has an outline and, therefore, a limit. Now I will maintain, paradoxical as it may seem, that the child does not desire merely to fall out of the window, or even to fly through the air or to be drowned in the sea. When he wishes to go to other places, they are still places, even if nobody has ever been there. But, in truth, the case is much stronger than that. It is plain on the face of the facts that the child is positively in love with limits. He uses his imagination to invent imaginary limits. The nurse and the governess have never told him that it is his moral duty to step on alternate paving-stones. He deliberately deprives this world of half its paving-stones, in order to exult in a challenge that he has offered to himself. I played that kind of game with myself all over the mats and boards and carpets of the house; and, at the risk of being detained during his Majesty's pleasure, I will admit that I often play it still. In that sense I have constantly tried to cut down the actual space at my disposal; to divide and subdivide, into these happy prisons, the house in which I was quite free to run wild.
And I believe that there is in this psychological freak a truth without which the whole modern world is missing its main opportunity. If we look at the favourite nursery romances, or at least if we have the patience to look at them twice, we shall find that they all really support this view; even when they have largely been accepted as supporting the opposite view. The charm of Robinson Crusoe is not in the fact that he could find his way to a remote island, but in the fact that he could not find any way of getting away from it. It is that fact which gives an intensive interest and excitement to all the things that he had with him on the island; the axe and the parrot and the guns, and the little hoard of grain. The tale of "Treasure Island" is not the record of a vague desire to go on a sea voyage for one's health. It ends where it began; and it began with Stevenson drawing a map of the island, with all the bays and capes cut out as clearly as fretwork. And the eternal interest of the Noah's Ark, considered as a toy, consists in its complete suggestion of compactness and isolation; of creatures so comically remote and fantastic being all locked up in one box; as if Noah had been told to pack up the sun and moon with his luggage. In other words, it is exactly the same game that I have played myself, by piling all the things I wanted on a sofa, and imagining that the carpet around me was the surrounding sea.
This game of self-limitation is one of the secret treasures of life. As it says in the little manuals about such sports, the game is played in several forms. One very good way of playing it is to look at the nearest book-case, and wonder whether you would find sufficient entertainment in that chance collection, even if you had no other books. But always it is dominated by this principle of division and restriction, which begins with the game played by the child with the paving-stones. But I dwell upon it here because it must be understood as something real and rooted, so far as I am concerned, in order that the other views I have offered about these things may make any sort of sense. If anybody chooses to say that I have founded all my social philosophy on the antics of a baby, I am quite satisfied to bow and smile.
[GKC ILN Feb 8 1930 CW35:253-4, emphasis added]

A Postscript:
In case you were wondering, yes - I forgot to explain what "FSA" is. An FSA is a Finite State Automaton - it is the simplest of the kinds of automata, and in the final analysis, the only one which really matters, since we cannot buy infinite amounts of memory. In future columns I will tell you more about the FSA and you'll get to see how much fun they are... they make excellent gifts, and are very inexpensive. And you do NOT need a computer to make them... but you'll have to stop back if you want to know how. It's fun - you'll see.
--Dr. T.