1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
|
<html>
<title>Golly Help: QuickLife</title>
<body bgcolor="#FFFFCE">
<p>
QuickLife is a fast, conventional (non-hashing) algorithm for
exploring Life and other 2D outer-totalistic rules.
Such rules are defined using "B0...8/S0...8" notation, where
the digits after B specify the counts of live neighbors necessary
for a cell to be born in the next generation, and the digits
after S specify the counts of live neighbors necessary for a
cell to survive to the next generation.
Here are some example rules:
<p><b><a href="rule:B3/S23">B3/S23</a></b> [Life]<br>
John Conway's rule is by far the best known and most explored CA.
<p><b><a href="rule:B36/S23">B36/S23</a></b> [HighLife]<br>
Very similar to Conway's Life but with an interesting replicator.
<p><b><a href="rule:B3678/S34678">B3678/S34678</a></b> [Day & Night]<br>
Dead cells in a sea of live cells behave the same as live cells
in a sea of dead cells.
<p><b><a href="rule:B35678/S5678">B35678/S5678</a></b> [Diamoeba]<br>
Creates diamond-shaped blobs with unpredictable behavior.
<p><b><a href="rule:B2/S">B2/S</a></b> [Seeds]<br>
Every living cell dies every generation, but most patterns still explode.
<p><b><a href="rule:B234/S">B234/S</a></b> [Serviettes or Persian Rug]<br>
A single 2x2 block turns into a set of Persian rugs.
<p><b><a href="rule:B345/S5">B345/S5</a></b> [LongLife]<br>
Oscillators with extremely long periods can occur quite naturally.
<p><a name="vonNeumann"></a> <br>
<font size=+1><b>Von Neumann neighborhood</b></font>
<p>
The above rules use the Moore neighborhood, where each cell has 8 neighbors.
In the von Neumann neighborhood each cell has only the 4 orthogonal neighbors.
To specify this neighborhood just append "V" to the usual "B.../S..." notation
and use neighbor counts ranging from 0 to 4.
For example, try <b><a href="rule:B13/S012V">B13/S012V</a></b> or
<b><a href="rule:B2/S013V">B2/S013V</a></b>.
<p>
Note that when viewing patterns at scales 1:8 or 1:16 or 1:32, Golly displays
diamond-shaped icons for rules using the von Neumann neighborhood
and circular dots for rules using the Moore neighborhood.
<p><a name="hex"></a> <br>
<font size=+1><b>Hexagonal neighborhood</b></font>
<p>
QuickLife can emulate a hexagonal neighborhood on a square grid by ignoring the
NE and SW corners of the Moore neighborhood so that every cell has 6 neighbors:
<pre>
NW N NE NW N
W C E -> W C E
SW S SE S SE
</pre>
To specify a hexagonal neighborhood just append "H" to the usual "B.../S..." notation
and use neighbor counts ranging from 0 to 6. Here's an example:
<pre>
x = 7, y = 6, rule = B245/S3H
obo$4bo$2bo$bo2bobo$3bo$5bo!
</pre>
Editing hexagonal patterns in a square grid can be somewhat confusing,
so to help make things a bit easier Golly displays slanted hexagons
when in icon mode.
<p><a name="nontotal"></a> <br>
<font size=+1><b>Non-totalistic rules</b></font>
<p>
All of the above rules are classified as "totalistic" because the outcome depends only
on the total number of neighbors. Golly also supports non-totalistic rules for Moore
neighborhoods —
such rules depend on the configuration of the neighbors, not just their counts.
<p>
The syntax used to specify a non-totalistic rule is based on a notation developed by
Alan Hensel. It's very similar to the above "B.../S..." notation but uses
various lowercase letters to represent unique neighborhoods.
One or more of these letters can appear after an appropriate digit
(which must be from 1 to 7, depending on the letters).
The usual counts of 0 and 8 can still be used without letters since there is no way
to constrain 0 or 8 neighbors.
<p>
For example, <b><a href="rule:B3/2a34">B3/2a34</a></b> means birth on 3 neighbors
and survival on 2 adjacent neighbors (a corner and an edge), or 3 or 4 neighbors.
<p>
Letter strings can get quite long, so it's possible to specify their inverse
using a "-" between the digit and the letters.
For example, <b><a href="rule:B2cekin/S12">B2cekin/S12</a></b> is equivalent to
<b><a href="rule:B2-a/S12">B2-a/S12</a></b> and means birth on 2 non-adjacent
neighbors, and survival on 1 or 2 neighbors.
(This is David Bell's "Just Friends" rule.)
<p>
The following table shows which letters correspond to which neighborhoods.
The central cell in each neighborhood is colored red, corner neighbors are green,
edge neighbors are yellow and ignored neighbors are black:
<p>
<img src="hensel.png">
<p>
The table makes it clear which digits are allowed before which letters.
For example, B1a/S and B5z/S are both invalid rules.
<p>
Golly uses the following steps to convert a given non-totalistic rule into
its canonical version:
<p>
<ol>
<li>
An underscore can be used instead of a slash, but the canonical version
always uses a slash.
<li>
The lowercase letters are listed in alphabetical order.
For example, B2nic/S will become B2cin/S.
<li>
A given rule is converted to its shortest equivalent version.
For example, B2ceikn/S will become B2-a/S.
If equivalent rules have the same length then the version without the minus sign
is preferred. For example, B4-qjrtwz/S will become B4aceikny/S.
<li>
It's possible for a non-totalistic rule to be converted to a totalistic rule.
If you supply all the letters for a specific neighbor count then the canonical
version removes the letters. For example, B2aceikn3/S will become B23/S.
(Note that B2-3/S is equivalent to B2aceikn3/S so will also become B23/S.)
<li>
If you supply a minus sign and all the letters for a specific neighbor count
then the letters <i>and</i> the neighbor count are removed.
For example, B2-aceikn3/S will become B3/S.
</ol>
<p><a name="map"></a> <br>
<font size=+1><b>MAP rules</b></font>
<p>
The totalistic and non-totalistic rules above are only a small subset of all possible
rules for a 2-state Moore neighborhood. The Moore neighborhood has 9 cells which gives
512 (2^9) possible combinations of cells. For each of these combinations you define whether
the output cell is dead or alive, giving a string of 512 digits, each being 0 (dead) or 1 (alive).
<pre>
0 1 2
3 4 5 -> 4'
6 7 8
</pre>
The first few entries for Conway's Life (B3/S23) in this format are as follows:
<pre>
Cell 0 1 2 3 4 5 6 7 8 -> 4'
0 0 0 0 0 0 0 0 0 0 -> 0
1 0 0 0 0 0 0 0 0 1 -> 0
2 0 0 0 0 0 0 0 1 0 -> 0
3 0 0 0 0 0 0 0 1 1 -> 0
4 0 0 0 0 0 0 1 0 0 -> 0
5 0 0 0 0 0 0 1 0 1 -> 0
6 0 0 0 0 0 0 1 1 0 -> 0
7 0 0 0 0 0 0 1 1 1 -> 1 B3
8 0 0 0 0 0 1 0 0 0 -> 0
9 0 0 0 0 0 1 0 0 1 -> 0
10 0 0 0 0 0 1 0 1 0 -> 0
11 0 0 0 0 0 1 0 1 1 -> 1 B3
...
19 0 0 0 0 1 0 0 1 1 -> 1 S2
...
511 1 1 1 1 1 1 1 1 1 -> 0
</pre>
This creates a string of 512 binary digits:
<pre>
00000001000100000001...0
</pre>
This binary string is then base64 encoded for brevity giving a string of 86 characters:
<pre>
ARYXfhZofugWaH7oaIDogBZofuhogOiAaIDogIAAgAAWaH7oaIDogGiA6ICAAIAAaIDogIAAgACAAIAAAAAAAA
</pre>
By prefixing this string with "MAP" the syntax of the rule becomes:
<pre>
rule = MAP<base64_string>
</pre>
So, Conway's Life (B3/S23) encoded as a MAP rule is:
<pre>
rule = MAPARYXfhZofugWaH7oaIDogBZofuhogOiAaIDogIAAgAAWaH7oaIDogGiA6ICAAIAAaIDogIAAgACAAIAAAAAAAA
</pre>
Given each MAP rule has 512 bits this leads to 2^512 (roughly 1.34x10^154) unique rules.
Totalistic rules are a subset of isotropic non-totalistic rules which are a subset of MAP rules.
<p>
MAP rules can also be specified for Hexagonal and von Neumann neighborhoods.
<p>
Hexagonal neighborhoods have 7 cells (center plus 6 neighbors) which gives 128 (2^7) possible combinations of cells.
These encode into 22 base64 characters.
<p>
Von Neumann neighborhoods have 5 cells (center plus 4 neighbors) which gives 32 (2^5) possible combinations of cells.
These encode into 6 base64 characters.
<p><a name="b0emulation"></a> <br>
<font size=+1><b>Emulating B0 rules</b></font>
<p>
Rules containing B0 are tricky to handle in an unbounded universe because every
dead cell becomes alive in the next generation. If the rule doesn't contain S<i>max</i>
(where <i>max</i> is the number of neighbors in the neighborhood: 8 for Moore, 6 for
Hexagonal or 4 for Von Neumann) then the "background" cells alternate from all-alive
to all-dead, creating a nasty strobing effect. To avoid these problems, Golly emulates
rules with B0 in the following way:
<p>
A totalistic rule containing B0 and Smax is converted into an equivalent rule (without B0) by
inverting the neighbor counts, then using S(max-x) for the B counts and B(max-x) for
the S counts.
For example, B0123478/S01234678 (AntiLife) is changed to B3/S23 (Life)
via these steps: B0123478/S01234678 -> B56/S5 -> B3/S23.
<p>
A non-totalistic rule is converted in a similar way. The isotropic letters are inverted and
then S(max-x)(letters) is used for B counts and B(max-x)(letters) is used for the S counts.
The 4 neighbor letters are swapped using the following table:
<pre>
4c -> 4e
4e -> 4c
4k -> 4k
4a -> 4a
4i -> 4t
4n -> 4r
4y -> 4j
4q -> 4w
4j -> 4y
4r -> 4n
4t -> 4i
4w -> 4q
4z -> 4z
</pre>
A totalistic rule containing B0 but not Smax is converted into a pair of rules (both without B0):
one is used for the even generations and the other for the odd generations.
The rule for even generations uses inverted neighbor counts.
The rule for odd generations uses S(max-x) for the B counts and B(max-x) for the S counts.
For example, B03/S23 becomes B1245678/S0145678 (even) and B56/S58 (odd).
<p>
A non-totalistic rule is converted in a similar way. For even generations invert both
B(x)(letter) and S(x)(letter).
For odd generations except 4-neighbor letters, use B(x)(letter) if and only if the
original rule has S(max-x)(letter) and use S(x)(letter) if and only if the original rule
has B(max-x)(letter). For 4-neighbor isotropic letters use the table above.
For example, B0124-k/S1c25 becomes B34k5678/S01-c34678 (even) and B367c/S4-k678 (odd).
<p>
For a MAP rule B0 is equivalent to the first bit being 0. Smax is equivalent to the 511th
bit being 1. For B0 with Smax the rule is converted to NOT(REVERSE(bits)). For B0 with Smax
the even rule is NOT(bits) and the odd rule is REVERSE(bits).
<p>
In all cases, the replacement rule(s) generate patterns that are equivalent
to the requested rule. However, you need to be careful when editing an
emulated pattern in a rule that contains B0 but not Smax. If you do a cut
or copy then you should only paste into a generation with the same parity.
<p><a name="wolfram"></a> <br>
<font size=+1><b>Wolfram's elementary rules</b></font>
<p>
QuickLife supports Stephen Wolfram's elementary 1D rules.
These rules are specified as "Wn" where n is an even number from 0 to 254.
For example:
<p><b><a href="rule:W22">W22</a></b><br>
A single live cell creates a beautiful fractal pattern.
<p><b><a href="rule:W30">W30</a></b><br>
Highly chaotic and an excellent random number generator.
<p><b><a href="rule:W110">W110</a></b><br>
Matthew Cook proved that this rule is capable of universal computation.
<p>
The binary representation of a particular number specifies the cell
states resulting from each of the 8 possible combinations of a cell and
its left and right neighbors, where 1 is a live cell and 0 is a dead cell.
Here are the state transitions for W30:
<pre>
111 110 101 100 011 010 001 000
| | | | | | | |
0 0 0 1 1 1 1 0 = 30 (2^4 + 2^3 + 2^2 + 2^1)
</pre>
Note that odd-numbered rules have the same problem as B0 rules. Golly
currently makes no attempt to emulate such rules, and they are not supported.
</body>
</html>
|
