Re:Cryptography with Cellular Automata (1985) [pdf]
by DonHopkins on Thursday October 26, 2017 @01:23PM
(#15561024)
Great explanation and examples! But to be pedantic, a cell only has one property: its current state. The set of states, transition rules, etc are properties of the rule itself.
The point you made about transitioning simultaneously is very important: "So at the basic level (you can add more complexity) a cellular automata is a collection of finite automata operating on the same rules and transitioning simultaneously, but using each other's states as their inputs."
That means you can't serially apply the rule to the cells "in place" -- each cell needs to know the value of its neighbors at the same point in time, so if you serially scan top/bottom left/right over the cells, and change each of their values according to the values of their adjacent cells in memory at the time, the inputs to the rule will be incorrect, straddling values from the previous time step (below and to the right) and the current time step (above and to the left). So you have to double buffer the cells, and read ALL the rule inputs of each cell from the previous time step buffer, then write them into the next time step buffer.
If you implement in-place Life without double buffering, it will look and behave kind of like Life, but strangely mutated, and none of the gliders or other patterns will work properly, because the rule inputs are skewed in time.
The Moveable Feast Machine I described in another posting is not technically a cellular automata, because it's asynchronous, and relaxes the requirement that all cells transition simultaneously, and it only requires that no two overlapping neighborhoods may be computed at the same time.
So with MFMs, double buffering is not necessary, and you don't have to pay for synchronization (which is extremely expensive) if you don't need it (or you can just pay for as much as you need, a la carte). The point of Moveable Feast is robust computing on massively parallel unreliable hardware, which is practically impossible with Cellular Automata's strict synchronization requirements.
There are different ways of classifying Cellular Automata rules, and defining one kind in terms of another kind.
For example, Life and Anneal (a "twisted majority rule") are both "Counting Rules" because they can be reduced to simply counting the number of neighbors, then using a look-up table or logic to determine the next state based purely on the sum of the number of neighbors (which may or may not include the center cell). Not all CA rules are counting rules, though.
You can enumerate all possible rules (for a given set of inputs or "neighborhood") and refer to them by their rule number, an index into all possible rules of that type (the value of the lookup table as a binary number). That's what Wolfram means when he refers to "Rule 30", which is a particularly interesting two-dimensional "elementary cellular automaton". Golly has some formats for compactly enumerating and specifying rules.
Rules may also depend on additional inputs like the temporal phase (alternating 0/1 over two steps for two-phase rules, repeating 00/01/10/11 over four steps for four phase rules, etc), the spatial phase (low bit(s) of the x and y cell coordinates), and even corresponding cells from other rules run in parallel or video input.
For example, you can define the Margolus neighborhood in terms of the Moore neighborhood by using the temporal, horizontal and vertical phase to determine which cell is "opposite", "clockwise" or "counter clockwise". You use the time phase to alternate between two overlapping checkerboards of 2x2 cell blocks. Within each checkerboard you use the horizontal and vertical phase to determine whether to look left, right, up or down or diagonally to get the clockwise, counter clockwise or opposite cell in the 2x2 block.
The point you made about transitioning simultaneously is very important: "So at the basic level (you can add more complexity) a cellular automata is a collection of finite automata operating on the same rules and transitioning simultaneously, but using each other's states as their inputs."
That means you can't serially apply the rule to the cells "in place" -- each cell needs to know the value of its neighbors at the same point in time, so if you serially scan top/bottom left/right over the cells, and change each of their values according to the values of their adjacent cells in memory at the time, the inputs to the rule will be incorrect, straddling values from the previous time step (below and to the right) and the current time step (above and to the left). So you have to double buffer the cells, and read ALL the rule inputs of each cell from the previous time step buffer, then write them into the next time step buffer.
If you implement in-place Life without double buffering, it will look and behave kind of like Life, but strangely mutated, and none of the gliders or other patterns will work properly, because the rule inputs are skewed in time.
The Moveable Feast Machine I described in another posting is not technically a cellular automata, because it's asynchronous, and relaxes the requirement that all cells transition simultaneously, and it only requires that no two overlapping neighborhoods may be computed at the same time.
So with MFMs, double buffering is not necessary, and you don't have to pay for synchronization (which is extremely expensive) if you don't need it (or you can just pay for as much as you need, a la carte). The point of Moveable Feast is robust computing on massively parallel unreliable hardware, which is practically impossible with Cellular Automata's strict synchronization requirements.
There are different ways of classifying Cellular Automata rules, and defining one kind in terms of another kind.
For example, Life and Anneal (a "twisted majority rule") are both "Counting Rules" because they can be reduced to simply counting the number of neighbors, then using a look-up table or logic to determine the next state based purely on the sum of the number of neighbors (which may or may not include the center cell). Not all CA rules are counting rules, though.
https://en.wikipedia.org/wiki/Life-like_cellular_automaton
You can enumerate all possible rules (for a given set of inputs or "neighborhood") and refer to them by their rule number, an index into all possible rules of that type (the value of the lookup table as a binary number). That's what Wolfram means when he refers to "Rule 30", which is a particularly interesting two-dimensional "elementary cellular automaton". Golly has some formats for compactly enumerating and specifying rules.
http://mathworld.wolfram.com/Rule30.html
https://imgur.com/a/lKAbP
https://en.wikipedia.org/wiki/Elementary_cellular_automaton
https://en.wikipedia.org/wiki/Golly_(program)
https://github.com/gollygang/ruletablerepository/wiki/TheRul...
Each rule is defined in terms of a certain "neighborhood" of inputs.
A "neighborhood" is the set of adjacent cells that the rule may depend on. It's like a "kernel" from signal processing.
Classic 2D neighborhoods include the 9-neighbor (including center) 8-connected Moore Neighborhood (NW N NE W C E SW S E), used by Life for example:
https://en.wikipedia.org/wiki/Moore_neighborhood
The 5-neighbor 4-connected von Neumann neighborhood (N W C E S), used by John von Neumann's 29 state cellular automata rule for example:
https://en.wikipedia.org/wiki/Von_Neumann_neighborhood
The 4-neighbor rotationally symmetrical Margolus Neighborhood (C OPP CW CCW), use by billiard ball and reversible rules for example:
https://en.wikipedia.org/wiki/Block_cellular_automaton
Rules may also depend on additional inputs like the temporal phase (alternating 0/1 over two steps for two-phase rules, repeating 00/01/10/11 over four steps for four phase rules, etc), the spatial phase (low bit(s) of the x and y cell coordinates), and even corresponding cells from other rules run in parallel or video input.
For example, you can define the Margolus neighborhood in terms of the Moore neighborhood by using the temporal, horizontal and vertical phase to determine which cell is "opposite", "clockwise" or "counter clockwise". You use the time phase to alternate between two overlapping checkerboards of 2x2 cell blocks. Within each checkerboard you use the horizontal and vertical phase to determine whether to look left, right, up or down or diagonally to get the clockwise, counter clockwise or opposite cell in the 2x2 block.
https://github.com/SimHacker/CAM6/blob/master/javascript/CAM...