Home -> 
Solitarywaves -> 
State Machines

Rock Garden, Ryoan-ji: japan-guide.com


State Machines
A Statistical Interpretation of Mechanism

Alan Bawden's paper "Analyzing the State Behavior of Programs" [1], is a foundational building block.

The following statement by Alan Bawden resonates with me because of how essential I found state behavior to be in building basic neural networks.

It cannot be the case that state is an attribute possessed by an object independent of its observer.

This statement reflects the fact that the state attributes inside of a machine (or the mechanics of a mechanism) is dependent on the interaction of all its component parts. At the micro-level, you could treat components inside a machine as an assembly which depends on each other, and describe the interactions in this machine using statistical mechanics.

Alan Bawdens's working paper [1] is fun to read on two levels: first, it is fundamental or basic theory, and second, it's what I call cultural or mythic references. Both levels are embedded with truth. This is the kind of paper that inspires me because it's filled with deep foundational information; enough to fill a collection of books. So I'm now going to go off on the second path. The first path I think about when I'm writing code.

A fundamental methodology I believe we need to apply to understand our world is to describe it using a language. Knowing something or having the knowledge to understand something requires us to descibe it using a language or grammar. The more complex the mechanism is, the more complex the grammar to describe it must be.

The basic methodology used in building a computer language is using rewriting lists or expressions. Many modern functional programming languages are built upon a rewriting system (also referred to as a terminal rewriting system, graph rewriting system or production system). The venerable programming language Lisp is built upon rewriting lists. Newer pure functional programming languages uses graph reduction [2] (called the S-K reduction machine) to implement function calls which leads to removing function variables, and hence side effects. It's amazing how far we can go in applying symbolic rewriting methods to describing our world. [3]

Nature also uses a kind of rewriting process to build complex systems. What complex system you say. Of course it's the animal inhabitants of our world. Human beings and the other animal life are embedded with the most varied internal rewriting "language" on the earth. A fundamental rewriting system is expressed through the DNA molecule. The neurons in our brain assemble our thoughts using terminal rewriting circuits inside neural tree structures.

This language using rewriting processes goes all the way down from complex biological organisms to atoms. The explosion into complexity starts at the entropic micro-states at the edge of the physical vaccum. The simple hydrogen atoms are congealed into heavier atoms inside stars by the pressure of gravity.

Erwin Schrodinger [4] in chapter 6 of his book "What is Life?" presents a discussion of entropy. Especially note his remarks on what is call "negative" entropy which is about the origin of order. His book was written in 1944, but is as modern as if it was written just yesterday.

I'm now going to end this article by mentioning the theologian Pierre Teilhard de Chardin. He had a beautiful vision called the Omega point. In some sense, the Omega point is God. You have to smile at such an optimistic and wonderful idea.

[1] Alan Bawden, Analyzing the State Behavior of Programs, August 1988, MIT AI Lab working paper 311.

[2] David Turner, A New Implementation Technique for Applicative Languages, Software-Practice and Experience, Vol. 9, 31-49 (1979)

[3] A spectacular example of rewriting is a Lindenmayer system (L-system). If you wanted to paint a tree using a computer you'd use L-systems with simple recursive tree-structured algorithms. Using simple "production" rules with 2, 3 or 5 branches generates beautiful trees. In the art of bonsai, the black pine is characterized as generating its leaves or needles using a binary branch. Accordingly, in bonsai, the ponderosa pine generates its needles using a ternary structure, and the white pine generates its leaves using a quinary branch.
The Algorithmic Beauty of Plants

[4] Erwin Schrodinger, What is Life?, 1944