References

1

Jürgen Albert and Karel Culik II, ``A Simple Universal Cellular Automaton and its One-Way and Totalistic Version,'' Complex Systems 1 1-16 (1987).

2

Stan Augarten, Bit by Bit, Ticknor and Fields, New York, 1984 (ISBN 0-89919-302-1).

3

Charles Babbage, Charles Babbage and his Calculating Engines, (Philip and Emily Morrison, eds.), Dover Publications, Inc., New York, 1961.

4

R. C. Backhouse and B. A. Carré, ``Regular Algebra Applied to Path-finding Problems,'' Journal of the Institute of Mathematics and its Applications, 15 161-186 (1975).

5

Carter Bays, ``The game of three dimensional life'' (11/20/86) unpublished (available as a supplement to A. K. Dewdney's February 1987 column).

6

Carter Bays, ``Candidates for the Game of Life in Three Dimensions,'' Complex Systems 1 373-400 (1987).

7

Carter Bays, ``Patterns for Simple Cellular Automata in a Universe of Dense-Packed Spheres,'' Complex Systems 1 853-875 (1987).

8

Carter Bays, ``Classification of Semitotalistic Cellular Automata in Three Dimensions,'' Complex Systems 1 373-400 (1987).

9

Elwyn R. Berlekamp, John H. Conway, and Richard K. Guy, Winning Ways for your Mathematical Plays, Academic Press, 1982 (ISBN 0-12-091152-3) vol. 2, chapter 25.

10

Abraham Berman and Robert J. Plemmons, Nonnegative Matrices in the Mathematical Sciences, Academic Press, New York, 1979 (ISBN 0-12-092250-9).

11

Janusz A. Brzozowski, ``Derivatives of regular expressions,'' Journal of the Association for Computing Machinery 11 481-494 (1964).

12

David J. Buckingham, ``Some facts of life,'' Byte vol. 3, no. 12 (December, 1978), pp. 54-67.

13

Arthur W. Burks (editor), Essays on Cellular Automata, University of Illinois Press, Urbana, 1970.

14

Gerardo Cisneros and Harold V. McIntosh, Notas sobre los lenguajes REC y Convert (Spanish), Universidad Autonoma de Puebla, 1986.

15

E. F. Codd, Cellular Automata, Academic Press, New York, 1968.

16

J. H. Conway, Regular Algebra and Finite Machines, Chapman and Hall, Ltd., London, 1971 (ISBN 412-10620-5).

17

Karel Culick II and Sheng Yu, ``Undecidability of CA Classification Schemes,'' Complex Systems 2 177-190 (1988).

18

Karel Culick II, Jan Pachl, and Sheng Yu, ``On the Limit Sets of Cellular Automata,'' SIAM Journal on Computing 18 831-842 (1989).

19

Predrag Cvitanovic, ``Invariant measurement of strange sets in terms of cycles,'' (preprint).

20

A. K. Dewdney, ``Computer Recreations - Building computers in one dimension sheds light on irreducibly complicated phenomena,'' Scientific American, May 1985, pp. 10-16.

21

A. K. Dewdney, ``Computer Recreations - The game Life acquires some successors in three dimensions,'' Scientific American, February 1987, pp 8-13.

22

A. K. Dewdney, The Armchair Universe, W. H. Freeman and Company, New York, 1988. (ISBN 0-7167-1939-8 pbk)

23

A. K. Dewdney, ``Computer Recreations - A cellular universe of debris, droplets, defects, and demons,'' Scientific American, August 1989, pp 88-91.

24

M. Dresden and D. Wong, ``Life Games and Statistical Models,'' Proceedings of the National Academy of Sciences (U.S.A.) 72 956-960 (1975).

25

Manfred Eigen, ``Abstract: The Hypercycle: A Principle of Natural Self-Organization,'' International Journal of Quantum Chemistry, Quantum Biology Symposium 5 219 (1978).

26

Glen Fleck (Ed.), A Computer Perspective, Harvard University Press, Cambridge, 1973 (ISBN 674-15625-0).

27

F.R. Gantmacher, The Theory of Matrices, volume 2, Chelsea Publishing Company, New York, 1959.

28

Martin Gardner, ``Mathematical Games - The fantastic combinations of John Conway's new solitaire game `life,' '' Scientific American, October 1970, pp. 120-123.

29

Martin Gardner, Wheels, Life, and Other Mathematical Amusements, W. H. Freeman and Company, New York, 1983. (ISBN 0-7167-1589-9 pbk)

30

Herman H. Goldstine, The Computer from Pascal to von Neumann, Princeton University Press, Princeton, 1972 (ISBN 0-691-08104-2).

31

Solomon W. Golomb, Shift Register Sequences, Holden-Day, Inc., San Francisco, 1967.

32

Howard A. Gutowitz, ``Local Structure Theory for Cellular Automata,'' Thesis Rockefeller University, 1987.

33

Howard A. Gutowitz and Jonathan D. Victor, ``Local structure theory in more than one dimension,'' Complex Systems 1 57-68 (1987).

34

Howard A. Gutowitz, Jonathan D. Victor, and Bruce W. Knight, ``Local structure theory for cellular automata,'' Physica 28D 18-48 (1987).

35

Howard A. Gutowitz and Jonathan D. Victor, "Local structure theory: calculation on hexagonal arrays, and interaction of rule and lattice," Journal of Statistical Physics 54 495-514 (1989).

36

Fred Hapgood, ``Let there be Life,'' Omni, vol. 9, no. 7 (April 1987) pp. 40-46, 116-117.

37

Brian Hayes, ``Computer Recreations - The cellular automaton offers a model of the world and a world unto itself,'' Scientific American, March 1984, pp. 10-16.

38

Lyman P Hurd, ``Formal Language Characterizations of Cellular Automaton Limit Sets,'' Complex Systems 1 69-80 (1987).

39

Lyman P. Hurd, ``The Application of Formal Language Theory to the Dynamical Behavior of Cellular Automata,'' Thesis, Princeton University, 1988.

40

Lyman P Hurd, ``The Non-wandering Set of a CA Map,'' Complex Systems 2 549-554 (1988).

41

Erica Jen, ``Global Properties of Cellular Automata,'' Journal of Statistical Physics 43 219-242 (1986).

42

Erica Jen, ``Invariant Strings and Pattern-Recognizing Properties of One-Dimensional Cellular Automata,'' Journal of Statistical Physics 43 243-265 (1986).

43

Erica Jen, ``Scaling of preimages in cellular automata,'' Complex Systems 1 1045-1062 (1987).

44

Erica Jen, ``Cylindrical cellular automata,'' Communications in Mathematical Physics 118 569-590 (1988).

45

S. C. Kleene, "Representation of events in nerve nets and finite automata," in Claude E. Shannon and John McCarthy (editors), Automata Studies, Annals of Mathematics Studies #34, Princeton University Press, Princeton, 1956. (ISBN 0-691-07916-1), pp. 3-41.

46

Christopher G. Langton, ``Self-Reproduction in Cellular Automata,'' Physica 10D 135-144 (1984).

47

Christopher G. Langton, ``Studying artificial life with cellular automata,'' Physica 22D 120-149 (1986).

48

Stephen Levy, Hackers: Heroes of the Computer Revolution, Anchor Press/ Doubleday, Garden City, New York, 1984 (ISBN 0-385-19195-2), chapter 7.

49

O. Martin, A. Odlyzko, and S. Wolfram, ``Algebraic aspects of cellular automata,'' Communications in Mathematical Physics 93 219-258 (1984).

50

W. S. McCulloch and W. Pitts, ``A logical calculus of the ideas immanent in nervous activity,'' Bulletin of Mathematical Biophysics 5 115-133 (1943).

51

Edward F. Moore, ``Machine models of self-reproduction,'' in A. Burks (ed), Essays on Cellular Automata, University of Illinois Press, Urbana, 1970. pp. 186-203.

52

Scott Morris, ``Games - The game of Life,'' Omni, vol. 7, no. 1 (October, 1984), pp. 188-189.

53

John von Neumann, Theory of Self-reproducing Automata (edited and completed by A. W. Burks), University of Illinois Press, 1966.

54

Mark D. Niemiec, ``Life Algorithms,'' Byte vol. 4, no 1 (January, 1979) pp. 90-97.

55

Norman H. Packard and Stephen Wolfram, ``Two-Dimensional Cellular Automata,'' Journal of Statistical Physics 38 901-946 (1985).

56

Kenneth E. Perry, ``Abstract mathematical art,'' Byte, vol. 11, no. 13 (December 1986), pp. 181-192.

57

William Poundstone, The Recursive Universe, William Morrow and Company, New York, 1985 (ISBN 0-688-03975-8).

58

Kendall Preston, Jr., and Michael J. B. Duff, Modern Cellular Automata, Plenum Press, New York, 1984 (ISBN 0-306-41737-5).

59

Anthony Ralston, ``De Bruijn Sequences---A Model Example of the Interaction of Discrete Mathematics and Computer Science,'' Mathematics Magazine 55 131-143 (1982).

60

Brian Randell (Ed.), The Origins of Digital Computers: Selected Papers, Springer Verlag, Berlin, 1973 (ISBN 3-540-06169-X).

61

D. R. Rutherford, Substitutional Analysis, Edinburgh, at the University Press (1948).

62

L.S. Schulman and P.E. Seiden, ``Statistical mechanics of a dynamical system based on Conway's game of Life,'' Journal of Statistical Physics 19 293-314 (1978).

63

Eugene Seneta, Non-Negative Matrices, John Wiley and Sons, New York, 1973 (ISBN 0-470-77605-6).

64

Claude E. Shannon and John McCarthy (editors), Automata Studies, Annals of Mathematics Studies #34, Princeton University Press, Princeton, 1956. (ISBN 0-691-07916-1).

65

Alvy Ray Smith III, ``Simple computation-universal cellular spaces,'' Journal of the Association for Computing Machinery 18 339-353 (1971).

66

Stanislaw Ulam, ``On some mathematical problems connected with patterns of growth of figures,'' in A. Burks (ed.) Essays on Cellular Automata, University of Illinois Press, 1970.

67

Richard S. Varga, Matrix Iterative Analysis, Prentice Hall, Inc, Englewood Cliffs, New Jersey, (1962).

68

Robert T. Wainwright (editor), Lifeline, a quarterly newsletter with 11 issues published between March 1971 and September 1973.

69

W. John Wilbur, David J. Lipman, and Shihab A. Shamma, ``On the prediction of local patterns in cellular automata,'' Physica 19D 397-410 (1986).

70

Stephen Wolfram, ``Statistical mechanics of cellular automata,'' Reviews of Modern Physics 55 601-644 (1983).

71

Stephen Wolfram, ``Universality and complexity in cellular automata,'' Physica 10D 1-35 (1984).

72

Stephen Wolfram, ``Computation theory of cellular automata,'' Communications in Mathematical Physics 96 15-57 (1984).

73

Stephen Wolfram (Ed.), Theory and Applications of Cellular Automata, World Scientific Press, Singapore, 1986 (ISBN 9971-50-124-4 pbk).

74

Takeo Yaku, ``The constructibility of a configuration in a cellular automaton,'' Journal of Computer and System Sciences 7 481-496 (1973).