8. Sequential and nonsequential evolving algebras

Q: Now I understand what the program of a sequential EA is; it is essentially a finite set of conditional function updates. But I still do not understand what a sequential EA is exactly. Do you identify a sequential EA with its program?

A: It is reasonable to identify sequential EAs and their programs and this is done sometimes [GR]. Often it is convenient, however, to avoid a formal definition. For example, many authors define precisely the language of a first-order theory, the set of theorems, etc. but leave the notion of first-order theory itself informal.

Q: What do you gain by leaving the notion of sequential EAs informal?

A: Usually, constructing an EA for a given algorithm F involves more than just writing a program. You indicate a class of static structures which includes presumably the presentations of all possible or all relevant states of F . You may want also to indicate a class of initial static structures. See for example how Turing machines are formalized above. It may be convenient to view all that as a part of the definition of the EA.

Q: What non-basic rules are most common?

A: Most common is the generalization of basic rules where the terms are allowed to have free individual variables. This generalization is used even in the sequential case (as a syntactic sugar) to make the program more succinct [BRo1 and BRo2], but it is indispensable in the case of unbounded parallelism. Consider, for example, a tree algorithm that colors red - in one step - all children of the currently active node whenever the active node is green. This may be expressed by the rule

if Color(C) = green and x is a child of C then
   Color(x) := red
endif

which is not equivalent to any (finite) set of basic rules. In the paper on Occam, we used (limited) universal quantification [GMs, BRi1]. To show why one may need universal quantification, let us suppose that the tree algorithm, mentioned above, colors the active node C green if all children of C are red. This may be expressed by the rule

if ( child x of C)(Color(x) = red) then
   Color(C) := green
endif

Q: You mentioned asynchronous distributed computing a while ago. I have been wondering; how do you deal with such computations? It seems that going from one state to another is a basis of the EA approach. In the case of a distributed asynchronous computation, it may be unclear what the states are.

A: Syntactically, an evolving algebra for a distributed asynchronous algorithm may look like one that works in (discrete) sequential time. The difference is in the definition of a run. Instead of one demon, you may have a multitude of demons responsible for different rules. Whenever conditions are right, demons perform the required changes, but some demons may work with lightning speed whereas some others may be lazy. Let me again refer you to the paper [GMs] with Larry Moss on the programming language Occam. By the way, the sequential interpretation and the parallel interpretation of a list of commands coexist in Occam as well as in Parlog. This is one way to generalize the basic language of transition rules.

Q: Can one compose evolving algebras?

A: Of course [GR], but this is a topic for another conversation.

Acknowledgement. The EA project would probably die without the active participation of Egon Börger. I benefited greatly from the collaboration with Andreas Blass, Larry Moss and Dean Rosenzweig. The strcpy example was ``lifted'' from Jim Huggins' homework for the Principles of Programming Languages class. I am very greatful to Bob Blakley, Erich Grädel, Angelica Kappel, Gerti Kappel, Anatol Slissenko, Ed Wimmers and Moshe Vardi for their comments.