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

Станислав Улам, работая в Лос-Аламосской национальной лаборатории в 1940-е годы, изучал рост кристаллов, используя простую решёточную модель[1]. В это же время Джон фон Нейман, коллега Улама, работал над проблемой самовоспроизводящихся систем. Первоначальная концепция фон Неймана основывалась на идее робота, собирающего другого робота. Такая модель известна как кинематическая. Разработав эту модель, фон Нейман осознал сложность создания самовоспроизводящегося робота и, в частности, обеспечения необходимого «запаса частей», из которого должен строиться робот. Улам предложил фон Нейману использовать более абстрактную математическую модель, подобную той, что Улам использовал для изучения роста кристаллов. Таким образом возникла первая клеточно-автоматная система. Подобно решётке Улама, клеточный автомат фон Неймана двухмерный, а самовоспроизводящийся робот описан алгоритмически. Результатом явился универсальный конструктор, работающий «внутри» клеточного автомата с окрестностью, включающей непосредственно прилегающие клетки, и имеющего 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 году немецкий инженер Конрад Цузе опубликовал книгу «Вычислимый космос», где выдвинул предположение, что физические законы дискретны по своей природе, и что вся Вселенная является гигантским клеточным автоматом. Это была первая книга из области, называемой сейчас цифровой физикой.

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle N_{r}=\sigma ^{\sigma ^{n}}}$[3]

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

Правило 30

Правило 30

Правило 110

Правило 110

Правило 161

Правило 161

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

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

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

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

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

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

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

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

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

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

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

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