Nonconstructible blocks in 1D cellular automata: minimal generators and natural systems

摘要

The paper concerns minimal nonconstructible blocks of cellular automata, i.e. minimal combinations of cell states that never appear in the evolution of an automaton. Using our previous work on the construction of predecessors of given configurations, we analyse with numerical experiments the sets of nonconstructible blocks for one-dimensional (1D) cellular automata with binary and ternary neighbourhoods and binary cell states, and compare our results with the classification made by Voorhees; we also analyse the relationship of the Voorhees classes to the static parameter gl. On applying our algorithm to cellular-automata models of natural systems, we provide common sense interpretations of unreachable states of some biological distributed processes.