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

Планерное ружьё Госпера в клеточном автомате «Жизнь»

Кле́точный автома́т — дискретная модель, изучаемая в математике, теории вычислимости, физике, теоретической биологии и микромеханике. Основой является пространство из прилегающих друг к другу клеток (ячеек), образующих решётку. Каждая клетка может находиться в одном из конечного множества состояний (например, 1 и 0). Решётка может быть любой размерности, бесконечной или конечной, для решётки с конечными размерами часто предусматривается закольцованность при достижении предела (границы). Для каждой клетки определено множество клеток, называемых окрестностью. Например, окрестность фон Неймана ранга 2 включает все клетки на расстоянии не более 2 от текущей. Устанавливаются правила перехода клеток из одного состояния в другое. Обычно правила перехода одинаковы для всех клеток. Один шаг автомата подразумевает обход всех клеток и на основе данных о текущем состоянии клетки и её окрестности определение нового состояния клетки, которое будет у неё при следующем шаге. Перед стартом автомата оговаривается начальное состояние клеток, которое может устанавливаться целенаправленно или случайным образом.

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

История

Станислав Улам, работая в Лос-Аламосской национальной лаборатории в 1940-е годы, изучал рост кристаллов, используя простую решёточную модель. В это же время Джон фон Нейман, коллега Улама, работал над проблемой самовоспроизводящихся систем. Первоначальная концепция фон Неймана основывалась на идее робота, собирающего другого робота. Такая модель известна как кинематическая. Разработав эту модель, фон Нейман осознал сложность создания самовоспроизводящегося робота и, в частности, обеспечения необходимого «запаса частей», из которого должен строиться робот. Улам предложил фон Нейману использовать более абстрактную математическую модель, подобную той, что Улам использовал для изучения роста кристаллов. Таким образом возникла первая клеточно-автоматная система. Подобно решётке Улама, клеточный автомат фон Неймана двухмерный, а самовоспроизводящийся робот описан алгоритмически. Результатом явился универсальный конструктор, работающий «внутри» клеточного автомата с окрестностью, включающей непосредственно прилегающие клетки, и имеющего 29 состояний. Фон Нейман доказал, что для такой модели существует паттерн, который будет бесконечно копировать самого себя.

Также в 1940-е годы, Норберт Винер и Артуро Розенблют (англ. Arturo Rosenblueth) разработали клеточно-автоматную модель возбудимой среды. Целью было математическое описание распространения импульса в сердечных нервных узлах. Их оригинальная работа продолжает цитироваться в современных исследованиях по аритмии и возбудимым средам.

В 1960-е годы клеточные автоматы изучались как частный тип динамических систем, и впервые была установлена их связь с областью символьной динамики. В 1969 году Г. А. Хедланд (англ. Gustav A. Hedlund) провёл обзор результатов, полученных в этом направлении. Наиболее значимым результатом явилось описание набора правил клеточного автомата как множества непрерывных эндоморфизмов в сдвиговом пространстве.

В 1970-е получила известность двухмерная клеточно-автоматная модель с двумя состояниями клеток, известная как игра «Жизнь». Изобретённая Джоном Конвеем и популяризованная Мартином Гарднером, она использует следующие правила: на квадратной решётке каждая клетка имеет 8 соседей; если клетка имеет двух «живых» соседей, она остаётся в прежнем состоянии. Если клетка имеет трёх «живых» соседей, она переходит в «живое» состояние. В остальных случаях клетка «умирает». Несмотря на свою простоту, система проявляет огромное разнообразие поведения, колеблясь между хаосом и порядком. Одним из феноменов игры «Жизнь» являются глайдеры — сочетания клеток, «движущиеся» по сетке как единое целое и взаимодействующие с другими статичными или подвижными конструкциями. Возможно установить стартовое состояние клеток, при котором глайдеры будут выполнять некоторые вычисления. Впоследствии было доказано, что игра «Жизнь» может полностью эмулировать универсальную машину Тьюринга. 11-го ноября 2002 года Пауль Чепмен (англ. Paul Chapman) построил вариант «Жизни», который является РММ (Регистровой Машиной Минского). Первая версия образца была большой (268’096 живых ячеек на площади 4,558 x 21,469 клеток) и медленной (20 поколений/сек при использовании Life32 Иогана Бонтеса (англ. Johan Bontes) на 400 MHz AMD K6-II). Таким образом было доказано, что в игре «Жизнь» можно выполнить любой вычислительный алгоритм.

В 1969 году немецкий инженер Конрад Цузе опубликовал книгу «Вычислимый космос», где выдвинул предположение, что физические законы дискретны по своей природе, и что вся Вселенная является гигантским клеточным автоматом. Это была первая книга из области, называемой сейчас цифровой физикой.

В СССР профессор В. З. Аладьев опубликовал ряд работ по теории клеточных автоматов. Как обобщающий использовался термин «однородные структуры». Была предложена и другая терминология для описания отдельных аспектов данной проблематики. Одну из его с соавторами книг по клеточным автоматам BookAuthority включила в список 100 лучших электронных книг всех времён по дискретной математике.

В 1983 Стивен Вольфрам опубликовал первую из серии статей, исследующих элементарные клеточные автоматы . Неожиданная сложность поведения этих простых одномерных автоматов привела Вольфрама к предположению, что сложность естественных систем обусловлена сходным механизмом. Кроме того, в течение этого периода Вольфрам формулирует концепцию истинной случайности и вычислительной неприводимости, и выдвигает предположение, что автомат с «правилом 110» может быть универсальным (полным по Тьюрингу). Это доказал в 1990 году его ассистент Мэтью Кук.

В 1987 году Брайан Сильверман (англ. Brian Silverman) предложил клеточный автомат Wireworld.

В 2002 году Вольфрам публикует 1280-страничный текст «Наука нового типа» (A New Kind of Science), где широко аргументирует, что достижения в области клеточных автоматов не являются изолированными, но весьма устойчивы и имеют большое значение для всех областей науки.

Математическое определение

Двумерный клеточный автомат можно определить как множество конечных автоматов на плоскости, помеченных целочисленными координатами (i, j), каждый из которых может находиться в одном из состояний $\sigma _{i,j}$:

$\sigma _{i,j}\in \Sigma \equiv \{0,1,2...k-1,k\}$.

Изменение состояний автоматов происходит согласно правилу перехода

$\sigma _{i,j}(t+1)=\phi (\sigma _{k,l}(t)|(k,l)\in {\mathcal {N}}(i,j))$,

где ${\mathcal {N}}(i,j)$ — некоторая окрестность точки $(i,j)$. К примеру, окрестность фон Неймана определяется как

${\mathcal {N}}_{N}^{1}(i,j)=\{(k,l)|~|i-k|+|j-l|\leq 1\}$,

а окрестность Мура

${\mathcal {N}}_{M}^{1}(i,j)=\{(k,l)|~|i-k|\leq 1,|j-l|\leq 1\}$.

Число всех возможных правил перехода определяется числом состояний $\sigma$ и количеством соседей n и составляет

$N_{r}=\sigma ^{\sigma ^{n}}$

Классификация

Классификация по типам поведения

Правило 40 (Класс 1) со случайными начальными условиями. Как видно, информация быстро исчезает в этой системе.

Правило 3 (Класс 2) со случайными начальными условиями. Очевидно появление периодических структур

Правило 18 (Класс 3) со случайными начальными условиями. Видно, что начальные условия порождают хаотические движения внутри системы.

Правило 193 (Класс 4) со случайными начальными условиями. Можно увидеть порождение устойчивых структур (колонка белых треугольников) и взаимодействие таких структур в других частях изображения.

Стивен Вольфрам в своей книге A New Kind of Science предложил 4 класса, на которые все клеточные автоматы могут быть разделены в зависимости от типа их эволюции. Классификация Вольфрама была первой попыткой классифицировать сами правила, а не типы поведения правил по отдельности. В порядке возрастания сложности классы выглядят следующим образом:

• Класс 1: Результатом эволюции начальных условий является быстрый переход к гомогенной стабильности. Любые негомогенные конструкции быстро исчезают.
• Класс 2: Результатом эволюции начальных условий является быстрый переход в неизменяемое негомогенное состояние либо возникновение циклической последовательности. Большинство структур начальных условий быстро исчезает, но некоторые остаются. Локальные изменения в начальных условиях оказывают локальный характер на дальнейший ход эволюции системы.
• Класс 3: Результатом эволюции почти всех начальных условий являются псевдо-случайные, хаотические последовательности. Любые стабильные структуры, которые возникают почти сразу же уничтожаются окружающим их шумом. Локальные изменения в начальных условиях оказывают неопределяемое влияние на ход эволюции системы.
• Класс 4: Результатом эволюции являются структуры, которые взаимодействуют сложным образом с формированием локальных, устойчивых структур. В результате эволюции могут получаться некоторые последовательности Класса 2, описанного выше. Локальные изменения в начальных условиях оказывают неопределяемое влияние на ход эволюции системы. Некоторые клеточные автоматы этого класса обладают свойством универсальности по Тьюрингу, что доказано для Правила 110 и игры «Жизнь».

Такого рода определения носят по большей части качественный характер и их можно по-разному интерпретировать. Вот что Вольфрам говорит об этом:

Практически при всякой попытке классификации будут возникать ситуации, когда по одному свойству предмет можно отнести к одному классу, а какому-либо другому свойству — к другому классу. Такая же ситуация и с клеточными автоматами: встречаются правила, которые показывают свойства, присущие одновременно одному и другому классу.

Оригинальный текст (англ.)

...with almost any general classification scheme there are inevitably cases which get assigned to one class by one definition and another class by another definition. And so it is with cellular automata: there are occasionally rules...that show some features of one class and some of another.

Тоталистичные клеточные автоматы

Существует специальный класс клеточных автоматов, называемых тоталистичными. На каждом шаге эволюции клеточного автомата значение клетки равно какому-либо целому числу (обычно выбираемого из конечного множества), а новое состояние клетки определяется суммой значений клеток-соседей и, возможно, предыдущим состоянием клетки. Если состояние клетки на новом шаге зависит от её предыдущего состояния, то такой клеточный автомат называется внешним тоталистичным. Игра Жизнь является примером внешнего тоталистического клеточного автомата с набором значений ячеек ${0,1}$.

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

Связанные определения клеточных автоматов

Существует множество возможных обобщений концепций клеточных автоматов.

Клеточный автомат, работающий на сетке, компонентами которой являются шестиугольники, а не квадраты (правило 34/2)

Один из них — использование сетки не с квадратами (гиперкубами в многомерном случае), а с другими геометрическими фигурами в её основе. Например, если поле представлено шестиугольным паркетом, то шестиугольники будут клетками. Однако иногда такие клеточные автоматы оказывались идентичными клеточным автоматам на сетке с квадратными клетками, только при этом было необходимо ввести специальные правила отношений с клетками-соседями. Другой способ обобщения — использование нерегулярной сетки (например, в виде Мозаики Пенроуза).

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

Определение соседства клетки может меняться с течением времени и/или пространства. Например, на первом шаге соседями будут горизонтально смежные клетки, а на другом — вертикально смежные.

В клеточных автоматах на новое состояние клетки не влияют новые состояния смежных клеток. Правило можно поменять: можно сделать так, что, например, в блоках 2 на 2 состояния клеток зависят от состояния клеток внутри блока и от таких же смежных блоков.

Существуют непрерывные клеточные автоматы. В таких системах вместо дискретного набора состояний используются непрерывные функции (обычно определяемые на промежутке $[0,1]$).

Свойство обратимости

Основная статья: Обратимый клеточный автомат

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

Для одномерных клеточных автоматов существуют алгоритмы определения обратимости или необратимости. Однако для клеточных автоматов с двумя и более измерениями таких алгоритмов нет.

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

Элементарные клеточные автоматы

Основная статья: Элементарный клеточный автомат

Простейшим нетривиальным клеточным автоматом будет одномерный клеточный автомат с двумя возможными состояниями, а соседями клетки будут смежные с ней клетки. Такие автоматы называются элементарными. Три клетки (центральная, её соседи) порождают $2^{3}=8$ комбинаций состояний этих трёх клеток. Далее на основе анализа текущего состояния тройки принимается решение о том, будет ли центральная клетка белой или чёрной на следующем шаге. Всего существует $2^{8}=256$ возможных правил. Эти 256 правил кодируются в соответствии с кодом Вольфрама — стандартному соглашению, правилу, которое было предложено Вольфрамом. В некоторых статьях эти 256 правил были исследованы и сравнены. Наиболее интересными представляются правила с номерами 30 и 110. На двух изображениях ниже представлены эволюции указанных правил. Начальное условие для каждого автомата — одна центральная клетка — чёрная, остальные — белые. По оси $Y$ откладывается дискретное время, а по оси $X$ откладываются состояния клеток автомата.

Правило 30

Правило 30

Текущее состояние	111	110	101	100	011	010	001	000
Новое состояние центральной клетки	0	0	0	1	1	1	1	0

Правило 110

Правило 110

Текущее состояние	111	110	101	100	011	010	001	000
Новое состояние центральной клетки	0	1	1	0	1	1	1	0

Правило 161

Правило 161

Текущее состояние	111	110	101	100	011	010	001	000
Новое состояние центральной клетки	1	0	1	0	0	0	0	1

Правило 30 проявляет поведение класса 3, что означает, что эволюция простых начальных условий приводит к хаотической, кажущейся случайной динамике.

Правило 110, как и игра «Жизнь» проявляет поведение класса 4, которое не является полностью случайным, но при этом отсутствует периодичность. При этом возникают структуры, которые взаимодействуют друг с другом неочевидным, сложным образом. Во время написания книги A New Kind of Science ассистент Стивена Вольфрама Мэттью Кук в 1994 году доказал, что некоторые из порождаемых правилом структур достаточно разнообразны, чтобы обладать полнотой по Тьюрингу. Этот факт представляет собой интерес, потому что в своей сути Правило 110 является простой одномерной системой. Также это хороший аргумент в пользу того, что системы класса 4 являются в некотором смысле универсальными. Мэттью Кук представил своё доказательство на конференции Института Санта-Фе в 1998 году, но Вольфрам запретил включать это доказательство в бумажную версию материалов конференции, потому что не хотел, чтобы оно было опубликовано до издания книги A New Kind of Science. В 2004 году доказательство Кука было опубликовано в журнале Вольфрама «Complex Systems»(выпуск 15, том 1), через 10 лет после того как Кук впервые представил его. Правило 110 было основой для построения наименьших Тьюринг-машин.

Правило 161 порождает фрактальные структуры, которые можно увидеть на рисунке. Можно видеть вложенные подобные треугольники.

Пространство правил клеточных автоматов

Простейший одномерный клеточный автомат задается с помощью восьми бит. Таким образом, все правила клеточного автомата располагаются на вершинах 8-мерного единичного куба. Такой гиперкуб является пространством всех возможных одномерных клеточных автоматов. Для одномерного клеточного автомата, где соседями одной клетки являются соседи её соседей необходимо $2^{5}=32$ бита и пространством всех возможных правил будет 32-мерный единичный куб. Расстоянием между двумя клеточными автоматами может считаться количество шагов, необходимых для того, чтобы перейти от одного правила к другому по ребрам многомерного куба. Такое расстояние называется расстоянием Хэмминга.

Исследования пространства правил клеточных автоматов позволяет ответить нам на вопрос, который ставится следующим образом: близко ли расположены относительно друг друга правила, которые порождают похожие друг на друга(в плане динамики) клеточные автоматы. Графическое представление гиперкуба высокой размерности на двумерной плоскости — весьма сложная задача. Однако на двумерной плоскости можно легко представить процесс эволюции одномерного клеточного автомата. При этом по одной оси откладывается дискретное время, а по другой — соответствующие состояния клеточного автомата. В случае двумерного клеточного автомата можно добавить третью ось. При этом две оси будут соответствовать состояниям клеточного автомата, а третья — дискретному времени. Процесс эволюции такого автомата представляет собой некоторую трехмерную фигуру в пространстве. Подробнее такие эксперименты описаны в книге Стивена Вольфрама A New Kind of Science. Исследования показали, что клеточные автоматы, классифицированные как класс 1, имели меньшее количество единичных бит в строке правила и они были сконцентрированы примерно в одном месте на гиперкубе. В то же время правила класса 3 имели большее (порядка 50 %) количество единичных бит.

Для пространств правил клеточных автоматов большей размерности было показано, что правила класса 4 расположены между классами 1 и 3.

Это наблюдение приводит к понятию грани хаоса применительно к теории клеточных автоматов и напоминает понятие фазового перехода в термодинамике.

Клеточные автоматы в естественной среде

Узор на поверхности раковины Conus textile формируется по механизму клеточного автомата

Некоторые живые организмы проявляют свойства клеточных автоматов. Раскраска раковин ряда морских моллюсков, например, родов Conus или Cymbiola, генерируется естественным одномерным клеточным автоматом, результат эволюции которого похож на Правило 30. Их пигментные клетки располагаются тонкой полоской вдоль края раковины. Секреция пигмента каждой клетки зависит от активирующей и ингибиторной активности соседних клеток. В процессе роста раковины полоса клеток формирует цветной узор на её поверхности. Окраска чешуек ящерицы Timon lepidus описывается стохастическим клеточным автоматом.

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

Нейронные сети также могут быть использованы как клеточные автоматы. Сложный движущийся узор на коже головоногих является отражением паттернов активирования в мозгу животных.

Компьютерное моделирование реакции Белоусова — Жаботинского в тонком слое жидкости в чашке Петри.

Реакция Белоусова — Жаботинского представляет собой пространственно-временной химический осциллятор, который может быть смоделирован клеточным автоматом. В 1950-х годах А. М. Жаботинский, продолжая работу Б. П. Белоусова, обнаружил, что тонкий однородный слой смеси определённых химических веществ способен образовывать движущиеся геометрические узоры, такие как концентрические круги и спирали.

Клеточные автоматы также используются в моделировании экосистем и популяционной динамики.

Применения клеточных автоматов

Компьютерные процессоры

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

Криптография

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

Моделирование физических процессов

Клеточные автоматы используются в компьютерном моделировании процессов рекристаллизации.

Фундаментальная физика

Основные статьи: Цифровая физика и Цифровая философия

Как указывает Andrew Ilachinski в своей книге Клеточные автоматы (оригинальное название — Cellular Automata), многие исследователи задавались вопросом является ли наша вселенная клеточным автоматом. Andrew Ilachinski указывает, что смысл этого вопроса может быть понят лучше с помощью простого наблюдения, которое можно произвести следующим образом. Рассмотрим эволюцию Правила 110: если бы это было что-то вроде «инопланетной физики» (оригинал — alien physics), то как можно было бы описать возникающие закономерности? Если бы вы не знали, как получены конечное изображение эволюции автомата, вы могли бы предположить, что данный рисунок отражает некоторым образом движение каких-либо частиц. Тогда делается следующее предположение: возможно, наш мир, хорошо описываемый физикой элементарных частиц, может быть клеточным автоматом на фундаментальном уровне.

Однако, законченная теория, базирующаяся на этих утверждениях все ещё далека от того, чтобы считаться законченной (равно как и сколько-нибудь общепринятой). Увлекаясь и развивая эту гипотезу, исследователи приходят к интересным заключениям, как можно использовать эту теорию для описания мира вокруг. Марвин Минский, пионер ИИ, разработал способ для изучения взаимодействия частиц с помощью четырёхмерного клеточного автомата. Конрад Цузе, известный как создатель первого действительно работающего программируемого компьютера Z3 занимался клеточным автоматами на нерегулярных решетках для исследования вопроса информационного содержания частиц. Эдвард Фредкин представил то, что он называет «гипотезой конечной вселенной» (оригинал — finite nature hypothesis). Смысл гипотезы заключается в том, что

…всякая величина в физике, включая время и пространство, является конечной и дискретной.

Оригинальный текст (англ.)

ultimately every quantity of physics, including space and time, will turn out to be discrete and finite.

Фредкин и Вольфрам — последовательные приверженцы цифровой физики.

Нобелевский лауреат Герард ’т Хоофт разработал интерпретацию квантовой механики, основывающуюся на клеточных автоматах.

См. также

Специфические правила

• Муравей Лэнгтона
• Правило 184

Рассматриваемые проблемы

• Задача синхронизации стрелков

Связанные статьи

• Теория автоматов
• Циклический клеточный автомат
• Метод подвижных клеточных автоматов
• Окрестность (теория графов)

Ссылки

• Тоффоли Т., Марголус Н. Машины клеточных автоматов. — М.: «Мир», 1991. ISBN 5-03-001619-8
• Life Universal Computer Архивная копия от 8 декабря 2006 на Wayback Machine
• Wolfram S. «New Kind of Science» Архивная копия от 8 мая 2007 на Wayback Machine
• англоязычный сайт с массой информации по КА, обновляется Tim Tyler см. usenet: comp.theory.cell-automata Архивная копия от 12 октября 2007 на Wayback Machine
• Usenet конференция по КА
• КА в математической энциклопедии WolframMathWorld Архивная копия от 26 марта 2008 на Wayback Machine
• Ванаг В. К. Исследование пространственно распределённых динамических систем методами вероятностного клеточного автомата (рус.) // Успехи физических наук : журнал. — Российская академия наук, май 1999. — Т. 169, № 5. — С. 481—505.
• Линейный клеточный автомат, эквивалентность машине Тьюринга Архивная копия от 17 июля 2014 на Wayback Machine
• Аристов А. О. Теория квазиклеточных сетей: научная монография — М: МИСиС, 2014. — 188 с. ISBN 978-5-600-00321-7