Что такое клеточный автомат
Клеточный автомат — это поле из клеток, каждая из которых находится в каком-то состоянии (здесь — жива или мертва) и меняется по шагам, называемым поколениями. На каждом шаге все клетки обновляются одновременно по одному и тому же правилу, которое учитывает только восемь соседей вокруг каждой клетки.
В «Жизни» нельзя выиграть или проиграть: вы выбираете начальную позицию, а остальное делают правила. Самое интересное в том, что из столь простых правил рождается очень сложное и непредсказуемое поведение, поэтому игру изучают в математике, информатике и даже биологии.
Правила простым языком
Для каждой клетки считают число живых соседей (восемь вокруг, включая диагональные) и применяют эти правила одновременно по всему полю:
- Живая клетка, у которой меньше двух живых соседей, умирает от одиночества.
- Живая клетка с двумя или тремя живыми соседями остаётся живой.
- Живая клетка, у которой больше трёх живых соседей, умирает от перенаселённости.
- В мёртвой клетке, у которой ровно три живых соседа, рождается жизнь.
Краткая запись этих правил — B3/S23: B (от birth, рождение) 3 означает, что клетка рождается при 3 соседях, а S (от survival, выживание) 23 — что выживает при 2 или 3. Альтернативные правила в инструменте используют ту же запись, например HighLife — это B36/S23, а «Семена» — B2/S.
Одно поколение, посчитанное вручную
Возьмите мигалку: три живые клетки в горизонтальный ряд. У центральной 2 живых соседа, поэтому она выживает. У крайних всего по 1 соседу, поэтому они умирают. В клетках прямо над центром и прямо под ним по 3 живых соседа (все три из ряда), поэтому там рождаются новые клетки. Результат: вертикальный ряд из трёх клеток.
В следующем поколении процесс повторяется, и ряд снова становится горизонтальным. Поэтому мигалка — осциллятор с периодом 2. Попробуйте то же самое с блоком, квадратом 2 × 2: у каждой клетки по 3 соседа, поэтому все выживают, а у пустых клеток нет ровно 3 живых соседей. Он не меняется никогда, поэтому такие фигуры называют «натюрмортами».
История: Конвей, Гарднер и журнал
Британский математик Джон Конвей придумал игру в 1970 году. Её популяризировал Мартин Гарднер в своей колонке о математических играх в журнале Scientific American, в октябрьском номере 1970 года, и с тех пор вокруг неё сложилось огромное сообщество энтузиастов, которые ищут и каталогизируют фигуры.
Со временем было доказано, что игра полна по Тьюрингу: при подходящих фигурах она в принципе может вычислить всё, что вычисляет компьютер. Это одна из причин её славы: неограниченная сложность из минимальных правил.
Семейства фигур и какие попробовать
Фигуры классифицируют по поведению. Все они есть в меню «Фигура» инструмента под такими названиями:
| Семейство | Фигура | Что делает |
|---|---|---|
| Натюрморт | Блок, Улей | Не меняется никогда: 4 клетки у блока, 6 у улья |
| Осциллятор | Мигалка, Жаба, Маяк | Период 2: начинает заново каждые 2 поколения |
| Осциллятор | Пульсар | Период 3, 48 клеток в начальной фазе |
| Осциллятор | Пентадекатлон | Период 15 |
| Космический корабль | Глайдер | 5 клеток; продвигается на 1 клетку по диагонали каждые 4 поколения |
| Космический корабль | Лёгкий космический корабль | Пересекает поле по прямой, период 4 |
| Ружьё | Планерное ружьё Госпера | Выпускает новый глайдер каждые 30 поколений |
| Начальный хаос | R-пентамино | 5 клеток, которым требуется 1103 поколения, чтобы стабилизироваться на бесконечной плоскости |
Ружьё Госпера нашёл Билл Госпер в 1970 году, и это было первое доказательство того, что популяция может расти без ограничений. Кроме перечисленных, в инструменте есть «Жёлудь» и «Крепкий орешек» — две маленькие фигуры, которые очень долго определяются.
Как пользоваться инструментом «Игра «Жизнь»»
- Коснитесь поля или проведите по нему, чтобы нарисовать живые клетки (чтобы убрать живую клетку, коснитесь её ещё раз), или выберите фигуру в меню «Фигура».
- Нажмите «Старт». Кнопкой «Одно поколение» вы продвигаетесь на один шаг, чтобы спокойно следить за развитием, а «Пауза» всё останавливает. Когда поле выбрано, можно пользоваться клавиатурой: пробел запускает или ставит на паузу, N делает один шаг, R заполняет случайно, C очищает.
- Настройте «Скорость», «Размер поля» и «Правило» и попробуйте «Случайно» (с «Плотностью случайной заливки»), чтобы начать с заполненного клетками поля. «Очистить» оставляет поле пустым.
- Включите «Окрашивать клетки по возрасту», чтобы увидеть, какие области дольше всего остаются стабильными. Вверху показаны поколение и число живых клеток, а инструмент сообщает, когда поле стабилизируется, входит в цикл или остаётся без жизни.
Всё считается на вашем устройстве, ничего не отправляется на сервер. Инструмент сохраняет в вашем браузере настройки (размер, скорость, правило), но не рисунок.
Эксперименты, которые стоит провести
- Загрузите глайдер и посчитайте, за сколько поколений он сдвигается на одну клетку по диагонали: за 4. При замкнутых краях он обходит поле кругом и появляется с другой стороны.
- Поставьте два глайдера на встречный курс и посмотрите, чем всё закончится: в зависимости от того, как они столкнутся, они могут уничтожить друг друга или оставить натюрморт.
- Загрузите ружьё Госпера на поле размером не меньше 48 × 48 и посчитайте, за какое время оно выпускает каждый глайдер: за 30 поколений.
- Загрузите R-пентамино на большое поле и сравните с замкнутыми краями и без них. На бесконечной плоскости оно стабилизируется за 1103 поколения, но на конечном поле результат меняется.
- Смените правило при том же рисунке. При «Семенах» (B2/S) каждая клетка умирает в каждом поколении, остаются только рождения, так что рисунок расширяется наружу; при «Лабиринте» (B3/S12345) появляются структуры вроде коридоров.
Ограничения конечного поля
Исходная игра идёт на бесконечной плоскости. У поля в инструменте фиксированный размер, поэтому то, что доходит до края, ведёт себя иначе: при замкнутых краях оно входит с противоположной стороны (поле превращается в своего рода бублик), а без замыкания гаснет у стены.
Поэтому большим фигурам нужно место (ружью Госпера требуется не менее 48 × 48), а некоторые, например R-пентамино, могут закончить иначе, чем на неограниченной плоскости. Если фигура не помещается, инструмент предложит выбрать поле побольше.
Частые вопросы
Каковы правила игры «Жизнь» Конвея?
Живая клетка с 2 или 3 живыми соседями остаётся живой; при меньше чем 2 она умирает от одиночества, а при больше чем 3 — от перенаселённости. В мёртвой клетке с ровно 3 живыми соседями рождается жизнь. Коротко: B3/S23.
Что означает B3/S23?
B — рождение (birth), S — выживание (survival). B3 значит, что клетка рождается при 3 живых соседях, а S23 — что выживает клетка с 2 или 3.
Что такое глайдер?
Это фигура из пяти клеток, которая движется по диагонали на одну клетку каждые 4 поколения. Самая известная фигура игры.
Кто изобрёл игру «Жизнь»?
Британский математик Джон Конвей в 1970 году. Мартин Гарднер рассказал о ней в том же году в журнале Scientific American.
Почему мой рисунок исчезает или застывает?
Это самое обычное дело: многие маленькие фигуры вымирают или стабилизируются за несколько поколений. Попробуйте другую начальную позицию, поле побольше или «Случайно».