Notes

(1) An introduction to cellular automata in this context, together with many references is given in [1]. Further results are given in [2, 3], and are surveyed in [4, 5].

(2) The notation used here differs slightly from that of [2]. In particular, in [2] is denoted here as .

(3) Also known as general, phrase-structure, and semi-Thue languages.

(4) Compare many implementations of the LISP programming language. Also, compare with models of multiparticle production cascade processes (e.g. [13]).

(5) Although there are some mathematically-defined operations which they cannot perform (as discussed below), it seems likely that the usual class of ``universal computers'' can simulate the behaviour of any physically-realizable system.

(6) This is a form of Godel's theorem, in which the processes of mathematical proof are formalized in the operation of a computer.

(7) Requests for copies of the C language computer program used to obtain these and other results in this paper should be directed to the author.

(8) is related to the generating function for the sequence (e.g. [19, Sect. 1.8]).

(9) The are always Perron numbers [23]. Any Perron number may be obtained from some regular language, and in fact also from some finite complement language [23].

(10) The algorithm essentially involves testing whether a NDFA with states is equivalent to a NDFA that generates the trivial language . This problem is known to be PSPACE-complete [28], and therefore presumably cannot be solved in a time polynomial in .

(11) A more complicated example of this behaviour was given in [33].

(12) This paper concentrates on one-dimensional cellular automata. Such cellular automata potentially correspond most directly with conventional formal languages. Two and higher dimensional cellular automata show some differences. For example the set of configurations obtained after a finite number of time steps in their evolution need not form a regular language and may in fact be nonrecursive [36, 51].

(13) The actual configurations with particular periods may be found by methods analogous to those used in [29] for the complementary problem of determining the temporal periods of configurations with given spatial period.

(14) This is analogous to but distinct from the problem of finding all initial configurations which ultimately evolve to a particular complete final configuration, such as the null configuration (cf. [2, 44, 45]).

previous