Клеточные автоматы

Как из трёх строчек правил рождаются раковины, эпидемии и вычислимая вселенная

Если ты возьмёшь раковину тропической улитки Conus textile — её ещё называют «тканевый конус» — и присмотришься, увидишь сетку треугольников, которые то распадаются, то снова собираются в острые узоры. Узор не нарисован клетка за клеткой и нигде не «записан» в виде картинки. Он рождается сам, по мере того как улитка строит раковину край за краем, а каждая клетка пигментного слоя на крае мантии решает, выделять ей сейчас краску или нет, глядя только на двух-трёх соседей слева и справа.

Это и есть клеточный автомат. Буквально живой, ползающий по океанскому дну.

Клеточный автомат — это математическая модель, у которой есть всего четыре составные части.

Пространство разбито на одинаковые клетки. Сетка может быть одномерной (просто линия), двумерной (квадраты, шестиугольники, треугольники) или даже трёхмерной. Чаще всего работают с квадратной 2D-сеткой.

Каждая клетка в каждый момент времени находится в одном из конечного числа состояний. В простейшем случае состояний всего два: «живая» и «мёртвая», «есть пигмент» и «нет», 0 и 1. Бывают модели с десятками состояний — например, в модели сердечной мышцы клетка может быть покоящейся, возбуждённой или находиться в одном из нескольких состояний рефрактерности.

Множество «соседей», на которых клетка смотрит, чтобы решить, что с ней произойдёт дальше. Обычно это либо окрестность фон Неймана (4 соседа: верх, низ, лево, право), либо окрестность Мура (8 соседей, включая диагонали).

Функция, которая по текущему состоянию клетки и состояниям её соседей выдаёт новое состояние. Правило одно и то же для всех клеток и не меняется со временем.

Самый простой клеточный автомат живёт на одной строке. Состояний два — чёрное и белое. Правило смотрит на тройку (левый сосед, сама клетка, правый сосед). У этой тройки восемь возможных значений (000, 001, 010, ..., 111), и для каждого значения правило указывает, чем стать клетке: 0 или 1. Восемь бит результата = одно число от 0 до 255. Получается ровно 256 разных правил, и каждое имеет свой номер: правило 30, правило 90, правило 110.

Стивен Вольфрам в 1980-х годах систематически перебрал все 256 правил и обнаружил, что они делятся на четыре класса.

Правило 30 знаменито вдвойне. Во-первых, оно генерирует последовательность настолько хаотичную, что Вольфрам долгое время использовал его как генератор псевдослучайных чисел в системе Mathematica. Во-вторых, биологи нашли тот же узор в природе — на раковинах Conus textile. Улитка не «знает» о существовании Вольфрама, но клетки её мантии, по всей видимости, реализуют что-то очень близкое к правилу 30.

Шаг в двумерность сделал в 1970 году британский математик Джон Конвей. Его «Игра Жизнь» — клеточный автомат на квадратной сетке с окрестностью Мура (8 соседей). Правила:

Три строчки. И из них рождается зоопарк, словарь которого занимает сотни страниц. Планер (glider) — пятиклеточная фигурка, ползущая по диагонали со скоростью одна клетка в четыре шага. Мигалка (blinker) — три клетки в ряд, превращающиеся в три клетки в столбик и обратно, осциллируя бесконечно. R-пентомино — пять клеток, из которых рождается хаос на тысячу с лишним шагов, после чего остаётся стабильная россыпь объектов. Пушка Госпера — конструкция, которая бесконечно стреляет планерами в одну сторону.

В 2010 году было показано, что в Жизни можно построить логические элементы AND, OR, NOT, регистры памяти и в принципе универсальный компьютер. Иначе говоря, Жизнь Тьюринг-полна: на ней теоретически можно запустить любую программу — в том числе и саму Игру Жизнь.

Клеточные автоматы — не игрушка. В современной биологии их используют как первое приближение всякий раз, когда нужно понять, как из локальных взаимодействий клеток рождается глобальное поведение ткани, органа или популяции.

Самый канонический пример. Раковины моллюсков растут наращиванием по краю, и пигментные клетки на этом крае подчиняются примерно тем же правилам, что и одномерный клеточный автомат. Узоры конусов, оливок, цимбиол моделируются с фотографической точностью. Окраска шкур млекопитающих (пятна жирафа, полосы зебры, узор гепарда) точнее описывается так называемой реакцией-диффузией Тьюринга, но дискретные клеточные автоматы дают похожие результаты и используются как удобное приближение.

Клетки сердечной мышцы — миокардиоциты — после возбуждения короткое время находятся в рефрактерном периоде, когда не реагируют на новые сигналы, потом снова чувствительны. Если возбудился сосед — клетка тоже возбудится. Из этого правила в норме рождается аккуратная плоская волна сокращения, которая прокатывается от предсердий к желудочкам. Но при сбое — например, после инфаркта — могут возникнуть спиральные волны, и это уже фибрилляция, при которой сердце вместо насосной работы хаотично трясётся. Клеточно-автоматные модели сердца помогают понять, почему дефибриллятор работает: разряд буквально «перезапускает» автомат, гася спираль. Те же спиральные волны наблюдают в коре головного мозга при эпилептических приступах и при мигренозной ауре.

Каждая клетка может быть в одном из трёх состояний: S (susceptible — здоров и восприимчив), I (infected — болен и заразен) или R (recovered — переболел и приобрёл иммунитет). Правила: S заражается, если рядом есть хотя бы один I. I через k шагов становится R. R уже не заражается. На сетке такая модель показывает, как болезнь расходится фронтом, как карантин (мёртвые клетки = изоляция) останавливает распространение, как влияет плотность населения и иммунная прослойка. В 2020 году пандемическое моделирование активно использовало именно такие модели.

Тот же SIR, но клетки — это деревья. Зелёная (живая), горит, сгорела. Лесники используют клеточно-автоматные модели для оценки пожароопасности и выбора мест для противопожарных просек. Те же модели работают для распространения инвазивных растений (борщевик, амброзия) и для расчёта эффективности заповедных коридоров.

Каждая клетка опухоли делится, конкурирует с соседями за кислород и питательные вещества, при недостатке умирает (некроз). Простейшая модель: клетка делится, если рядом есть хотя бы одно свободное место и достаточно «питания», иначе погибает. Из этих правил сами собой получаются формы, очень похожие на формы реальных опухолей: плотное ядро, активный пролиферативный край, центральный некроз. Такие модели помогают подбирать дозы и расписания химиотерапии и лучевой терапии.

Настоящая слизевая плесень — одноклеточный гигантский организм без нервной системы, который умеет решать оптимизационные задачи. Японские исследователи в 2010 году положили слизевика на влажную чашку, расставили овсяные хлопья в местах, где находятся станции токийского метро, и через несколько дней получили сеть, почти совпадающую со схемой реального токийского метро. Поведение Physarum хорошо моделируется клеточным автоматом, в котором слизевик выделяет хемоаттрактант, а тот диффундирует по соседним клеткам.

Самая молодая тема — с 2020 года. Идея: вместо того чтобы вручную писать правило, обучают нейронную сеть, которая работает как правило клеточного автомата. Цель — чтобы из одной начальной живой клетки автомат сам вырастил заданный рисунок (например, ящерицу или морскую звезду). Если рисунок повредить — отрезать ножку — автомат сам её регенерирует. Это математический прокси для понимания того, как настоящие живые ткани (саламандры, морские звёзды, гидры) умеют отращивать утраченные части тела. Если ты учишься на биолога, то это — одна из самых интересных тем, где встречаются клеточная биология, теория развития и машинное обучение.

Игра Жизнь в десять строк, через numpy:

import numpy as np

def step(grid):
    # считаем число живых соседей для каждой клетки сразу для всего поля
    n = sum(np.roll(np.roll(grid, dx, 0), dy, 1)
        for dx in (-1, 0, 1) for dy in (-1, 0, 1)
        if (dx, dy) != (0, 0))
    # правило Конвея в одну строку
    return ((n == 3) | ((grid == 1) & (n == 2))).astype(np.uint8)

# случайное стартовое поле 50x50 с плотностью 30%
grid = np.random.choice([0, 1], (50, 50), p=[0.7, 0.3]).astype(np.uint8)
for _ in range(100):
    grid = step(grid)
    print(grid.sum(), "живых клеток")

Правило 30 (одномерный автомат Вольфрама):

def wolfram(rule=30, width=80, steps=40):
    cells = [0] * width
    cells[width // 2] = 1
    for _ in range(steps):
        print("".join("\u2588" if c else " " for c in cells))
        new = []
        for i in range(width):
            l = cells[(i - 1) % width]
            m = cells[i]
            r = cells[(i + 1) % width]
            # индекс паттерна 0..7
            idx = (l << 2) | (m << 1) | r
            # вытаскиваем idx-й бит из номера правила
            new.append((rule >> idx) & 1)
        cells = new

wolfram(30)
wolfram(90)
wolfram(110)

Простейшая SIR-модель эпидемии на сетке:

import numpy as np

S, I, R = 0, 1, 2
N = 100

grid = np.zeros((N, N), dtype=np.int8)
grid[N // 2, N // 2] = I  # один пациент-ноль в центре
infected_steps = np.zeros((N, N), dtype=np.int16)
RECOVERY_TIME = 7

for day in range(50):
    new = grid.copy()
    for y in range(1, N - 1):
        for x in range(1, N - 1):
            if grid[y, x] == S:
                # окрестность фон Неймана
                neighbors = [grid[y-1, x], grid[y+1, x], grid[y, x-1], grid[y, x+1]]
                if I in neighbors and np.random.random() < 0.3:
                    new[y, x] = I
            elif grid[y, x] == I:
                infected_steps[y, x] += 1
                if infected_steps[y, x] >= RECOVERY_TIME:
                    new[y, x] = R
    grid = new
    print(day, np.sum(grid==S), np.sum(grid==I), np.sum(grid==R))

Этот кусочек кода уже даёт классическую эпидемиологическую кривую: число заражённых сначала растёт по экспоненте, потом достигает пика и начинает падать, когда вокруг заражённых остаются в основном переболевшие.

У клеточного автомата на конечной сетке состояний конечное число. Для поля 10×10 с двумя состояниями всех возможных конфигураций ровно 2¹⁰⁰ ≈ 10³⁰. Это много, но конечно. А значит, по принципу Дирихле автомат рано или поздно обязательно попадёт в состояние, в котором уже был, — и с этого момента всё пойдёт по кругу.

На практике для больших полей дождаться цикла не удаётся (состояний слишком много), но для малых — это рабочий алгоритм, и он лежит в основе многих задач олимпиадного уровня.
Попробуйте решить задачу Валера и дек, которая использует описанную идею.

Hans Meinhardt — The Algorithmic Beauty of Sea Shells. Главная книга по моделированию узоров на раковинах. Много картинок, простой математический язык, идеально для биолога, который не боится формул.

Stephen Wolfram — A New Kind of Science. Программное (и местами спорное) сочинение, в котором Вольфрам утверждает, что клеточные автоматы — это новая основа всей науки. Бесплатно доступна целиком на сайте wolframscience.com.

Distill.pub — Growing Neural Cellular Automata. Интерактивная статья 2020 года про нейронные клеточные автоматы. Можно прямо в браузере наблюдать, как из одной клетки вырастает ящерица, и тыкать в неё, чтобы посмотреть, как она регенерирует.

Конвей и Мартин Гарднер. Оригинальная колонка Гарднера про Игру Жизнь в журнале Scientific American за октябрь 1970 года — классика, которую стоит прочитать ради красивого языка.