Next: Contents Previous: Papers

Linear Cellular Automata

Harold V. McIntosh
Universidad Autonoma de Puebla
Apartado Postal 461
(72000) Puebla, Puebla, MEXICO
Email:mcintosh@servidor.unam.mx

May 20, 1987
revised August 10, 1990

• Contents
• History
  • Early origins
  • Automata theory
  • The Gardner era
  • The Wolfram era
  • One dimensional automata
  • The vocabulary of automata theory
  • Probability theory
  • Graph theory and de Bruijn diagrams
  • Reversible automata
• What to look for
  • General characteristics
  • Cycles
  • Periods
  • Ancestors
  • Subautomata
  • Factor automata
  • Product automata
  • Automata with memory
  • Idempotent rules
  • Membranes and macrocells
  • Totalistic rules
  • Two-cell neighborhoods
  • Blocking transformations
  • Tailor made automata
• Cycles in space
  • Cycles in Life
  • Evolution for Rule 22 - one dimensional Life
  • Evolutionary diagrams and matrices
  • Evolution of a seven-cell ring
  • Cycles for a sixteen-member ring
    • Quiescent ring
    • Period 14
    • Period 12, 6 phases
    • Period 12, 12 phases
    • period 6
    • Period 4
    • Period 2
    • Period 1 (still life)
  • Cycles for Rule 22
  • The evolution matrix
  • The reduced evolution matrix
• Periods in time
  • Characteristics of cycles
  • Overlapping of neighborhoods
  • The de Bruijn matrix
    • B1
    • B2
    • B3
    • as product and sum
  • Periods and other properties
  • Superluminal configurations for Rule 22
  • Periods for Rule 22
  • The gap theorems
• The Garden of Eden
  • The subset construction
  • Excluded states for Rule 22
  • Symbolic equations
  • Arden's lemma
  • The use of symbolic equations
  • Systems of symbolic equations
  • Ancestorless states for Rule 18
  • Factors
• The calculus of regular expressions
  • Derivatives
  • Ideals and factors
  • Rule 18
  • Factors for Rule 18
  • A geometrical representation
• Probabilistic de Bruijn matrix
  • Block probabilities
  • Kolmogorov conditions in matrix form
  • Probabilistic de Bruijn matrix
  • Some properties of n-block probabilities
  • Some simple examples
  • Determinant and inverse
  • Characteristic equation
    • merged product
    • trace
    • second coefficient
    • principal minors
    • determinant
  • Correlations
• Probabilistic evolution matrix
  • Regularities and anomalies
  • Mean field theory
  • More refined theories
  • Local structure theory
  • Hartree-Fock approach
  • Kolmogorov consistency conditions
  • The vector subset diagram
  • Estimating the number of ancestors
  • Trivial solutions
• Positive matrices
  • Gerschgorin's disks
  • Eigenvalues on the boundary
  • Minimax principle
  • Largest eigenvalue
  • Second largest eigenvalue
  • Averaging and convergence
  • Non-negative matrices
• Zeta function
  • Counting loops
  • Traces, ,
  • Infinite de Bruijn matrix
  • Cluster expansion
  • Reduced evolution matrix
• Cycles for Rule 22
  • Summary
  • N = 1
  • N = 2
  • N = 3
  • N = 4
  • N = 5
  • N = 6
  • N = 7
  • N = 8
  • N = 9
  • N = 10
  • N = 11
  • N = 12
  • N = 13
  • N = 14
  • N = 15
  • N = 16
  • N = 17
  • N = 18
  • N = 19
  • N = 20
  • N = 21
  • N = 22
  • N = 23
  • N = 24
  • N = 25
  • N = 26
  • N = 27
  • N = 28
  • N = 29
  • N = 30
  • N = 31
  • N = 32
  • N = 33
  • N = 34
  • A pair of isolated cells
• References
• About this document ...