I've been playing with a cellular automaton simulator. Read the wiki article.
The standard "Conway's Game of Life" uses the rule 3/23, i.e., cells are activated ("born") when they have 3 active neighbors, and active cells remain active if they have 2 or 3 active neighbors. This rule is at a temperate medium between too fecund (every input grows out of control, chaotically) and too sterile (every input dies). Certain engineered structures can replicate themselves (actually a slightly different rule, 36/23) or spit-out new patterns indefinitely. Most patterns, however, tend over many turns to a static system of oscillators and still-lifes.
The "replicator" rule is 1357/1357--born or survive with an odd number of active neighbors. Every pattern is a replicator. Here's an example. The input is a 5x5 square at the center of the map.
In the course of their replication, the patterns become pretty baroque, but they return in embedded cycles to the simplicity of the original pattern (again, many steps omitted):
Here is the 2nd-to-last step.
And the last step. Nearly all of the material from the previous step has disappeared, which means that, excepting the 25x2 positions constituting the two squares, all of the positions had an even number of active neighbors (remember, the rule is 1357/1357).
The original 5x5 square has produced doppelgangers equidistant from its starting position. This last step becomes the first part of a 64-cycle loop that continually returns to this simple starting-point (I'll call it "step 1"). Here is the 63rd step of the cycle:
The two squares in Step 1 are linked together in interesting ways. Consider what happens when you modify one of the squares but not the other. I've hollowed-out the lower square, i.e., removed a 3x3 square from its center.
The change from step 1 has been inverted--now the top square bears it. More interestingly, the difference between the doppelgangers has been rendered equidistant between them. That is the 3x3 square in the middle of the map. The system is actually a calculator of geometric difference. It supports a sort of arithmetic. Let's call the initial unmodified 5x5 figure "M" and the modified figure "N." There are 3 positions on the map: top, difference, and bottom. So, respectively, the initial state is [M, Ø, N]. The final is [N, M-N, M]. Figure subtraction produces whatever sub-figure is not shared by the inputs. Modifying the difference imposes identical changes on the top and bottom:
I've added a little crown to the difference, a 3x1 bar.
One of many intermediary stages. Notice how many combinations of figures and differences have emerged. Notationally, M is the filled 5x5, N is the hollow 5x5, and f is the modified difference. Below we see M, N, M-N, Mf, Nf and f -- six figures in all.
But by the last step, only three remain: [Mf, Mf-Nf, Nf] = [Mf, M-N, Nf].
Remember that all of this calculation follows from a simple rule governing cell activity. I think that only particular sorts of maps can support this pattern -- the one used here has 192x256 cells, both multiples of 64. The smallest map I've found that works is 6x8 cells. It has a 2-cycle but follows all the same properties as the big map above. Cool stuff!
P.S.
The rule could also be thought of as a boolean calculator. Let's consider a simple 12x16 map with only 1D figures. Each is like a boolean vector. So let's have two figures, A = {TTF} and B = {FTF}. The operation AB is defined as: A XOR B = {a1 XOR b1, a2 XOR b2, a3 XOR b3}, so AB = {TFF}.
XOR is defined for two inputs, either T or F. It outputs F if the inputs are the same, T if different.
So, in our automata map, the middle figure calculates A XOR B:
Indeed, {TTF} XOR {FTF} = {TFF}. Note that A and B have traded places in the process. This inversion is pretty odd, especially since it doesn't seem to happen during regular cycles (i.e., when step 1 is configured as top, middle, bottom: (A, AB, B), respectively. But in fact, the same inversion rule applies across the board--it's just invisible in some cases. This surface variety is a consequence of the properties of XOR.
Let's consider the transparent cases first.
If we take [M, MN, N] and give the bottom figure an additional figure x, then the new initial state is [M, MN, Nx]. The final state will be [Mx, MNx, N]. A technicality here: the "additional" figure x is defined according to the same XOR operation that defines any "XY" relation. So, e.g., if X = {TTF} and Z = {TFT}, and Xy = Z, then y = {FTT}, since {TTF} XOR {FTT} = {TFT}. Or intuitively, the additional element "y" adds to X where X has nothing but subtracts from X where there is overlap. Back to [Mx, MNx, N], note that the additional element x has been transferred from the bottom to the top figure. In effect, the original state [M, MN, Nx] (1) --> [MNNx, MNx, MMN] (2) --> [Mx, MNx, N]. What happened there? I'll get to step (1) below. Step (2) follows the general properties of XOR. It is both commutative and associative, so we can group like terms together. For any boolean vector A, A XOR A = 0, the false vector (since XOR returns F for all like input pairs). T XOR F = T and F XOR F = F, so XOR 0 preserves its first input. Thus, MNNx = Mx, and MMN = N. The first step follows the proposed generalized transformation: [a, b, c] --> [bc, ac, ab]. In other words, the automata game calculates all possible XOR combinations on the map. Let's try it on the other cases.
The input [M, 0, N] will return [N, MN, M]. Explanation? The generalized transformation gives [N0, MN, M0]. Since 0 preserves inputs, the final state is [N, MN, M].
The input [M, MN, N] will return itself. The generalized transformation is [MNN, MN, MMN]. Likes cancel, so the output is [M, MN, N].
One last case. The input [M, MNx, N] will return [Mx, MN, Nx]. The generalized transformation is [MNNx, MNxx, MNMx]. Apply XOR rules and the output is [Mx, MN, Nx].
Here are some examples:
M = {TFFFT], N = {FTFTF}, MN = {TTFTT}. Suppose {M, MNx, N}, where x = {FFTFF}. Note that the vector x does not appear graphically per se, but through its XOR addition to the middle figure. In the first image below, it thus appears as the filled-in slot in the middle of the middle figure (since {TTFTT} XOR {FFTFF} = {TTTTT}).
The whole process should yield {Mx, MN, Nx} = {TFTFT, TTFTT, FTTTF}. Graphically:
A more complicated example:
[M, MN, N] = [TTTT, FFFT, TTTF]
[Mx, MNy, Nz]: x = {TFFF}, y={FTFF}, z = {FFTF}; [FTTT, FTFT, TTFF]
[MNNyz, MNxz, MMNxy] = [Myz, MNxz, Nxy] = [TFFT, TFTT, FFTF]
--A Hermit
The standard "Conway's Game of Life" uses the rule 3/23, i.e., cells are activated ("born") when they have 3 active neighbors, and active cells remain active if they have 2 or 3 active neighbors. This rule is at a temperate medium between too fecund (every input grows out of control, chaotically) and too sterile (every input dies). Certain engineered structures can replicate themselves (actually a slightly different rule, 36/23) or spit-out new patterns indefinitely. Most patterns, however, tend over many turns to a static system of oscillators and still-lifes.
The "replicator" rule is 1357/1357--born or survive with an odd number of active neighbors. Every pattern is a replicator. Here's an example. The input is a 5x5 square at the center of the map.
I've omitted a lot of steps. Here's the 8th, where the original pattern has produced eight copies.
The original 5x5 square has produced doppelgangers equidistant from its starting position. This last step becomes the first part of a 64-cycle loop that continually returns to this simple starting-point (I'll call it "step 1"). Here is the 63rd step of the cycle:
The two squares in Step 1 are linked together in interesting ways. Consider what happens when you modify one of the squares but not the other. I've hollowed-out the lower square, i.e., removed a 3x3 square from its center.
The 2nd-to-last step of the new cycle.
The final step:
I've added a little crown to the difference, a 3x1 bar.
Remember that all of this calculation follows from a simple rule governing cell activity. I think that only particular sorts of maps can support this pattern -- the one used here has 192x256 cells, both multiples of 64. The smallest map I've found that works is 6x8 cells. It has a 2-cycle but follows all the same properties as the big map above. Cool stuff!
P.S.
The rule could also be thought of as a boolean calculator. Let's consider a simple 12x16 map with only 1D figures. Each is like a boolean vector. So let's have two figures, A = {TTF} and B = {FTF}. The operation AB is defined as: A XOR B = {a1 XOR b1, a2 XOR b2, a3 XOR b3}, so AB = {TFF}.
XOR is defined for two inputs, either T or F. It outputs F if the inputs are the same, T if different.
So, in our automata map, the middle figure calculates A XOR B:
Let's consider the transparent cases first.
If we take [M, MN, N] and give the bottom figure an additional figure x, then the new initial state is [M, MN, Nx]. The final state will be [Mx, MNx, N]. A technicality here: the "additional" figure x is defined according to the same XOR operation that defines any "XY" relation. So, e.g., if X = {TTF} and Z = {TFT}, and Xy = Z, then y = {FTT}, since {TTF} XOR {FTT} = {TFT}. Or intuitively, the additional element "y" adds to X where X has nothing but subtracts from X where there is overlap. Back to [Mx, MNx, N], note that the additional element x has been transferred from the bottom to the top figure. In effect, the original state [M, MN, Nx] (1) --> [MNNx, MNx, MMN] (2) --> [Mx, MNx, N]. What happened there? I'll get to step (1) below. Step (2) follows the general properties of XOR. It is both commutative and associative, so we can group like terms together. For any boolean vector A, A XOR A = 0, the false vector (since XOR returns F for all like input pairs). T XOR F = T and F XOR F = F, so XOR 0 preserves its first input. Thus, MNNx = Mx, and MMN = N. The first step follows the proposed generalized transformation: [a, b, c] --> [bc, ac, ab]. In other words, the automata game calculates all possible XOR combinations on the map. Let's try it on the other cases.
The input [M, 0, N] will return [N, MN, M]. Explanation? The generalized transformation gives [N0, MN, M0]. Since 0 preserves inputs, the final state is [N, MN, M].
The input [M, MN, N] will return itself. The generalized transformation is [MNN, MN, MMN]. Likes cancel, so the output is [M, MN, N].
One last case. The input [M, MNx, N] will return [Mx, MN, Nx]. The generalized transformation is [MNNx, MNxx, MNMx]. Apply XOR rules and the output is [Mx, MN, Nx].
Here are some examples:
M = {TFFFT], N = {FTFTF}, MN = {TTFTT}. Suppose {M, MNx, N}, where x = {FFTFF}. Note that the vector x does not appear graphically per se, but through its XOR addition to the middle figure. In the first image below, it thus appears as the filled-in slot in the middle of the middle figure (since {TTFTT} XOR {FFTFF} = {TTTTT}).
The whole process should yield {Mx, MN, Nx} = {TFTFT, TTFTT, FTTTF}. Graphically:
[M, MN, N]
[M, MNx, N]
[Mx, MN, Nx]
[M, MN, N] = [TTTT, FFFT, TTTF]
[Mx, MNy, Nz]: x = {TFFF}, y={FTFF}, z = {FFTF}; [FTTT, FTFT, TTFF]
--A Hermit
No comments:
Post a Comment