Objectively classifying 2D cellular automata

[Plasmath]

Wolfram's classification for cellular automata kind of sucks (at least, when it comes to analyzing 2D rules). In principle, I think that the idea of classifying cellular automata into one of a few categories is a great idea, but I've got some problems with his system:

• It was meant for 1D rules. This is mentioned in the LifeWiki article, but this classification was intended for the 1D automata that Wolfram was analyzing. Extending it to 2D rules adds a lot of gray area and reduces its usefulness.
• It's hard to tell what class rules are in. Take B3/S as an example. Although soups in this rule technically have a chance of generating something other than the vacuum, the chance of this actually happening in a random soup is extremely low. Especially in INT rules, figuring out the difference between a class 1 rule and a class 2 rule can be difficult, even though both are well-defined.
• Figuring out what class a rule is in is subjective. In particular, distinguishing between class 2 and 4 automata and class 3 and 4 automata is pretty subjective. There is no defined line in the sand between being chaotic, having 'a mixture between order and randomness', and turning into simple ash. Soups in DryLife seem to have portions of both order and randomness to me, but it's placed into class 3 on the wiki.

The wiki also seems to list each CA as having one of three 'characters': chaotic, stable, or explosive. These also have the issue of lacking any formal definition (or at least not one that I can find, let me know if I'm wrong).

All of this is to say that I think we can do better! In my opinion this is a useful idea - I'm interested in hearing ideas of alternative classification methods, and I wanted to share an interesting (failed) attempt at a classification that I think could be a step in the right direction.

My attempt

The general idea here is to assign to each rule some collection of numerical values which represent the rule's dynamics in some way. These values correspond to some point in Euclidean space - let's call this the 'property space'. If we partition this space into several regions, then the rules can be divided into categories based on which region they lie in. Because rules with similar dynamics will be close together, they will generally be in the same region, and so similar rules should be grouped together.

Here are the two parameters, both ranging from 0-1, that I used in my simulation:

• Density: Starting from a random soup, what percentage of cells will be alive after a long time? Here a density of 0 means all cells are dead and a density of 1 means all cells are alive.
• Temperature: Starting from a random soup and simulating for a long time, what percentage of cells will change state on the next generation? Here a temperature of 0 means no cells change state after a long time, and a temperature of 1 means all of them do. Essentially soups will become more 'flickery' as temperature increases.

In an ideal world we could let the random soup be infinitely big and 'a long time' be infinitely long, but in reality we have to approximate. For my simulation, I created a random soup on a 500x500 toroidal grid and let it run for 3000 generations. The program then checks the density and temperature of the resulting pattern. For example, the simulation found that Life has a density of approximately 0.033 and a temperature of approximately 0.011.

I ran this simulation for all of the 131072 Life-like rules which don't have the B0 condition. This was done with some custom (and probably horribly inefficient) C# code which generated the soups & then simulated them on the GPU. After the processing is done we can visualize the results with a scatterplot. Here, each rule we simulated is represented by a point in property space, which is then plotted. This is what it looks like:

plot.png (1.01 MiB) Viewed 451 times

You can see that all the rules are located in a triangle (I've darkened the spaces where it's impossible for rules to be). Here, the left edge of the triangle represents all live cells dying at the end of each generation (e.g. B2/S), the right edge represents all dead cells becoming alive at the end of each generation, and the bottom edge represents a rule in which soups tend towards completely static patterns. It's kind of hard to see but there are many rules with very low temperature (like Life) which are near the bottom edge but are kind of obscured by the x-axis. The graph also nearly has mirror symmetry - this symmetry corresponds to mapping a rule to its complement, which must have the same temperature and the opposite density. This means that all self-complementary rules should lie on the vertical line x = 0.5.

I was hoping that the rules would group together into a few defined 'clumps'. If this was the case, it would lead to natural regions (one for each clump) as it means similar rules would very rarely be put into different regions. Unfortunately, that doesn't seem to be the case here. There does seem to be a 'phase transition' at some point where rules go from being very low temperature to being very high temperature (note how the region with temperature 0.1-0.2 is nearly empty), but other than that there doesn't seem to be any obvious categorization here. To me, this is a sign that a different set of parameters need to be used in order to give a truly 'natural' classification where rules fall into one of a few discrete clumps. If we can find a set of properties which does clump naturally for Life-like rules, it probably means it extends well to INT rules as well.

With that said, what ideas do you all have? Any ideas on different parameters to use for a simulation? Did I miss a natural way to divide this plot into regions? Or something completely different? Let me know your thoughts. I've also attached a JSON file of the data used for the above plot if you want to take a closer look.

data.zip

(1.17 MiB) Downloaded 4 times

[TheWayOfTheCon]

This is some neat information. On the graph, I would plot the locations of some example rules (Seeds, Life, Gems, etc.) to make it easier to understand which rules with certain conditions go where. I think it would also be nice to have a graph organized by the rules themselves and not their properties, if it would even be possible to graph that (maybe rule integers would work?)

[Plasmath]

On the graph, I would plot the locations of some example rules (Seeds, Life, Gems, etc.) to make it easier to understand which rules with certain conditions go where.

Here's a graph with some named (and a few unnamed) rules on it:

plot.png (1.14 MiB) Viewed 426 times

I can try making one of the axes the rule integer but that will take a bit more work to graph.

[actinophrys]

This is a really neat exercise. In absence of defined clusters, it might be interesting to see if other known properties relate to regions of the graph. Like you say, Wolfram's classification is not easy to apply, though certainly anything with B1 or B2 will be explosive. David Eppstein (2010) proposed two more rigorously defined categories:

1. Mortal, whether there are any finite patterns can die. This is equivalent to the complement of the S rules allowing p1s, so for instance B345/S013 is immortal because B345/S245678 has no p1s. Which rules allow them is not completely solved but it is known for the vast majority of rules.
2. Fertile, whether there are any finite patterns that will escape any given boundary box. This is harder to determine. However rules without any of B123 are definitely infertile, and then new-gliders.db gives a long list of rules that are known to have spaceships and so are definitely fertile. And possibly rules known to have spaceships are an interesting enough category on their own.

With things like this I also do wonder what happens if you start with soups that have other densities. Some explosive rules have a tendency to form stable patterns when the density is low, which presumably changes their temperature.

[NNlk05]

I've been saving up this idea for a long time now.
Here's the idea in pseudocode

Code: Select all

for(each OT non-B0 rule){ 
  run n d% fill soups on a x*y torus for t[0] ticks;
  record the state;
  for(each of the next t[1]generations) {
    check periodicity;
    if(periodic) {
      output current tick t;
    } else {
      continue to next tick;
    }
  }
}

I'll try to make it.
EDIT: LLM-made code

Code: Select all

## Definition
A Life-like cellular automaton (OT) is a CA meeting the following criteria:

the universe is a two-dimensional array of square cells,
each cell can be in one of two states (which are referred to as "alive" and "dead", or alternatively "on" and "off"),
the neighbourhood of each cell is the Moore neighbourhood,
the new state of a cell in the next generation can be expressed as a function of the current state of the cell and the number of alive neighbours of the cell; that is, the rule is outer totalistic (sometimes called semitotalistic).
This class of cellular automata is named for Conway's Game of Life, the most famous cellular automaton, which meets all above criteria. It is also common to refer to this rulespace as the "Life family" or to simply use phrases like "similar to Life".
## Pseudocode
```
for(each OT non-B0 rule){ 
  run n d% fill soups on a x*y torus for t[0] ticks;
  record the state;
  for(each of the next t[1]generations) {
    check periodicity;
    if(periodic) {
      output current tick t;
    } else {
      continue to next tick;
    }
  }
}
```
## Goal
Implent this code in CUDA, then plotting this as a PNG image. A Python harness may be used.

## Input
-n: n in the pseudocode
-d: d in the pseudocode
-x, -y: x and y in the pseudocode
-t <int> <int>: t[0] and t[1] in the pseudocode

Code: Select all

I'll provide you with a complete CUDA implementation for Life-like cellular automaton simulation with Python visualization. This is a substantial project, so I'll break it into components.

## Complete Implementation

### 1. CUDA Kernel (`ca_kernel.cu`)

```cuda
#include <cuda_runtime.h>
#include <curand_kernel.h>

// Rules stored as 9-bit bitmaps (index 0-8 represents neighbor count 0-8)
// bit i = 1 means the cell survives/births with i neighbors
struct CARule {
    unsigned char birth;   // bitmask for birth conditions
    unsigned char survive; // bitmask for survival conditions
};

__device__ int count_neighbors(unsigned char* grid, int x, int y, int width, int height) {
    int count = 0;
    for (int dy = -1; dy <= 1; dy++) {
        for (int dx = -1; dx <= 1; dx++) {
            if (dx == 0 && dy == 0) continue;
            
            int nx = (x + dx + width) % width;
            int ny = (y + dy + height) % height;
            int idx = ny * width + nx;
            
            if (grid[idx]) count++;
        }
    }
    return count;
}

__global__ void step_ca(
    unsigned char* current,
    unsigned char* next,
    int width,
    int height,
    CARule rule
) {
    int x = blockIdx.x * blockDim.x + threadIdx.x;
    int y = blockIdx.y * blockDim.y + threadIdx.y;
    
    if (x >= width || y >= height) return;
    
    int idx = y * width + x;
    int neighbors = count_neighbors(current, x, y, width, height);
    unsigned char cell_state = current[idx];
    unsigned char new_state = 0;
    
    if (cell_state) {
        // Cell is alive - check survival
        new_state = (rule.survive >> neighbors) & 1;
    } else {
        // Cell is dead - check birth
        new_state = (rule.birth >> neighbors) & 1;
    }
    
    next[idx] = new_state;
}

__global__ void init_grid(
    unsigned char* grid,
    int width,
    int height,
    float density,
    unsigned long seed
) {
    int x = blockIdx.x * blockDim.x + threadIdx.x;
    int y = blockIdx.y * blockDim.y + threadIdx.y;
    
    if (x >= width || y >= height) return;
    
    int idx = y * width + x;
    
    curandState state;
    curand_init(seed + idx, 0, 0, &state);
    
    grid[idx] = (curand_uniform(&state) < density) ? 1 : 0;
}

// Check if current state equals previous state (periodicity check)
__global__ void check_equal(
    unsigned char* a,
    unsigned char* b,
    int width,
    int height,
    int* result
) {
    int x = blockIdx.x * blockDim.x + threadIdx.x;
    int y = blockIdx.y * blockDim.y + threadIdx.y;
    
    if (x >= width || y >= height) return;
    
    int idx = y * width + x;
    
    if (a[idx] != b[idx]) {
        atomicCAS(result, 0, 1); // Mark as different
    }
}
```

### 2. Python Harness (`ca_simulator.py`)

```python
import argparse
import numpy as np
import pycuda.driver as cuda
import pycuda.autoinit
from pycuda.compiler import SourceFile
import struct
from PIL import Image
import os

class CASimulator:
    def __init__(self, width, height, cuda_module_path="ca_kernel.cu"):
        self.width = width
        self.height = height
        self.grid_size = width * height
        
        # Compile CUDA module
        self.module = SourceFile(cuda_module_path).get_module()
        self.step_kernel = self.module.get_function("step_ca")
        self.init_kernel = self.module.get_function("init_grid")
        self.check_equal_kernel = self.module.get_function("check_equal")
        
        # Allocate GPU memory
        self.current_grid = cuda.mem_alloc(self.grid_size)
        self.next_grid = cuda.mem_alloc(self.grid_size)
        self.equal_check = cuda.mem_alloc(4)
        
        # Thread block configuration
        self.block_size = (16, 16, 1)
        self.grid_blocks = (
            (width + self.block_size[0] - 1) // self.block_size[0],
            (height + self.block_size[1] - 1) // self.block_size[1],
            1
        )
    
    def init_random(self, density, seed=0):
        """Initialize grid with random configuration"""
        self.init_kernel(
            self.current_grid,
            np.int32(self.width),
            np.int32(self.height),
            np.float32(density),
            np.uint64(seed),
            block=self.block_size,
            grid=self.grid_blocks
        )
    
    def step(self, rule):
        """Execute one generation"""
        # Create rule structure
        birth = np.uint8(rule['birth'])
        survive = np.uint8(rule['survive'])
        rule_struct = np.array([(birth, survive)], 
                               dtype=[('birth', np.uint8), ('survive', np.uint8)])[0]
        
        self.step_kernel(
            self.current_grid,
            self.next_grid,
            np.int32(self.width),
            np.int32(self.height),
            rule_struct,
            block=self.block_size,
            grid=self.grid_blocks
        )
        
        # Swap grids
        self.current_grid, self.next_grid = self.next_grid, self.current_grid
    
    def is_equal(self, other_grid):
        """Check if current grid equals another grid"""
        cuda.memset_d32(self.equal_check, 0, 1)
        
        self.check_equal_kernel(
            self.current_grid,
            other_grid,
            np.int32(self.width),
            np.int32(self.height),
            self.equal_check,
            block=self.block_size,
            grid=self.grid_blocks
        )
        
        result = np.zeros(1, dtype=np.int32)
        cuda.memcpy_dtoh(result, self.equal_check)
        return result[0] == 0
    
    def get_grid(self):
        """Copy current grid to CPU"""
        grid_cpu = np.zeros(self.grid_size, dtype=np.uint8)
        cuda.memcpy_dtoh(grid_cpu, self.current_grid)
        return grid_cpu.reshape((self.height, self.width))
    
    def set_grid(self, grid_cpu):
        """Copy grid from CPU to GPU"""
        cuda.memcpy_htod(self.current_grid, grid_cpu.astype(np.uint8).flatten())
    
    def save_as_png(self, filename, scale=2):
        """Save current grid as PNG"""
        grid = self.get_grid()
        scaled_grid = np.repeat(np.repeat(grid, scale, axis=0), scale, axis=1)
        img_array = (scaled_grid * 255).astype(np.uint8)
        img = Image.fromarray(img_array, mode='L')
        img.save(filename)
    
    def cleanup(self):
        """Free GPU memory"""
        self.current_grid.free()
        self.next_grid.free()
        self.equal_check.free()


def generate_rules(exclude_b0=True):
    """Generate all Life-like rules"""
    rules = []
    for b in range(0, 512):  # 2^9 combinations for birth
        for s in range(0, 512):  # 2^9 combinations for survival
            if exclude_b0 and (b & 1):  # Skip B0 rules
                continue
            
            # Convert bitmask to notation
            birth_conditions = [i for i in range(9) if (b >> i) & 1]
            survive_conditions = [i for i in range(9) if (s >> i) & 1]
            
            rules.append({
                'name': f"B{''.join(map(str, birth_conditions))}/S{''.join(map(str, survive_conditions))}",
                'birth': b,
                'survive': s
            })
    
    return rules


def main():
    parser = argparse.ArgumentParser(description='Life-like Cellular Automaton Simulator')
    parser.add_argument('-n', type=int, required=True, help='Number of soups (initial configurations)')
    parser.add_argument('-d', type=float, required=True, help='Density percentage (0-100)')
    parser.add_argument('-x', type=int, required=True, help='Grid width')
    parser.add_argument('-y', type=int, required=True, help='Grid height')
    parser.add_argument('-t', type=int, nargs=2, required=True, metavar=('T0', 'T1'),
                        help='t[0] initial ticks, t[1] periodicity check ticks')
    parser.add_argument('-o', type=str, default='output', help='Output directory')
    parser.add_argument('--rule', type=str, help='Specific rule (e.g., B3/S23)')
    
    args = parser.parse_args()
    
    # Create output directory
    os.makedirs(args.o, exist_ok=True)
    
    density = args.d / 100.0
    t0, t1 = args.t[0], args.t[1]
    
    # Initialize simulator
    sim = CASimulator(args.x, args.y)
    
    # Get rules to simulate
    if args.rule:
        rules = [parse_rule(args.rule)]
    else:
        rules = generate_rules(exclude_b0=True)
        rules = rules[:10]  # Limit for demo - remove for full run
    
    results = []
    
    for rule_idx, rule in enumerate(rules):
        print(f"Testing rule {rule_idx+1}/{len(rules)}: {rule['name']}")
        
        for soup_idx in range(args.n):
            sim.init_random(density, seed=rule_idx * 1000 + soup_idx)
            
            # Run t0 generations
            for _ in range(t0):
                sim.step(rule)
            
            # Save initial state for periodicity check
            initial_state = cuda.mem_alloc(sim.grid_size)
            cuda.memcpy_dtod(initial_state, sim.current_grid, sim.grid_size)
            
            # Check periodicity in next t1 generations
            period = None
            for gen in range(1, t1 + 1):
                sim.step(rule)
                
                if sim.is_equal(initial_state):
                    period = gen
                    break
            
            if period:
                results.append({
                    'rule': rule['name'],
                    'soup': soup_idx,
                    'period': period
                })
                
                # Save example
                filename = os.path.join(args.o, f"{rule['name']}_soup{soup_idx}_period{period}.png")
                sim.save_as_png(filename)
            
            initial_state.free()
    
    # Print results
    print("\nPeriodic patterns found:")
    for r in results:
        print(f"  Rule: {r['rule']}, Soup: {r['soup']}, Period: {r['period']}")


def parse_rule(rule_str):
    """Parse rule string like 'B3/S23' into birth/survive bitmasks"""
    parts = rule_str.split('/')
    birth_str = parts[0][1:]  # Remove 'B'
    survive_str = parts[1][1:]  # Remove 'S'
    
    birth = sum(1 << int(c) for c in birth_str)
    survive = sum(1 << int(c) for c in survive_str)
    
    return {'name': rule_str, 'birth': birth, 'survive': survive}


if __name__ == '__main__':
    main()
```

### 3. Installation & Usage

```bash
# Install dependencies
pip install pycuda pillow numpy

# Compile and run
python ca_simulator.py -n 5 -d 50 -x 128 -y 128 -t 100 500 -o results
python ca_simulator.py -n 3 -d 25 -x 256 -y 256 -t 50 100 --rule B3/S23 -o conway_results
```

## Key Features

| Feature | Details |
|---------|---------|
| **CUDA Acceleration** | GPU-parallelized grid updates with neighbor counting |
| **Torus Topology** | Wrapping boundaries using modulo arithmetic |
| **Periodicity Detection** | Compares grid states using GPU memory comparison |
| **Flexible Rules** | Supports all B/S Life-like rules, excludes B0 |
| **PNG Visualization** | Scalable output with adjustable pixel size |
| **Batch Processing** | Tests multiple soups and rules efficiently |

## How It Works

1. **Initialization**: Random grids with specified density
2. **Warmup**: Run t[0] generations to reach attractor
3. **Periodicity Check**: Track if pattern repeats within t[1] generations
4. **Visualization**: Save PNG for found periodic patterns

**Note**: For production use on your GPU, adjust block size (currently 16×16) based on your GPU's compute capability, and enable full rule space by removing the `[:10]` limit on rules.

Running.

[Plasmath]

...

With things like this I also do wonder what happens if you start with soups that have other densities. Some explosive rules have a tendency to form stable patterns when the density is low, which presumably changes their temperature.

I tried this out with 5% soup density, and unfortunately it seems pretty similar. Most of the visible differences are found in the bottom part of the graph, which is now slightly more asymmetrical. There are some other differences, but it might be because I was running the simulation with less precision just because it took a while last time (now 400 generations with a 200x200 soup).

plot-lowdensity.png (82.63 KiB) Viewed 363 times

...I think it would also be nice to have a graph organized by the rules themselves and not their properties, if it would even be possible to graph that (maybe rule integers would work?)

Plotting gives these results. Certainly interesting-looking! Not sure what it means though, and rule integers unfortunately don't generalize well to INT rules.

plot-ruleinteger.png (133.32 KiB) Viewed 363 times

[TheWayOfTheCon]

Plotting gives these results. Certainly interesting-looking! Not sure what it means though, and rule integers unfortunately don't generalize well to INT rules.


plot-ruleinteger.png

I was hoping that plotting by rule integer would be more concise in relation to figuring out what rules share similar properties on the graph, but that wasn't the case. Life would fall in the 6,000 range.

I don't think there really is a good way to represent all rules on a graph, though.

[Rhombicubocta]

...

I don't think there really is a good way to represent all rules on a graph, though.

I disagree that there is not a good way to represent all rules on a graph. There is an almost periodic nature of the temperature and density by the rule integer and since the rule integer in base 2 tells you the transitions, the period would tell you about what transition effect those values. I think Discrete Fourier Transform might be good to look at considering rules with certain transition will repeat after a given power of 2. For instance rule integers divisible by 2 have S8.

Also how does this handle B0 given that an infinite number of cell change state every generation.
edit:
Apple Bottom came up with this system generalize rule integers however I do not know if it has the nice base 2 nature of the original rule integer system.

[unname4798]

TPT uses a different rule integer system. Every rule integer divisible by 2 doesn't have S0.

[actinophrys]

I tried this out with 5% soup density, and unfortunately it seems pretty similar. Most of the visible differences are found in the bottom part of the graph, which is now slightly more asymmetrical.

Thank you for trying this. I don't think it's necessarily a bad result to find your values are relatively independent of that starting parameter. It does seem like the ones that are changing tell you something interesting about that part of the chart though.

Like you say most rules fall into just two major regions, either "hot messes" like 3-4 life and Gems or "cold messes" like Vote and Assimilation. However there is also the line that Life, DryLife, and DotLife fall on, where temperature ≈ density < 0.3. I took a look at your data table and those are nearly all B3(45678) rules, and become a very prominent feature when just those are plotted. B(45678) rules overlap near the origin but otherwise are colder, and then rules with B1 or B2 all stay in the main region with density > 0.2.

This "thin but warm" line is a lot more populous on your low density plot, which means it also depends on the parameters you changed. I imagine the main one is how long you ran things. The rules in that region of the original chart typically show chaotic phases that take a long time to settle down, so presumably this line traces where they are still in the process of developing from hot messes to cold thin ash after that many generations.

[g0t0]

This is my classification:

The word 'pattern' following means finite pattern.

Class Θ: All patterns finally evolve to empty.
Class I: All patterns finally evolve to class I in Lifeline 2-2(still life) and there exist a still life.
Class II: All patterns finally evolve to class I or class II(oscillator) and there exist an oscillator.
Class III: All patterns finally evolve to class I or class II or class III(spaceship) and there exist a spaceship.
Class IV: All patterns finally evolve to class I or class II or class III or class IV(linear growth) and there exist a linear growth.
Class V: there exist a pattern that is Turing complete.

A problem:
For OT rules, is class V includes class IV?

[g0t0]

This is my classification:

The word 'pattern' following means finite pattern.

Class Θ: All patterns finally evolve to empty.
Class I: All patterns finally evolve to class I in Lifeline 2-2(still life) and there exist a still life.
Class II: All patterns finally evolve to class I or class II(oscillator) and there exist an oscillator.
Class III: All patterns finally evolve to class I or class II or class III(spaceship) and there exist a spaceship.
Class IV: All patterns finally evolve to class I or class II or class III or class IV(linear growth) and there exist a linear growth.
Class V: there exist a pattern that is Turing complete.

A problem:
For OT rules, is class V includes class IV?

Sorry, there is an issue in the definition.

Class V: Turing Complete with finite patterns.

[actinophrys]

Class V: Turing Complete with finite patterns.

A proper Turing machine requires some equivalent of limited memory, so if you require it to be finite then logically you need some form of infinite growth. You have that listed as the top spot on a hierarchy though and it doesn't always have to be. Life without death has linear growth and is even Turing complete if you allow infinite patterns (lines of unit cells), but does not have any oscillators or spaceships.

Another type of growth you skipped over is quadratic growth. This occurs with various patterns in Life, which then don't fall into any of the classes you named. In most rules though it isn't really a complex structure so much as the failure to produce stable patterns. For instance B2/S1 is not known to have any, not because everything dies like your class Θ but because everything that does not die explodes into endless chaos. (I haven't seen an actual proof there aren't any though.)

Rule B2/S0 on the other hand does allow still lifes, oscillators, spaceships, and linear growth, and again is known to be Turing complete if you allow infinite patterns. So in terms of what it is possible to build it is a lot like Life. But in terms of random patterns it is completely different since anything that is not stable tends to explode into quadratic growth. That kind of general behaviour is what Wolfram's classification and Plasmath's attempt to improve it are about.

[g0t0]

Oh, this is my another way:

1. Generating a randomized soup.
2. Run it for t tick(s).
3. Flip one cell on the origin soup.
4. Run the new soup for t tick(s).
5. Compare different cells between 2 soups.

And do it for many ts to draw a graph.

If a rule is explosive, the graph will look like a quadratic function.

Edit: How to write a script to calculate this?

Edit: I don't know why, but the graph of Life is about y=1.2x^2(1<=x<=240).

Edit: Oh, The value is not stable, golly said x=1000, y=8108(soup is not stable)

[g0t0]

Class V: Turing Complete with finite patterns.

Life without death has linear growth and is even Turing complete if you allow infinite patterns (lines of unit cells), but does not have any oscillators or spaceships.

I don't allow infinite patterns, because a infinite line can be replicator in Life, and B/S01245678 is Turing Complete but it is a boring rule.

Edit: B/S01234578

[speedydelete]

Life without death has linear growth and is even Turing complete if you allow infinite patterns (lines of unit cells), but does not have any oscillators or spaceships.

I don't allow infinite patterns, because a infinite line can be replicator in Life, and B/S01245678 is Turing Complete but it is a boring rule.

What about B2a/S? I believe that is Turing-complete on infinite grids, and it is a quite interesting rule...

There can just be separate sections for finite and infinite patterns, infinite patterns aren't inherently "bad".

[g0t0]

Life without death has linear growth and is even Turing complete if you allow infinite patterns (lines of unit cells), but does not have any oscillators or spaceships.

I don't allow infinite patterns, because a infinite line can be replicator in Life, and B/S01245678 is Turing Complete but it is a boring rule.

What about B2a/S? I believe that is Turing-complete on infinite grids, and it is a quite interesting rule...

There can just be separate sections for finite and infinite patterns, infinite patterns aren't inherently "bad".

Why it's interesting?