1
$\begingroup$

This is a similar question to How 2d cellular automata rules works? However, the answer there did not provide me what I am looking for. Specifically, I want to be able to render these 2d cellular automata forms: https://www.wolframscience.com/nks/p173--cellular-automata/ I cannot find any reference anywhere that explains how to change between a real number and a growth rule. In 1d, the situation is well documented, such as here: https://mathworld.wolfram.com/ElementaryCellularAutomaton.html but in 2d the exact mapping of bits is nowhere to be found. I'd really like to make a program, so that I can for instance enter the number 465 and it will draw the pattern 465 from the Wolfram book. The other stack exchange answer I linked to above provides a possible binary mapping, however the method given there does not produce the same numbers as in the Wolfram reference. The binary value of 465 is 111010001 which does not help me at all. This particular shape is based on adding a cell when exactly one neighbor is currently occupied, so shouldn't we expect to have 4 1's in a row, one for each of the four neighbors? And to make this even more confusing, the last two digits seem to be swapped from the description given on the Wolfram page itself... It seems clear from the other Stack Overflow answer that there is not just one possible binary mapping but many, however given that there already exists a guide with pictures referenced by rule numbers I would really like to actually be able to use those specific rule numbers. Thanks.

$\endgroup$
  • $\begingroup$ There is explanation on the bottom of the Wolfram page you link to. The bits indeed code the number of cells set in the neighbourhood and the value of the central cell itself, starting from the last bit for central=white, all white neighbours. So your binary value is then read as (all 4 neighbours;black,white) 01. (3) 11. (2) 01. (1) 00. (0) 01. Unfortunately that does not comply with your assumption, when one neighbour is occupied the cell well be empty afterwards. $\endgroup$ – Hendrik Jan Aug 17 at 16:12
1
$\begingroup$

The description given on the page you linked to is correct:

"In each case the base 2 digit sequence for the code number specifies the rule as follows. The last digit specifies what color the center cell should be if all its neighbors were white on the previous step, and it too was white. The second-to-last digit specifies what happens if all the neighbors are white, but the center cell itself is black. And each earlier digit then specifies what should happen if progressively more neighbors are black. (Compare page 60.)"

What you might be missing is that, if the rule number is odd, the empty lattice is unstable since white cells surrounded by other white cells will spontaneously turn black. Specifically, any rules whose number is congruent to 1 modulo 4 (i.e. whose binary form ends in 01), like 465, are "strobing", i.e. the empty lattice will alternate between all white and all black in each successive generation.

In particular, this means that rule 465 cannot correspond to "adding a cell when exactly one neighbor is currently occupied". (That would presumably be rule 686, or 1010101110 in binary.)

Instead, as you correctly note, 465 equals 111010001 in binary. Written in five groups of two bits each, that gives 01 11 01 00 01. In each of these groups the rightmost bit in group $k$ (numbered right-to-left from 0 to 4) is 1 if a white cell with $k$ black neighbors will turn black in the next generation, and the leftmost bit is 1 if a black cells with $k$ black neighbors will stay black.

This means that, under this rule, a white cell will turn black if it has 0, 2, 3 or 4 black neighbors (since the rightmost bit is 1 in groups 0, 2, 3 and 4 counting from the right) and a black cell will stay black if it has exactly 3 black neighbors (since the leftmost bit is 1 only in group 3).

And indeed, simulating this rule for 22 generations, starting from one black pixel on a white background, produces an image matching the one on the linked page.


Ps. It turns out that rule 465 is the "strobing equivalent" of the state-symmetric rule 558 = 010001011102, which differs from rule 686 by exactly one bit and can be described as "add a cell when exactly one neighbor is occupied, remove a cell when exactly one neighbor is empty".

Started from a single cell, it seems that rules 558 and 686 evolve identically, since from this starting point they apparently never generate a live cell with exactly three live neighbors. Thus, on even-numbered generations, the strobing rule 465 also looks identical to both of them.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ thank you for clearing that up! I had seen the construction of that specific form described elsewhere and I didn't realize that 465 was actually different and what had been described was actually 686. Also, the grouping of the the bits makes plenty of sense the way you describe it. Thanks! $\endgroup$ – billTavis Aug 17 at 19:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.