Next: Introduction

Cellular automata with almost periodic initial conditions

A. Hof and O. Knill

October 1994 (revised March 1995)

This paper appeared in the journal Nonlinearity, 8 p. 477-491, 1995 MR 96g:58093
1991 Mathematics Subject Classification: 82C20, 54H20, 58Fxx


Cellular automata are dynamical systems on the compact metric space of subshifts. They leave many classes of subshifts invariant. Here we show that cellular automata leave `circle subshifts' invariant. These are the strictly ergodic subshifts of tex2html_wrap_inline403 obtained by a circle sequence tex2html_wrap_inline405, where J is a finite union of half-open intervals. For such initial conditions, the evolution of the whole infinite configuration can be computed by evolving the finitely many parameters defining the set J. Moreover, many macroscopic quantities can be computed exactly for the infinite system. We illustrate that in one dimension by rule 18 and in two dimensions by the Game of Life. The ideas also apply to cellular automata acting on tex2html_wrap_inline411. This we illustrate by the HPP model, a lattice gas automaton with N=16.

  • Higher dimensional CA
  • Discussion and open problems
  • References
  • About this document ...
  • Back to Oliver's Homepage

  • Oliver Knill
    Fri Jun 26, 1998