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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Планерное ружьё Госпера в клеточном автомате «Жизнь»

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

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

История[править | править вики-текст]

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

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

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

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

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

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

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

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

11-го ноября 2002 года Пауль Чепмен (Paul Chapman) построил образец Жизни, который является РММ (Регистровой Машиной Минского). Фактически РММ эквивалентна машине Тьюринга. Первая версия образца была большой (268,096 живых ячеек на площади 4,558 x 21,469 клеток) и медленной (20 поколений/сек при использовании Life32 Иогана Бонтеса (Johan Bontes) на 400 MHz AMD K6-II). Таким образом, в игре Жизнь можно выполнить любой алгоритм, который можно реализовать на современном компьютере.

Математическое определение[править | править вики-текст]

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

\sigma \in \Sigma \equiv \{0,1,2 ... k-1, k\}.

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

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

где {\mathcal N} — множество автоматов, составляющих окрестность. К примеру, окрестность фон Неймана определяется как

{\mathcal N}_N^1(i,j)=\{\sigma_{k,l}|~|i-k|+|j-l|\le 1\},

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

{\mathcal N}_M^1(i,j)=\{\sigma_{k,l}|~|i-k|\le 1, |j-l|\le 1\}.

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

N_r=\sigma^{\sigma^n}[1]

Классификация[править | править вики-текст]

Классификация по типам поведения[править | править вики-текст]

Правило 40(Класс 1) со случайными начальными условиями. Как видно, информация быстро исчезает в этой системе.
Правило 3(Класс 2) со случайными начальными условиями. Очевидно появление периодических структур
Правило 18(Класс 3) со случайными начальными условиями. Видно, что начальные условия порождают хаотические движения внутри системы.
Правило 193(Класс 4) со случайными начальными условиями. Можно увидеть порождение устойчивых структур(колонка белых треугольников и взаимодействие таких структур в других частях изображения.)

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

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

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

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

Тоталистичные клеточные автоматы[править | править вики-текст]

Существует специальный класс клеточный автоматов, называемых тоталистичными. На каждом шаге эволюции клеточного автомата значение ячейки равно какому-либо целому числу(обычно выбираемого из конечного множества), а новое состояние клетки определяется суммой значений клеток-соседей и, возможно, предыдущим состоянием клетки. Если состояние клетки на новом шаге зависит от её предыдущего состояния, то такой клеточный автомат называется внешним тоталистичным. Игра Жизнь является примером внешнего тоталистического клеточного автомата с набором значений ячеек {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

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


Правило 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. Их пигментные клетки располагаются тонкой полоской вдоль края раковины. Секреция пигмента каждой клетки зависит от активирующей и ингибиторной активности соседних клеток. В процессе роста раковины полоса клеток формирует цветной узор на её поверхности.

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

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

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

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

Применения клеточных автоматов[править | править вики-текст]

Компьютерные процессоры[править | править вики-текст]

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

Криптография[править | править вики-текст]

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

Моделирование физических процессов[править | править вики-текст]

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

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

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

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

См. также[править | править вики-текст]

Специфические правила[править | править вики-текст]

Рассматриваемые проблемы[править | править вики-текст]

Связанные статьи[править | править вики-текст]

Примечания[править | править вики-текст]

  1. A.G.Hoekstra, J.Kroc, P.Sloot. Simulating complex systems by cellular automata. Springer, 2010. ISBN 978-3-642-12202-6

Ссылки[править | править вики-текст]