[Vm-dev] Tangential: A Lisp Interpreter Implemented in Conway's Game of Life

[Stéphane Rollandin]

> I can not map 
> that implementation to the rules of the game... Can someone explain to 
> me or point me to a paper/description of why that implementation works?

There is the Byte paper, around
https://archive.org/details/byte-magazine-1981-08/page/n205/mode/2up?view=theater

The figure there shows how ancilliary forms are used to count, in 
parallel, the number of neighbors for each point in the pattern.

For each direction in the Moore neighborood, the pattern is shifted and 
these eight shifted grids are combined together.

This is an addition in base two, and we need to count up to eight, so 
the algorithm uses three forms (nbr1, nbr2 and nbr4) to store the 
corresponding bits, and two other forms (carry2 and carry4) to store the 
bits carried from one bit to the next (so here from nbr1 to nbr2, and 
from nbr2 to nbr4), just as you need to do when performing an addition 
by hand.

The last step (the last four lines in #nextLifeGeneration from the Byte 
paper) generates the next pattern from nbr1, nbr2 and nbr4. The rules of 
the Game of Life are encoded here in the successive combination rules, 
in a nifty and quite obfuscated way that I did not even tried to 
comprehend.

Stef