Self-similarity of linear cellular automata

摘要

Space-time patterns of linear cellular automata are studied. Existence of the limit of a series of space-time patterns contracted by time (called a “limit set”) is proved for any linear cellular automata, using properties of multinomial coefficients. Such limit sets of linear cellular automata are generally fractals. We characterize the self-similar structure of the limit set by a transition matrix, whose maximum eigenvalue determines its Hausdorff dimension. The limit set of (a power of a prime)-state linear cellular automata has the same dimension as the corresponding prime-state linear cellular automata, which considerably simplifies the calculation of dimensions of limit sets. The limit set with respect to one of the states is shown to be identical to the limit set of another or the same linear cellular automata.