pithlessly
commented
3 years ago The first question is, which rule do I use? Not Conway's Game of Life, to be sure. I want to do something more novel.
The rule used by CGoL is abbreviated B3/S23: a dead cell is "born" if it has three living neighbors, and a living cell "survives" if it has two or three living neighbors. A cell's neighbors are regarded as the eight cells surrounding it, reachable by one step orthogonally or laterally, as if by a king's move in chess. This leads us to a broader classification of so-called Life-like cellular automata by varying which quantities of neighbors allow a dead cell to come alive, or a living cell to survive.
One could imagine creating a table:
| # of living neighbors | result, if the cell is alive | result, if the cell is dead |
|---|---|---|
| 0 | dead | dead |
| 1 | dead | dead |
| 2 | alive | dead |
| 3 | alive | alive |
| 4 | dead | dead |
| 5 | dead | dead |
| 6 | dead | dead |
| 7 | dead | dead |
| 8 | dead | dead |
| 9 | dead | dead |
A cell's state next generation depends on its previous state (two possibilities) and the total liveness of its neighbors (nine possibilities, from 0 to 8). A life-like rule maps each of these cases to one of two states, making a total of 2^18 = 262,144 possible life-like rules.
There are a myriad of ways to generalize Life further, but most of these generalizations will significantly expand the search space. 2^18 is already a lot, and I'd like to do something to narrow it instead:
- First, we can switch from the Moore neighborhood to the von Neumann neighborhood. This means cells are allowed to consider only the surrounding four cells reachable by one orthogonal step (like the movement of a general in Chinese chess).
- If we still let cells consider only the total liveness of their neighbors, this would give us 2^10 possible rules. However, we'll relax this, and let cells depend on their neighbors arbitrarily.
- This results in a massive explosion of possibilities: the number of distinct neighborhoods has increased from 5 to 2^4, so there are 2^32 total rules! To reduce this, let's deny cells the ability to look at their own previous state, reducing it to 2^16.
By doing this, we also introduce a lot of redundancy. For example, the rule "always copy the value of the left neighbor" and "always copy the value of the right neighbor" are considered different, but we don't really need to distinguish them. For any given rule, we could imagine obtaining essentially equivalent rules by:
- Rotating its view of the input by a quarter, half, or three-quarters of a turn;
- Reflecting its view of the input north-south, east-west, or along a diagonal;
- Inverting its view of the input, and also inverting its output (essentially renaming 0 to 1).
Note that not all of these actually result in new rules. For example, "always become 0, no matter what" already disregards its inputs, so the first two types of transformations won't do anything to it. Therefore, while we can generate a maximum of 2 * 8 = 16 variants, not all of the 2^16 rules are going to have this many variants. Luckily, 2^16 is a very manageable search space for a computer, so the next step is to write a program which gives us a representative rule from each group of variants. This should hopefully give us a search space of <10k, and we can look at each of these variants in more detail (e.g. how many elements it has).
dluman
This will be less of a novel and more of a textbook. Specifically, I want to create a reference guide describing the elements and reactions in an artificial chemistry.
I already have a general idea for how the chemistry should work: pick some cellular automaton rule, and let it play out in a 5x5 toroidal space. When you do this, you might find that some configurations end up as fixed points, while some configurations fall into cycles. We can call the stable patterns "elements," and the unstable patterns... um, just "unstable". For example, this is an element in Conway's Game of Life (a 2x2 block which happens to wrap around the edges):
You can "react" two elements A and B by placing them adjacent to each other; this might result in a 10x5 jointly stable configuration (call this a "compound"), and this compound might be irreducible, or it might decompose into two new elements. In the irreducible case, we say A + B → (AB), and in the reducible case, we say A + B → C + D.
As for the book itself: I'm not sure exactly how it should be structured. I could go with something a little like Theodore Gray's book Elements, which has a page-long, informal description of every element and its properties, along with images and a variety of more formal information (a few natural questions with this: how do I create images? how do I determine which formal properties are relevant? how can I create an informal description of these elements?) I'll probably rely more on reactions than elements for word count.