О клеточных автоматах | Игра «Жизнь», Правило 30, Правило 110 и другие

Четыре основные части

Любой клеточный автомат состоит из одних и тех же четырёх частей. Сетка — пространство, в котором живут клетки. Это может быть одномерная линия, двумерная плоскость, как шахматная доска, или даже трёхмерное пространство. Состояния — то, какой может быть клетка. В простейшем случае клетка двоичная: чёрная или белая, 1 или 0. Окрестность — набор клеток, которые напрямую влияют на клетку. На квадратной сетке это обычно окрестность Мура — все восемь окружающих клеток — или окрестность фон Неймана — только север, восток, юг и запад. Правила — мозг автомата: логика, которая задаёт каждой клетке новое состояние. Например: если я жива, но у меня меньше двух живых соседей, я умираю от одиночества. Каждая клетка применяет одни и те же правила в один и тот же момент.

1. Игра «Жизнь» Конвея

Правила: B3/S23. Живая клетка выживает при 2 или 3 живых соседях. Мёртвая клетка оживает ровно при 3. Все остальные клетки в следующем поколении мертвы. Джон Конвей придумал её в 1970 году, а знаменитой её сделала колонка Мартина Гарднера в Scientific American. В ней возникают планеры, осцилляторы и космические корабли. В том же году Билл Госпер нашёл первое планерное ружьё — узор, который бесконечно выпускает новый планер каждые 30 поколений. «Жизнь» способна выполнять вычисления: планеры могут переносить сигналы и сталкиваться, как логические вентили. Но прежде всего она показывает, как из простых правил вырастает сложное поведение.

Планерное ружьё Госпера в игре «Жизнь» выпускает диагональный поток планеров — Планерное ружьё Госпера через 330 поколений. Отрисовано в PictorX.

2. Правило 30

Тип: одномерный элементарный клеточный автомат. Следующее состояние каждой клетки зависит от неё самой и двух её соседей, а каждое поколение рисуется новой строкой под предыдущей. Стивен Вольфрам представил Правило 30 в 1983 году. Начните с одной чёрной клетки, и оно вырастит хаотичный треугольник. Несмотря на детерминированное правило, оно выглядит случайным — настолько, что его средний столбец использовали как генератор псевдослучайных чисел. Такие же треугольники встречаются в окраске раковины моллюска Conus textile.

Треугольник Правила 30, выращенный из одной чёрной клетки: хаотичный справа и полосатый слева — Правило 30 из одной чёрной клетки, 224 поколения. Отрисовано в PictorX.

3. Правило 110

Тип: одномерный элементарный клеточный автомат, как Правило 30, но с другой таблицей из восьми ответов. Доказано, что Правило 110 вычислительно универсально: Мэттью Кук показал, что при подходящей первой строке оно может эмулировать любое вычисление, которое способен выполнить компьютер общего назначения. В нём есть движущиеся структуры, которые путешествуют по повторяющемуся фону и взаимодействуют при встрече. Именно эти столкновения доказательство использует как логику. Правило 110 показывает, как очень простые правила могут эмулировать произвольные вычисления.

Правило 110, выращенное из одной клетки справа и расходящееся влево вложенными треугольниками — Правило 110 из одной чёрной клетки у правого края. Отрисовано в PictorX.

4. Brian's Brain

Состояния: выключенное, включённое (возбуждённое) и рефрактерное. Правила: выключенная клетка включается, если включены ровно 2 соседа. Включённая клетка становится рефрактерной. Рефрактерная клетка выключается. Этот автомат придумал Брайан Сильверман. Поскольку после возбуждения клетка должна отдохнуть одно поколение, каждый импульс продолжает удаляться от того места, где он уже был. В результате возникает толпа самодвижущихся узоров, похожих на волны в возбудимых средах, например в нервной ткани или сердечной мышце; часто они выглядят живыми и органичными.

Brian's Brain расходится от случайного пятна: возбуждённые клетки жёлтые, угасающие следы фиолетовые — Brian's Brain через 70 поколений после случайного пятна, с угасающими следами. Отрисовано в PictorX.

5. Wireworld

Состояния: пустое, голова электрона, хвост электрона и проводник. Правила: голова становится хвостом, хвост становится проводником, а проводник становится головой, если ровно 1 или 2 его соседа — головы. Пустые клетки остаются пустыми. Wireworld тоже придумал Брайан Сильверман, в 1987 году. Клетки-проводники — это провода, а голова, за которой следует хвост, — электрон, бегущий по ним. Автомат может моделировать электронные схемы: петля провода с одним электроном — тактовый генератор, небольшая выемка — диод, а несколько клеток образуют логический вентиль. Внутри него построены целые компьютеры, например компьютер Wireworld Дэвида Мура и Марка Оуэна, который вычисляет простые числа.

Схема Wireworld с двумя тактовыми петлями, двумя диодами и вентилем XOR: синие и красные электроны на жёлтом проводе — Два тактовых генератора, два диода и вентиль XOR в Wireworld. Отрисовано в PictorX.

256 правил Вольфрама и четыре класса

Одномерная клетка с двумя соседями видит один из восьми узоров — от 111 до 000. Правило задаёт новое состояние для каждого из них, поэтому оно состоит из восьми битов, и всего существует 2⁸ = 256 элементарных правил. Прочитайте восемь ответов как двоичное число, и получите название правила: Правило 30 — это 00011110, а Правило 110 — 01101110. Стивен Вольфрам рассортировал правила по их поведению — от порядка к хаосу. 1. Класс 1 приходит к однородному состоянию. 2. Класс 2 приходит к устойчивым или повторяющимся структурам. 3. Класс 3 остаётся хаотичным и выглядит случайным, как Правило 30. 4. Класс 4 строит структуры, которые движутся и взаимодействуют на границе между порядком и хаосом, как Правило 110.

Рейтинг сложности

Игра «Жизнь» ★☆☆☆☆ · Правило 30 ★☆☆☆☆ · Brian's Brain ★★☆☆☆ · Wireworld ★★★★☆ · Правило 110 ★★★★★. Первые два объясняют себя, пока вы смотрите. Правило 110 прячет свои движущиеся структуры в повторяющемся фоне.

Самые красивые визуально

1. Brian's Brain · 2. Игра «Жизнь» Конвея · 3. Правило 30 · 4. Правило 110 · 5. Wireworld.

Самые важные математически

1. Правило 110 — за универсальность · 2. Игра «Жизнь» — за универсальность и эмерджентность · 3. Правило 30 — за хаос и случайность · 4. Wireworld — за цифровую логику · 5. Brian's Brain — за возбудимые системы.

В природе, физике и криптографии

Клеточные автоматы используют для моделирования сложных систем в природе, физике и криптографии. Идея восходит к Станиславу Уламу и Джону фон Нейману в 1940-х годах: они использовали сетку клеток, чтобы спроектировать машину, способную копировать саму себя. В реальном мире клеточные автоматы видны в окраске некоторых раковин, например Conus textile, чьи треугольники похожи на Правило 30, и в чешуе глазчатой ящерицы, которая переключается между зелёным и чёрным по правилу, близкому к клеточному автомату. Физики моделируют с их помощью течение газа, кучи песка и лесные пожары. Кажущаяся случайность Правила 30 сделала его кандидатом для генераторов случайных чисел и потоковых шифров.

Исследуйте в PictorX

Откройте «Клеточные автоматы», чтобы запустить все пять. Посмотрите на планерное ружьё, флотилию космических кораблей или R-пентамино, которому нужно 1103 поколения, чтобы успокоиться. Введите любое правило «Жизни», например B36/S23, или любой номер элементарного правила от 0 до 255. Рисуйте и стирайте клетки, отправляйте электроны по схемам Wireworld, замыкайте края и включайте разноцветный режим. Сохраните PNG или откройте холст в редакторе PictorX.

Часто задаваемые вопросы

Что такое клеточный автомат?

Сетка клеток, в которой у каждой клетки есть состояние. На каждом такте все клетки обновляются вместе по одному фиксированному правилу, которое смотрит только на клетку и её соседей. Несмотря на простые правила, узоры могут быть сложными и непредсказуемыми.

Кто изобрёл клеточные автоматы?

Станислав Улам и Джон фон Нейман в 1940-х годах в Лос-Аламосе. Игра «Жизнь» Джона Конвея (1970) сделала идею популярной, а Стивен Вольфрам изучал 256 элементарных правил в 1980-х.

Какие клеточные автоматы полны по Тьюрингу?

Из пяти представленных здесь универсальность доказана для Правила 110 и игры «Жизнь», а в Wireworld можно разместить целый компьютер. Универсальность означает, что при правильном начальном узоре автомат может выполнить любое вычисление, доступное компьютеру общего назначения.

Что такое четыре класса Вольфрама?

Класс 1 угасает до однородного состояния, класс 2 приходит к устойчивым или повторяющимся структурам, класс 3 остаётся хаотичным, как Правило 30, а класс 4 строит движущиеся, взаимодействующие структуры, как Правило 110.

Почему Правило 30 выглядит случайным?

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