Cellular Automata/Global Dynamics
Attractor Basin[edit | edit source]
When discussing global dynamics of cellular automata the word state is used to describe configurations.
Graphic conventions[edit | edit source]
The following diagrams/captions are based on the original figure State-space and basins of attraction on the DDLab website. Sub-trees, basins of attraction, and the entire basin of attraction field (for cellular automata, random Boolean networks, and discrete dynamic networks in general) can be computed and drawn with the DDLab software.
The state space is made of all available states of a cellular automaton. It's size is where is the size of the (finite) lattice, and is the value-range or alphabet, for binary systems. is one of the states.
The trajectory is defined by the global transition function. State is a predecessor and state is the successor of state .
If the global transtition function is not injective, than states may have more than one predecessor (preimage). The in-degree of the state is the number of its predecessors. A state may have no predecessors, than it is called garden of Eden.
A trajectory may encounter a state occurred previously (it must if the lattice is finite), thus it has entered an attraction cycle. A point attraction cycle has the length of a single cell.
By recursively searching predecessors from a root state on the attraction cycle (the predecessor on the cycle is excluded) till all garden of Eden states are reached a transient tree is constructed. A subtree can be constructed from an arbitrary state on the tree, the root of the subtree.
By adding transient trees to each state on the attraction cycle, a basin of attraction is constructed. Some attraction cycles may have no transient trees, this is especially true for reversible cellular automata.
By grouping all the states in the state space into respective basins of attraction, a basin of attraction field is constructed.
Injectivity, surjectivity and bijectivity[edit | edit source]
The CA rule is reversible, if the global transition function is bijective (both injective and surjective).
Injectivity of the global transition function[edit | edit source]
is injective, there is at most one preimage for any CA configuration.
So there are no configurations with more than one predecessor.
Surjectivity of the global transition function[edit | edit source]
is injective, there is at least one preimage for any CA configuration.
So there are no configurations without a predecessor (so called Garden of Eden).
It is easy to determine the existence of garden of Eden states for one dimensional CA using De Bruijn Diagrams.
Bijectivity of the global transition function[edit | edit source]
is bijective if it is both injective and surjective. For any configuration there is exactly one predecessor.