In the interest of concreteness, I am going to talk about cellular automata (CA) a lot here. They serve as a convenient toy example for talking about computation, and particularly about structures embedded in computations (it is easy to think about how such structures exert control over their environment, although this is just as philosophically problematic as acausal control in general). CA have no relevant mystical properties. You could substitute any other sufficiently complicated program, but CA have the virtue of matching our intuition about physics in several ways (similar notions of space and time, of regular physical law, and so on). Whenever the intuition from CAs seems to get in the way of thinking about what is going on in generality I will abandon them.
In general, a CA is defined by a collection of cells, connected by some notion of locality and evolving over time. The state of a cell at time T+1 is determined by the state of its neighbors at time T. We will normally assume that the cells are regular in a strong sense, for example arranged in an N-dimensional grid with translationally invariant update rules.
There are many possible CA and some of their properties are useful exemplars of more general phenomena.
- Deterministic: The state of a deterministic CA at any time T is completely determined by knowledge of its state at any earlier time together with the update rule.
- Reversible: An automata is reversible if the state at time T-1 is uniquely determined by the state at time T. For example, if we have an automata on a line and each cell becomes equal to its left-hand neighbor on each step, we can reverse the evolution by shifting to the right each step.
- Randomized: In a randomized automaton, the state of a cell and its neighbors at time T determine only a probability distribution over possible states for the cell at time T+1. Knowledge of the initial configuration of a randomized CA is not enough to determine its state at future times: it may be necessary to specify a very large number of random bits in order to pin down the future state.
- Local: A CA is local if there is a constant D (the dimension) such that changing the value at any cell can affect the value of at most T^D other cells within T steps.
- Quantum: Quantum mechanics changes the way probability works; we can talk about a randomized CA using quantum probability (where now the local transitions are required to be unitary rather than Markov), and we obtain a quantum CA. These exhibit nearly all of the “weirdness” of physical quantum systems.