new books and old articles (3)

Date: Fri, 5 Apr 1996 22:23:27
To: ca@think.com

The paper

   G.A. Hedlund,
   "Endomorphisms and Automorphisms of the Shift Dynamical System," 
   Mathematical Systems Theory 4 320-375 (1969).

is frequently cited in the celular automaton literature in spite of the fact that it is a topological article culminating a long series of investigations arising out of celestial mechanics and differential equation theory. The reason for this is that the central object of discussion - continuous maps of symbolic sequences - turns out to coincide exactly with cellular automata; moreover the discussion of endomprphisms and automorphisms resolves many of the questions which could be asked about reversible automata. Similarly not emphasized in the paper, there is a significant overlap with mathematical communication theory. Indeed the whole article reflects an austerity and style of mathematical exposition characteristic of the author.

Over fifty pages in length, the paper is divided into twenty sections, each one of which could be the subject of a day or two of study in a seminar. At that, a background in topology and real analysis is required; given the origins of the subject it is not surprising that there is a heavy emphasis on the topology of the real numbers, sometimes obscuring differences between that topology and the topology of sequences.

For cellular automata theory, this style of argument has two consequences. The first is that a cleaner separation between topology and the combinatorial arguments, as the author describes them, might have made the presentation more understandable. The second is an overwhelming emphasis on periodicity and varying degrees of near periodicity which are of minor concern for automata therory. This would be a greater annoyance were it not for the fact that later on, if iteration of the automaton's evolution operator replaces or supplements the shift operator, such aspects assume a much greater importance.

For all the article's detail, three of its theorems contain the essence of its applicability to cellular automata theory:

After working up from local maps to the one-sided shift to the two-sided shift, Theorem 3.4 (Curtis, Hedlund, Lyndon) asserts that continuous, shift-commuting maps of the full shift are none other than the evolutionary rules of cellular automata.

The fundamental result is Theorem 5.4, which equates surjectivity with uniform (and finite) multiplicity. The theorem requires careful understanding, to know how the accounting can change while passing from the local map to the global map.

Following some ideas attributed to L. R. Welch, Theorem 14.9 reveals which sheep have strayed from the fold and where they have gone. The indices L, M, and R carry this information, moreover are multiplicative under composition, and have a bearing on which automata are reversible. Perhaps these results have not been applied to automata theory as much as they should be.

Naturally the article consists of much more than the three theorems mentioned. Some idea of its organization and orientation can be seen from the sequence of section headings:

Introduction

definitions, antecedents, overview (2 pages)

Bisequence Space and the Shift Dynamical System

basic definitions (1/2 page)

Subdynamical Systems of (X(S),sigma) and their Characterization

more definitions and their topological implications (1 page)

A Class of Mappings which Commute with the Shift

The section in which a construction that can be seen as equivalent to defining a cellular automaton is introduced; in three stages it produces the shift-commiting continuous functions.

1) the local map

2) right-extended to one-sided sequences

3) left translated to encompass two-sided sequences.

Giving each of these three stages their due creates gives a not insignificant complexity to treatments of the Shift. (2 pages)

Properties of F[infinity](S,1)

Several details concerning permutations, the uncountable multiplicity of counterimages, and restrictions for automata of neighborhood-length 1. (1 page)

Multiplicities of the Mappings f[m] and f[infinity]

various results on the cardinalities of counterimages including the finiteness-and-uniform-multiplicity theorem for surjective mappings (endomorphisms).

(6 pages)

Existence Theorems for the Classes A(S), E(S), and Phi(S)

existence and strict inclusion running from automorphism through endomprohism to simple continuity is established by examples. (6 pages)

Classification of Points of (X(S),sigma)

a classification, charasteristic of symbolic dynamics, of periodicities and near periodicities (4 pages)

Invariance of Properties of (X(S),sigma) under phi in Phi(S) and under phi inverse.

the behavior of this menangerie with respect to image and counterimage (3 pages)

A Fundamental Property of Inverses

this section is developed without the use of de Bruijn diagrams and their pair diagrams, so it establishes by topology and the examination of counterimages the requirement that paths outside the diagonal of the pair diagram should remain there.

(4 pages)

Inverse [sic] of Recurrent Points are (n-1)-Separated

the preceding section takes account of recurrency. (3 pages)

Almost all Points Have the Same Number of Inverses

before stage (1) reaches stage (2), and before limits have been taken, uniform multiplicity prevails. (2 1/2 pages)

Invariance of Properties under phi inverse When phi in E(S)

taking the limit loses (or coalesces) some counterimages, but this varies according to periodicity or recurrence properties (4 pages)

Compositions

definition and properties of composites (1 page)

Maximal Compatible Extensions

The mechanism by which multiplicity may be lost, examined in detail but with the benefit of neither the de bruijn nor the subset diagram. Welch's indices.

(4 1/2 pages)

L(fg) = L(f)L(g) and R(fg) = R(f)R(g)

the indices are multiplicative by composition (1 page)

Cross-Sections of the Mappings f[infinity]

how to avoid losing multiplicity, in very topological terms. (6 pages)

Converse of Theorem 6.7

keeping the full multiplicity (1 page)

Roots of Powers of the Shift

an application of the index theorem (1 page)

Polynomial Mappings

defining mappings by polynomials in Z/(prime) (1 page)

Another Property of the Groups A(S) and A(S)/Sigma(S)

the author emphasizes the complexity of the automorphism group of the shift (two elements whose product is of infinite order, as well as containing all permutation groups). (1 1/2 pages)

Bibliography of 28 items

In summary, we have a very long and detailled article, with results of basic importance for cellular automata theory as well as the Shift Dynamical Systems to which it is addressed. Topology is thoroughly interwoven with the presentation, which nevertheless ought to be separable, leaving results derived strictly from automata concepts. The next article to be reviewd, by Nasu, accomplishes this to a great extent.

The article has its small quota of misprints but mercifully, they do not mislead, as such blemishes often do.