Tuesday, September 26, 2006

IFIP WG2.2 40th Anniversary Meeting (2): State Machines

Lamport and Boerger in their talks emphasized State machines.
I have a problem with the name.

Systems have two aspects: perhaps the simplest model of a system is a graph; that is, it consists of states (vertices, points, being) and transitions (actions, processes, edges, motions, becoming).

To concentrate on one of these is a mistake. It is somehow related to the classical view that mathematics is about sets (ZF), rather than the idea that sets *and* functions are primitive (Lawvere).

Of course functions may be thought of particular sets, just as memory allows actions to be stored as states, but not to regard functions and actions as primary is to distort the theory.

In principle, systems interact sequentially through states, and in parallel through actions.

I don't know why the name *automaton* has been abandoned - seems to be historical, and neutral with respect to states and actions. It should be rescued from the overstrict use by classical language theorists.

Further thoughts (16 October 2006) The usual meaning of a program to a programmer is that statements of a program are commands, i.e. actions or processes, and between the commands are states, often not represented explicitly. This point of view means that a program is a composition (in an approprate algebra) of basic programs; i.e. the program text is an expression, in an algebra of programs.

On the other hand, functional programming, and process algebras, take the program text to be state.

It is clearly correct to consider programs which have as part of their state text, plans, programs, specifications etc. For example the DNA in a human cell is a plan for the development of the cell. In fact one would expect most programs to have an internal model of themselves as state.

However it seems to me of fundamental importance to separate program as state from program as a composition (expression) of processes.



Post a Comment

<< Home