Injections of Neighborhood Size Three and Four on the Set of Configurations from the Infinite One-Dimensional Tessellation Automata of Two-State Cells.

The tessellation structure is a formal model of a regular array of identical finite-state machines (cells) uniformly interconnected. Array configurations are the infinite patterns formed by the states of the machines in the array. The transformation of one array configuration to another (called a global transformation) is caused by a local transformation acting simultaneously on all cells in the array. The set of cells affecting the next state of a cell (i.e., the arguments of the local transformation) is referred to as the cell's neighborhood. In the one-dimensioned infinite array of two-state cells, there are 128 local transformations having neighborhoods consisting of three contiguous cells and 32,768 local transformations having neighborhoods consisting of four continuous cells. By an exhaustive computer program, it has been shown that none of those having neighborhood size three correspond to global transformations that are non-trivial injections on the set of array configurations. It has been conjectured for some time that the same was also true for local transformations of neighborhood size four. The report proves that this conjecture is false. (Author)