Just a little more about that secret treasure...

Today we'll finish our little glimpse of automata, those fun games which make computing possible. Of course we have not actually explored the subject, but taken a view of the trails from a lookout. I'm not sure why anyone who likes to read would fear this topic, since the things are so interrelated, but then there are a variety of mental diseases around these days. Speaking of diseases in such discussions, I always like to recall this handy little piece of dialog:

"Well, that's all I can tell you about the new religion," went on Flambeau carelessly. "It claims, of course, that it can cure all physical diseases."
"Can it cure the one spiritual disease?" asked Father Brown, with a serious curiosity.
"And what is the one spiritual disease?" asked Flambeau, smiling.
"Oh, thinking one is quite well," said his friend.
[GKC "The Eye of Apollo" in The Innocence of Father Brown]

In line with this, since we ought to strive for humility even while we are striving to enlarge our knowledge and and wisdom, we must also remember the precision teaching GKC gave on that topic:

Pride consists in a man making his personality the only test, instead of making the truth the test. It is not pride to wish to do well, or even to look well, according to a real test. It is pride to think that a thing looks ill, because it does not look like something characteristic of oneself.
[GKC "If I Only Had One Sermon to Preach" in The Common Man]

The strange thing about automata theory is that it IS characteristic of literature as well as mathematics, since it underlies the whole realm of words and stories - and games - even though it seems to be so intractable a topic...

The principle is this: that in everything worth having, even in every pleasure, there is a point of pain or tedium that must be survived, so that the pleasure may revive and endure. The joy of battle comes after the first fear of death; the joy of reading Virgil comes after the bore of learning him; the glow of the sea-bather comes after the icy shock of the sea bath; and the success of the marriage comes after the failure of the honeymoon. All human vows, laws, and contracts are so many ways of surviving with success this breaking point, this instant of potential surrender.
In everything on this earth that is worth doing, there is a stage when no one would do it, except for necessity or honor.
[GKC WWWTW CW4:69]

Yes, the joy of reading Virgil entails the bore of learning Virgil - which means learning the conjugations and declensions and all that... why then should you refuse the joy of automata? Ah, well - alas, I have no time to make such an intricate argument, especially at this intermediate state of things, so let us proceed.

Last week I said we needed to talk a little more about the game-board. I gave you a little example last time, and as we know, good teachers give examples, and then explain the idea or principle using that example. The problem with giving you almost any example of a Finite State Machine or Automaton - our "game" of last week - is that the example contains many uses of the simple ideas - and they are very simple ideas.

It is the true paradox of such fundamental truths, which is why GKC was so insightful with his "too big to be seen" phrase. For example, when we begin to learn to read we pay lots of attention to the letters and their shapes. We learn them first - but then, as soon as we get started actually reading, we stop paying attention to the letters on their own, and begin to pay attention to how they are arranged - we read words and think about words, not the separate letters comprising each word.

The same thing is true about automata - that is, about the "playing board" for our game. But just like the mysterious method by which letters form words, there is a mystery about the board as well. And now I am going to explain it.

The playing board actually consists of two parts. The first is the "places" where your token may reside. In the actual theory we call these "states". Here we must apply our quote about limitation: there are always a finite number - and that number is fixed - that is, decided upon, and unchanging. You must draw your playing board, and once you've drawn it you must play with it - or discard it and and make another. You aren't allowed to edit your board during play! (Imagine a chess game where one player adds an extra row or column, or a card game where a player comes up with the 13 of ampersands, the 20 of roses, or the senator of clubs! (hee hee) In the real study of automata theory, we call this the "Set of States" - and it is always a finite set. Most often when we do this for real in computing, we simply give each state a number, and call the "starting state" zero - you can call it "Go" if you like, and are willing to risk some sort of copyright infringement. Traditionally, we write states as the letter "q" with an integer as a subscript - perhaps because it begins the Latin word quid, meaning "which" - that is which state we're in. But when we draw these states, we just make circles or ovals, and maybe write their names inside. If you like you can think of them as rooms, rather like that murder game with Mr. Mustard in the Conservatory with the lead pipe... ahem. We'll come back to this idea of rooms shortly. But remember, the set of states is a very simple idea, as simple as the rooms of a house or mansion... it's a real mansion, and it so it has a fixed, definite shape, and finite number of rooms.

The second part of our board is what we'll call "the rules of travel". That is, when you are in any given place (or state, or room), and you take up your next little tile with a symbol on it, you must move based on the possible lines which go out of your room. (Yes, you may end up coming right back to the same place - we permit that, even if it's kind of boring during actual play.) Now here is where we get technical - but just a little. It's not very hard, though.

What is a rule of travel? It simply means that when we are in a certain room and we take up a tile with a certain symbol, we must proceed to another certain room. In the theory we call this the "state transition function": that is given the pair which we'll call "an origin-state and a motion-symbol" there is just one single state which corresponds to that pair. That state is called the "destination state". It's a function, which is just another mathematical object... you know, a fancy kind of box, with smaller boxes inside. We look through them to find one where our given pair is in the left-hand box, and whatever state is in the right-hand box is the one we want.

Yeah, yeah, that's SO technical! you whine. It's not. If I wanted to be technical, I can be, and write

s:Q * A ® Q

which says the same thing and far more tidily. But really, I don't want you to worry about that. I want you instead to think about it like the game board. The "rules of travel" are very simple. All it means is that there are pathways that start in each room, and go to other rooms (or perhaps the same room). Each path has written beside it the characters which permit that path to be taken. So when you play, you take your little tiles one at a time, and you move your token according to the rules. Now, if the game is made correctly, you will always know what to do in every case. In other words, you won't try to move to two places at once, or suddenly find that there isn't any possible path for you to take! You'll cry and moan, and toss the game onto the floor - or, if you're a bit more mature, you'll take it back to the store.

Now, these cases are interesting ones... but here is where I must remind you that this is just an introduction to the topic. If you'd like to know more, you'll have to take a course in Automata Theory. You'll be surprised, since you do NOT need lots of math to deal with it. Nor is it exceedingly complex... at least not for Finite State Automata. Why - because of that self-limitation thing! Hee hee! It's wonderful.

But now for the treasure, which is the really grand part of this.

Every computer that exists, that has existed, or that will exist, is necessarily a finite thing. And that means every computer, and (a fortiori) every conceivable program which runs on such computers, can be represented by this simple little idea called a Finite State Automaton.

As you will learn if you ever take a course in this, these FSA are "well-known". That is, we understand what they do - and what they cannot do. We know them so well we are able to describe them formally using symbols, and explore them... and yet every part of computing, that is or that will be, is contained therein.

You are gagging - you are disgusted with me and this topic. You ought not be. Don't you realize that every possible writing - the Gospels and Chesterton and Marx and Aquinas and Nietzsche and Duhem and Belloc and Hitler and Tolkien, adventures and essays and poems and my own columns - anything and everything, good, bad, dull, instructive, misleading - is constructed from a mere handful of symbols? That does not put a stop to creative writing. You might as well say that God's limiting chemistry to about 100 elements puts a stop to creation!

No... this mystery of limit reveals the parallel truth which we need to ponder, whether we build
automata or mix chemicals or write poems about automata or chemicals - or about poetry:

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

Just for your reference, I will summarize the FSA here, but you may ignore this and go to another site to read about some meaningless sports figure or politician or theologian or playwright.... but remember, as you are using your computer, within it you are depending upon these automata.

A Finite State Automaton is a game (mathematical object)

< A, Q, s:Q*A®Q, q₀, Q_f >

where

1. A is the "alphabet" - a box full of tiles, each engraved with a symbol (like scrabble). Or you can think of these as "motion cards": at each move of the game you take the next one and play it.

2. Q is the "set of states" - the regions on the playing board.

3. s is the "state transition function" - the Rules of Motion. These are the pathways between the regions on the playing board, each of which is governed by some symbol from the alphabet. For any particular "origin state" and any particular symbol in the alphabet, you proceed to the "destination state".

4. q₀ is the starting state - or starting place on the board.

5. Q_f are the "final" or winning states. In order to WIN the game, you must be in one of the WINNING regions when you finish your playing tiles. Otherwise you lose.

And now, since you've been so patient and worked so hard to try to have just a tiny bit of acquaintance with this marvel, I will give you a bonus.

The bonus has to do with the "first" computer game - the real progenitor of just about every video game worth playing. That game is called "ADVENT" (short for "ADVENTURE"). It is a bunch of rooms, and some rooms have treasure, and others have little dwarves which throw knives at you (and sometimes kill you!) and mazes and a pirate and all sorts of other fun things. It had no graphics and was all done by simple text - but it was fun. All modern video games in which you struggle through mazes or complex layers of geography are derived from that game.

BUT...

All of them can easily be reduced to a FSA!!! Yes, think about it: your "states" are the rooms, or locations in the maze. The "state-transition function" is just "rules of travel" - how you may move from place to place. Instead of an alphabet, you yourself are the "input" or playing tiles, since you choose the next move...

Well, what does that mean? It means that in grasping the idea of FSA, you grasp the Ultimate Master Key to all such games. You understand how they exist, and what their underlying structure is... you can in fact write you own games, and you do not even need a computer!

This, of course, is why I said you can make them at home, and they are great gifts... you merely need the discipline and care to make sure you do not build an impossible arrangement.

This, incidentally, gives some insight into plot-design and other topics relating to fiction - and translation:

...no man has ever reproduced the atmosphere and magic of one single word by the use of another word. Nobody could put the exact equivalent of 'revisit thus the glimpses of the moon' into any other English words; and he certainly could not put it into German or Russian or Chinese words. It is this separation that makes necessary such intermediate explanations as these; it may be that the Tower of Babel was indeed the chief tragedy of mankind. But anyhow, it is strictly true that we can translate anything in reason. We cannot translate anything that is beyond reason; like the way in which mere sound and spelling can be a spell.
[GKC Chaucer CW18:317]

I mention translation because one of the three uses of automata is to translate - the other two are generating and recognizing, which we have seen in our example: you win when you recognize a winning pattern. (The changes to make a translator or a generator are trivial, and you might wish to work them out for yourself.)

But I see I am out of time for today, and so I will let you ponder all this until next time.

Remember: with automata theory you are touching the fundamental structure which underlies language itself - and be grateful for this secret treasure!