Some definitions
Configuration: The state of all the cells in the space of interest
- (The catch is: What are allowable states? Reachability problem rears it’s head)
Computation:
- Set up a correspondence with TM that preserves the tape/head distinction. Not all CA are TM and therefore not all CA are universal computers.
Construction:
- Stable or dying out configurations are not computationally interesting
Self-Reproduction: A special case of construction
Symmetries of Cellular Spaces:
- Symmetries of neighborhood functions, and those of transition functions.
Propagation:
- Does the CA go to infinity? Is it unbounded, bounded, asymptotic?
Paths and Signals: The states may be complex vectors with ‘semantics’ (see wire world example)