Injections of Neighborhood Size Three and Four on the Set of Configurations from the Infinite One-Dimensional Tessellation Automata of Two-State Cells.
Research and development technical rept.,
ARMY ELECTRONICS COMMAND FORT MONMOUTH N J
Pagination or Media Count:
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 cells 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