Let's Play a Game: FSA were made for Man...

I had debated today's topic several times since last week - especially because yesterday was the Nones of July, and that is a very special day for me and a major day in the Saga I am writing... but I must not tease you with that. Also (speaking of Sagas) last evening I watched a movie called "National Treasure" which had some hilarious moments besides some goofy distortions of history and physics... so perhaps maybe there is hope even for my Saga, which distorts geography as well. Mine has some cool hidden treasures too, and very difficult cyphers - and even more awesome history to go with my distorted geography. Ahem.

Having brought up geography, let us therefore resume my distorted literary presentation of automata theory in a Chestertonian style. This may sound like a game - but then it is a game. Most of us know a fair number of games - let us ignore typical sports for the time being, and stick with what are typically called "board games". As I was saying, one of the delights of a childhood Christmas is to receive a new game. You open it - there's the usual board which you unfold and put on the table (after your mom yells to tidy it up first!) Underneath the board is a funny little container, probably plastic, with the various parts in their compartments - and the all-critical instruction book. One or two games might have come with something out of the ordinary - a little egg-timer, perhaps, or something with a spring you wound up, or maybe it needed two batteries. But most of the time there were these things: the board, and the instructions, and the parts - and finally the thing that made it a GAME and not something else: THE PLAYERS. Here, a certain famous line pops into my head - "Tennis was made for Man and not Man for Tennis." [GKC The Thing CW3:168] In other words, there was something which made the game live - the Latins called that the anima or soul. In our modern computer game world, the word "animation" is used to signify that something is in motion. We'll talk about that more in a bit. But for now I want to call your attention as a Chestertonian to something larger.

It is, as I delight in recalling for you, something "too big to be noticed" [See "The Three Tools of Death" in The Innocence of Father Brown.] You may recall that last week I said how the mystery of the box as a container (we tech people call this "set theory") was merely the very curious idea that there is no reason why a "container" cannot contain OTHER containers! And so it is. In our particular idea of some general board game, we have a box - the one you found underneath the Christmas tree and unwrapped and pried open. But within that box we had at least one smaller "box" - perhaps the playing tokens, maybe money or dice or other items used in the game.

But this is not just a box - as if it were a trunk, or perhaps a suitcase. It is (as the Scholastics would phrase it) a thing-in-itself. Granted, it is a complex of simpler items. But the box, as it came to you under the Christmas tree and unwrapped, is a Whole Game. (We ignore for today the possibility that it was defective from the factory, another day we can consider this interesting case, which alters my larger topic from a Scientific into an Engineering Matter.)

Since I am trying to lecture you about something called the Finite State Automaton, which is NOT a Board Game (though it could be, as you will eventually learn), you will want to know what the correct word is for this very special sort of container. Yes, it is a "set" just as your board game is a "box" - but it is a special sort of set, because it contains an organized collection of things. Other experts might use other terms, but I will use the term "mathematical object" - that is nothing more than an organized collection of things. This idea is very simple - just think back to some Christmas gift, of some board game with lots of components - or even one of those awesome "art kits" with all sorts of stuff, all nestled in their little plastic depressions in the box. You have the sense that the box contains an arrangement of items, but they are organized. What a wonderful word!

Why is this word so wonderful? What is the mystery of "organization"? Is it simply a synonym for "order"? Well - no. There's something else added. It's another one of those Greek roots - "erg" - which means work or deed or action. The arrangement is made for the sake of DOING something. This sense is very powerful, and is one of the hidden delights of such diverse things as an orderly kitchen, or workshop, or the glory of the board game or art kit when first opened... everything is there, waiting to be used - to be worked with.

Now, at last, we have our various ideas - all except the last one. If this thing, this finite state automaton, is meant to be worked with, what is it we're going to accomplish when we work it?

Ah. This is the very famous question, another from the depths of the Middle Ages, which I myself learned from my mother: dic cur hic = "tell why you're here". Why do this? What is the Purpose?


We can just as readily ask what is the purpose of a board game - and the simple kid's answer is "to have fun" - but there is a simpler one, which exists at the level of the game, and not at the level of the child. Which is why some kids passionately hate board games, or sports - I think of the famous comic "Calvin" who detested the real game of baseball and favored his variants with 12th base or where the outfielder may tackle the goalie... such correctives would do much to ameliorate the corruption in our world... Ahem. But let us proceed. The point is that the "reason" for the game (to be distinguished from "the reason for John or Sally playing the game") is to find out who wins. And the finite state automaton has the very same reason: it is a device arranged to find out who wins.

This is no mere entertainment - or if it is, then all human actions are entertainment, and we might as well change our species from Homo sapiens (Man, the wise) to be Homo ludens (Man, the player). Sure, we can say this by some awkward analogy: An engineer works to design a bridge to "win" - that is, he wins if it stays up. I think of the fabulous Brooklyn Bridge in New York, opened in 1883, or the even more amazing Roman bridges built about two millennia ago. In order to play that game of Bridge (which is not played with 52 cards and a dummy) you need to know a lot about phsyics and materials and design and things like that - it's not an easy game to play. So let us take something far simpler - an example which you encounter from time to time when you use a computer. You are, let us say, need to tell the computer how many copies of this column you wish to print. There is a little box where you may type the quantity. This is a nice little game, perhaps too simple for you to bother with - but someone needs to bother with it. The milk in your refrigerator had to come from a cow - and someone needed to know about cows for you to get it. In the same way, someone needs to know how to play this very simple little game called "You win if you type in a valid number". Granted, you need to know what makes a "valid" number - but this is lots easier than deciding what makes a valid bridge. Or even a valid cow.

So. Here's our game - the "Valid Number Game". It comes in a box, and we unpack it. What's inside?

Oh boy oh boy!

Let's see. There's a playing board...

And there are a stack of tiles, just like those in Scrabble, but there are all the characters on your computer keyboard, the ampersand and F12 and stuff like that. There is your playing piece... I will let that up to your imagination. Then there's this little instruction book.

1. Draw a series of tiles - choose as many as you like - and put them in a row in front of you face down.

2. Place your playing piece on the blue-ringed starting location labelled "Start".

3. When it is your turn, take the leftmost tile from your row, and turn it over. Depending on what that character is, move to the correct location on the board. You must move your playing piece along the track that leads away from your current location, depending on the tile in play - and leave your piece in the new location as the track may direct. It may happen that you will not move from your present location; this is permissible, but only when there is such a track. After you have moved, you must discard that tile; your row will now be one tile shorter than it had been.

4. When you have no more tiles in your row, you WIN if you are in a green circle, you LOSE if you are in any other color.

And that's all. What a nice little game. It's very kindergarten, yes, of course it is. But we can make it lots more complicated... but not just now.

Instead, let's see what we have in our game box.
(1) a playing board
(2) a bunch of tiles with various symbols on them.
(3) a rule-book
(4) a place to start
(5) and places to win

We shall have to talk more - especially about that playing board - but not today.

You might try playing this yourself - you'll have to make your own tiles, but like Chesterton's Gype, the whole point is that you do it yourself. It's anti-Chestertonian to "buy" such a thing. Which is another reason why automata are so Chestertonian - they are so easy, it is silly to buy them... you might want some assistance if you have a really big one to build, but that's different. Not even the great master-builder John Roebling tried to span the East River by himself.

Hey. If you think all this is not Chestertonian, here are a few quotes which may help out:


"What is the shortest journey from one place to the same place?"
["Homesick at Home" in TCL; also CW14:64

The object of a street is to lead from one place to another...
[GKC NNH CW6:321]


...it is the definition of a story that it ends differently; that it begins in one place and ends in another.
[GKC TEM CW2:378]

For my part, I think it rather more foolish merely to rush from one place to another and back again, and pay money for wind (not to mention dust) than to pay money for wine, with its not quite extinct accompaniment of wit.
[GKC Sidelights CW21:491]


People go from one place to another place; but not from one place to another place on the road to everywhere else.
[GKC Appreciations and Criticisms of the Works of Charles Dickens CW15:344]

The story begins in one place and ends in another place, and there is no real connection between the beginning and the end except a biographical connection.
[ibid]