Клеточный автомат (мн. клеточный автомат , аббревиатура CA ) — дискретная модель вычислений, изучаемая в теории автоматов . Клеточные автоматы также называются клеточными пространствами , автоматами тесселяции , однородными структурами , клеточными структурами , структурами тесселяции и итеративными массивами . [2] Клеточные автоматы нашли применение в различных областях, включая физику , теоретическую биологию и моделирование микроструктуры .
Клеточный автомат состоит из регулярной сетки ячеек , каждая из которых находится в одном из конечного числа состояний , таких как включенное и выключенное (в отличие от решетки связанных карт ). Сетка может иметь любое конечное число измерений. Для каждой ячейки определяется набор ячеек, называемый ее окрестностью, относительно указанной ячейки. Начальное состояние (время t = 0) выбирается путем назначения состояния каждой ячейке. Новое поколение создается (увеличивая t на 1) по некоторому фиксированному правилу (обычно математической функции) [3] , которое определяет новое состояние каждой ячейки с точки зрения текущего состояния ячейки и состояний ячеек. в его окрестностях. Обычно правило обновления состояния ячеек одинаково для каждой ячейки, не меняется с течением времени и применяется ко всей сетке одновременно [4] , хотя известны исключения, такие как стохастический клеточный автомат и асинхронный клеточный автомат. .
Эта концепция была первоначально открыта в 1940-х годах Станиславом Уламом и Джоном фон Нейманом, когда они были современниками в Национальной лаборатории Лос-Аламоса . Хотя некоторые изучали эту тему на протяжении 1950-х и 1960-х годов, только в 1970-х годах и в «Игре жизни» Конвея , двумерном клеточном автомате, интерес к этому предмету вышел за пределы академических кругов. В 1980-х годах Стивен Вольфрам занимался систематическим изучением одномерных клеточных автоматов, или того, что он называет элементарными клеточными автоматами ; его научный сотрудник Мэтью Кук показал, что одно из этих правил является полным по Тьюрингу .
Основные классификации клеточных автоматов, предложенные Вольфрамом, пронумерованы от одного до четырех. Это, по порядку, автоматы, в которых закономерности обычно стабилизируются до однородности , автоматы, в которых закономерности превращаются в преимущественно стабильные или колеблющиеся структуры, автоматы, в которых закономерности развиваются хаотичным образом, и автоматы, в которых закономерности становятся чрезвычайно сложными и могут сохраняться в течение нескольких лет. долгое время, со стабильными местными структурами. Этот последний класс считается универсальным в вычислительном отношении или способен моделировать машину Тьюринга . Особыми видами клеточных автоматов являются обратимые , где только одна конфигурация приводит непосредственно к последующей, и тоталистические , в которых будущее значение отдельных ячеек зависит только от суммарного значения группы соседних ячеек. Клеточные автоматы могут моделировать различные системы реального мира, включая биологические и химические.
Один из способов смоделировать двумерный клеточный автомат — использовать бесконечный лист миллиметровой бумаги и набор правил, которым должны следовать ячейки. Каждый квадрат называется «клеткой», и каждая ячейка имеет два возможных состояния: черное и белое. Окрестность ячейки — это близлежащие, обычно соседние ячейки . Двумя наиболее распространенными типами окрестностей являются окрестности фон Неймана и окрестности Мура . [5] Первый, названный в честь основателя теории клеточных автоматов, состоит из четырех ортогонально соседних ячеек. [5] Последний включает в себя окрестность фон Неймана, а также четыре соседних по диагонали ячейки. [5] Для такой ячейки и ее окрестности Мура существует 512 (= 2 9 ) возможных шаблонов. Для каждого из 512 возможных шаблонов в таблице правил будет указано, будет ли центральная ячейка черной или белой в следующий интервал времени. «Игра жизни» Конвея — популярная версия этой модели. Другим распространенным типом соседства является расширенное соседство фон Неймана , которое включает в себя две ближайшие ячейки в каждом ортогональном направлении, всего восемь. [5] Общее уравнение для общего количества возможных автоматов: k k s , где k — количество возможных состояний для ячейки, а s — количество соседних ячеек (включая саму вычисляемую ячейку), используемых для определения следующее состояние клетки. [6] Таким образом, в двумерной системе с окрестностью Мура общее число возможных автоматов будет равно 2 2 9 , или1,34 × 10 154 .
Обычно предполагается, что каждая ячейка во Вселенной начинается в одном и том же состоянии, за исключением конечного числа ячеек в других состояниях; присвоение значений состояния называется конфигурацией . [7] В более общем плане иногда предполагается, что Вселенная изначально покрыта периодической структурой, и только конечное число ячеек нарушает эту структуру. Последнее предположение распространено в одномерных клеточных автоматах.
Клеточные автоматы часто моделируются на конечной, а не на бесконечной сетке. В двух измерениях Вселенная была бы прямоугольником, а не бесконечной плоскостью. Очевидная проблема с конечными сетками — как обращаться с ячейками на краях. То, как они обрабатываются, повлияет на значения всех ячеек сетки. Один из возможных способов — оставить значения в этих ячейках постоянными. Другой метод — по-разному определить окрестности для этих ячеек. Можно было бы сказать, что у них меньше соседей, но тогда пришлось бы также определять новые правила для ячеек, расположенных на ребрах. Эти ячейки обычно обрабатываются с периодическими граничными условиями , что приводит к тороидальному расположению: когда одна выходит сверху, другая входит в соответствующую позицию внизу, а когда одна выходит слева, другая входит справа. (По сути, это имитирует бесконечное периодическое замощение, и в области уравнений в частных производных это иногда называют периодическими граничными условиями.) Это можно представить себе как склеивание левого и правого краев прямоугольника, чтобы сформировать трубку, а затем склеивание верхней части прямоугольника. и нижние края трубки, чтобы сформировать тор (форму пончика). Вселенные других измерений обрабатываются аналогично. Это решает граничные проблемы с окрестностями, но еще одним преимуществом является то, что его легко программировать с использованием модульных арифметических функций. Например, в одномерном клеточном автомате, подобном приведенным ниже примерам, окрестность ячейки x i t равна { x i −1 t −1 , x i t −1 , x i +1 t −1 }, где t — шаг по времени (по вертикали), а i — индекс (по горизонтали) в одном поколении.
Станислав Улам , работая в Лос-Аламосской национальной лаборатории в 1940-х годах, изучал рост кристаллов, используя в качестве модели простую решетчатую сетку . [8] В то же время Джон фон Нейман , коллега Улама в Лос-Аламосе, работал над проблемой самовоспроизводящихся систем . [9] Первоначальный проект фон Неймана был основан на идее, что один робот строит другого робота. Эта конструкция известна как кинематическая модель. [10] [11] Разрабатывая эту конструкцию, фон Нейман осознал огромную сложность создания самовоспроизводящегося робота и высокую стоимость обеспечения робота «морем деталей», из которого можно построить его реплику. . Нейман написал статью под названием «Общая и логическая теория автоматов» для Хиксонского симпозиума в 1948 году. [9] Улам был тем, кто предложил использовать дискретную систему для создания редукционистской модели самовоспроизведения. [12] [13] Нильс Алл Барричелли выполнил многие из самых ранних исследований этих моделей искусственной жизни .
Улам и фон Нейман создали метод расчета движения жидкости в конце 1950-х годов. Основная идея метода заключалась в том, чтобы рассматривать жидкость как группу дискретных единиц и рассчитывать движение каждой из них на основе поведения ее соседей. [14] Так родилась первая система клеточных автоматов. Как и решетчатая сеть Улама, клеточные автоматы фон Неймана двумерны, а его саморепликатор реализован алгоритмически. В результате получился универсальный копировальный аппарат и конструктор , работающий внутри клеточного автомата с небольшой окрестностью (соседями являются только те ячейки, которые соприкасаются; для клеточных автоматов фон Неймана — только ортогональные ячейки) и с 29 состояниями на ячейку. [15] Фон Нейман предоставил доказательство существования того, что конкретный образец может создавать бесконечные копии самого себя в данной клеточной вселенной, разработав конфигурацию из 200 000 ячеек, которая могла это делать. [15] Эта конструкция известна как модель тесселяции и называется универсальным конструктором фон Неймана . [16]
Также в 1940-х годах Норберт Винер и Артуро Розенблют разработали модель возбудимой среды с некоторыми характеристиками клеточного автомата. [17] Их конкретной мотивацией было математическое описание проведения импульсов в сердечной системе. Однако их модель не является клеточным автоматом, поскольку среда, в которой распространяются сигналы, непрерывна, а волновые фронты представляют собой кривые. [17] [18] Истинная клеточно-автоматная модель возбудимой среды была разработана и изучена Дж. М. Гринбергом и С. П. Гастингсом в 1978 году; см. клеточный автомат Гринберга-Гастингса . Оригинальная работа Винера и Розенблюта содержит множество идей и продолжает цитироваться в современных исследовательских публикациях по сердечной аритмии и возбудимым системам. [19]
В 1960-е годы клеточные автоматы изучались как особый тип динамической системы и впервые была установлена связь с математической областью символической динамики . В 1969 году Густав А. Хедлунд собрал множество результатов, следующих этой точке зрения [20] , и это до сих пор считается основополагающей статьей для математического исследования клеточных автоматов. Наиболее фундаментальным результатом является характеризация в теореме Кертиса–Хедлунда–Линдона множества глобальных правил клеточных автоматов как множества непрерывных эндоморфизмов пространств сдвига .
В 1969 году немецкий пионер компьютеров Конрад Цузе опубликовал свою книгу «Вычисление пространства» , в которой предположил, что физические законы Вселенной дискретны по своей природе и что вся Вселенная является результатом детерминированных вычислений на одном клеточном автомате; «Теория Цузе» стала основой области исследований, называемой цифровой физикой . [21]
Также в 1969 году учёный-компьютерщик Элви Рэй Смит защитил Стэнфордскую докторскую диссертацию по теории клеточных автоматов, первой математической трактовке СА как общего класса компьютеров. На основе этой диссертации появилось множество статей: он показал эквивалентность окрестностей различной формы, как свести окрестность Мура к окрестностям фон Неймана или как свести любую окрестность к окрестностям фон Неймана. [22] Он доказал , что двумерные КА универсальны для вычислений, представил одномерные КА и показал, что они тоже универсальны для вычислений, даже с простыми окрестностями. [23] Он показал, как объединить сложное доказательство фон Неймана универсальности конструкции (и, следовательно, самовоспроизводящихся машин) в следствие универсальности вычислений в одномерном СА. [24] Задуманный как введение к немецкому изданию книги фон Неймана о СА, он написал обзор этой области с десятками ссылок на статьи, написанные многими авторами во многих странах за десятилетие или около того работы, часто упускаемые из виду современными специалистами. Исследователи ЦА. [25]
В 1970-х годах двумерный клеточный автомат с двумя состояниями под названием «Игра жизни» стал широко известен, особенно среди раннего компьютерного сообщества. Его правила , изобретенные Джоном Конвеем и популяризированные Мартином Гарднером в статье в Scientific American [26] , заключаются в следующем:
Несмотря на свою простоту, система демонстрирует впечатляющее разнообразие поведения, колеблясь между очевидной случайностью и порядком. Одной из наиболее очевидных особенностей Игры Жизни является частое появление планеров , расположений ячеек, которые по существу перемещаются по сетке. Можно организовать автомат так, чтобы планеры взаимодействовали для выполнения вычислений, и после долгих усилий было показано, что Игра Жизни может имитировать универсальную машину Тьюринга . [27] Это рассматривалось в основном как развлекательная тема, и в начале 1970-х годов была проведена небольшая дополнительная работа, помимо исследования особенностей «Игры жизни» и нескольких связанных с ней правил. [28]
Стивен Вольфрам независимо начал работать над клеточными автоматами в середине 1981 года после рассмотрения того, как сложные структуры формируются в природе в нарушение Второго закона термодинамики . [29] Первоначально его исследования были вызваны желанием смоделировать такие системы, как нейронные сети, обнаруженные в мозге. [29] Он опубликовал свою первую статью в «Обзорах современной физики», посвященную исследованию элементарных клеточных автоматов ( в частности, правило 30 ) в июне 1983 года . [2] [29] Неожиданная сложность поведения этих простых правил заставила Вольфрама подозревать, что сложность природа может быть обусловлена схожими механизмами. [29] Однако его исследования привели его к пониманию того, что клеточные автоматы плохо подходят для моделирования нейронных сетей. [29] Кроме того, в этот период Вольфрам сформулировал концепции внутренней случайности и вычислительной неприводимости [30] и предположил, что правило 110 может быть универсальным - факт, доказанный позже научным сотрудником Вольфрама Мэтью Куком в 1990-х годах. [31]
Вольфрам в книге «Новый вид науки» и нескольких статьях середины 1980-х годов определил четыре класса, на которые можно разделить клеточные автоматы и несколько других простых вычислительных моделей в зависимости от их поведения. В то время как более ранние исследования клеточных автоматов имели тенденцию пытаться определить тип шаблонов для конкретных правил, классификация Вольфрама была первой попыткой классифицировать сами правила. В порядке сложности классы следующие:
Эти определения носят качественный характер и допускают некоторую интерпретацию. Согласно Вольфраму, «...почти в любой общей схеме классификации неизбежно возникают случаи, которые относят к одному классу по одному определению, а к другому классу по другому определению. То же самое и с клеточными автоматами: иногда существуют правила... которые показать некоторые особенности одного класса и некоторые другие». [34] Классификация Вольфрама была эмпирически сопоставлена с кластеризацией сжатых длин выходных данных клеточных автоматов. [35]
Было предпринято несколько попыток классифицировать клеточные автоматы по формально строгим классам, вдохновленным классификацией Вольфрама. Например, Кулик и Ю предложили три четко определенных класса (и четвертый для автоматов, не соответствующих ни одному из них), которые иногда называют классами Кулика – Ю; членство в них оказалось неразрешимым . [36] [37] [38] Класс 2 Вольфрама можно разделить на две подгруппы стабильных (с фиксированной точкой) и осциллирующих (периодических) правил. [39]
Идея о существовании четырех классов динамических систем исходила от лауреата Нобелевской премии по химику Ильи Пригожина , который выделил эти четыре класса термодинамических систем: (1) системы, находящиеся в термодинамическом равновесии, (2) пространственно/временно однородные системы, (3) хаотические системы. системы и (4) сложные, далекие от равновесия системы с диссипативными структурами (см. рис. 1 в статье Николиса, ученика Пригожина, 1974 г.). [40]
Клеточный автомат обратим , если для каждой текущей конфигурации клеточного автомата существует ровно одна прошлая конфигурация ( прообраз ). [41] Если рассматривать клеточный автомат как функцию, отображающую конфигурации в конфигурации, обратимость подразумевает, что эта функция является биективной . [41] Если клеточный автомат обратим, его поведение в обращенном времени также можно описать как клеточный автомат; этот факт является следствием теоремы Кертиса-Хедлунда-Линдона , топологической характеристики клеточных автоматов. [42] [43] Для клеточных автоматов, в которых не каждая конфигурация имеет прообраз, конфигурации без прообразов называются шаблонами Эдемского сада . [44]
Для одномерных клеточных автоматов известны алгоритмы определения обратимости или необратимости правила. [45] [46] Однако для клеточных автоматов двух или более измерений обратимость неразрешима ; то есть не существует алгоритма, который принимает на вход правило автомата и гарантированно правильно определяет, является ли автомат обратимым. Доказательство Яркко Кари связано с проблемой замощения плитками Ванга . [47]
Обратимые клеточные автоматы часто используются для моделирования таких физических явлений, как динамика газа и жидкости, поскольку они подчиняются законам термодинамики . Такие клеточные автоматы имеют правила, специально построенные так, чтобы быть обратимыми. Подобные системы изучали Томмазо Тоффоли , Норман Марголус и другие. Для явного построения обратимых клеточных автоматов с известными обратными можно использовать несколько методов. Двумя распространенными из них являются клеточный автомат второго порядка и блочный клеточный автомат , оба из которых каким-то образом модифицируют определение клеточного автомата. Хотя такие автоматы не полностью удовлетворяют определению, данному выше, можно показать, что они могут эмулироваться обычными клеточными автоматами с достаточно большими окрестностями и количеством состояний и, следовательно, могут считаться подмножеством обычных клеточных автоматов. И наоборот, было показано, что каждый обратимый клеточный автомат может быть эмулирован блочным клеточным автоматом. [48] [49]
Особым классом клеточных автоматов являются тотальные клеточные автоматы. Состояние каждой ячейки тотального клеточного автомата представляется числом (обычно целым значением, взятым из конечного множества), а значение ячейки в момент времени t зависит только от суммы значений ячеек в ее окрестности. (возможно, включая саму ячейку) в момент времени t - 1. [50] [51] Если состояние клетки в момент времени t зависит как от ее собственного состояния, так и от суммы ее соседей в момент времени t - 1, то клеточный автомат правильно называть внешним тоталистическим . [51] «Игра жизни» Конвея является примером внешнего тотального клеточного автомата со значениями ячеек 0 и 1; внешние тоталистические клеточные автоматы с той же структурой окрестностей Мура, что и Жизнь, иногда называют жизнеподобными клеточными автоматами . [52] [53]
Существует множество возможных обобщений концепции клеточного автомата.
Один из способов — использовать что-то отличное от прямоугольной (кубической и т. д. ) сетки. Например, если плоскость покрыта правильными шестиугольниками , эти шестиугольники можно использовать в качестве ячеек. Во многих случаях полученные клеточные автоматы эквивалентны автоматам с прямоугольными сетками со специально разработанными окрестностями и правилами. Другой вариант — сделать саму сетку нерегулярной, как, например, в случае с плитками Пенроуза . [54]
Кроме того, правила могут быть вероятностными, а не детерминированными. Такие клеточные автоматы называются вероятностными клеточными автоматами . Вероятностное правило дает для каждого шаблона в момент времени t вероятности того, что центральная ячейка перейдет в каждое возможное состояние в момент времени t + 1. Иногда используется более простое правило; например: «Правило — игра в жизнь, но на каждом временном шаге существует вероятность 0,001%, что каждая ячейка перейдет в противоположный цвет».
Соседство или правила могут меняться со временем или в пространстве. Например, первоначально новое состояние ячейки может определяться соседними по горизонтали ячейками, но для следующего поколения будут использоваться вертикальные ячейки.
В клеточных автоматах новое состояние клетки не зависит от нового состояния других клеток. Это можно изменить так, чтобы, например, блок ячеек 2 на 2 мог определяться сам по себе и по соседним с ним ячейкам.
Существуют непрерывные автоматы . Они похожи на тотальные клеточные автоматы, но вместо того, чтобы правило и состояния были дискретными ( например , таблица, использующая состояния {0,1,2}), используются непрерывные функции, и состояния становятся непрерывными (обычно значения в [0,1 ] ). Состояние локации представляет собой конечное число действительных чисел. Некоторые клеточные автоматы могут таким образом обеспечивать диффузию в жидких структурах.
Непрерывные пространственные автоматы имеют континуум местоположений. Состояние локации представляет собой конечное число действительных чисел. Время также непрерывно, и состояние развивается согласно дифференциальным уравнениям. Одним из важных примеров являются текстуры реакции-диффузии , дифференциальные уравнения, предложенные Аланом Тьюрингом для объяснения того, как химические реакции могут создавать полосы у зебр и пятна у леопардов. [55] Когда они аппроксимируются клеточными автоматами, они часто дают схожие закономерности. МакЛеннан [1] рассматривает непрерывные пространственные автоматы как модель вычислений.
Известны примеры непрерывных пространственных автоматов, которые демонстрируют явления распространения, аналогичные планерам в Игре Жизни. [56]
Автоматы переписывания графов — это расширения клеточных автоматов, основанные на системах переписывания графов . [57]
Простейший нетривиальный клеточный автомат будет одномерным, с двумя возможными состояниями на ячейку, а соседями ячейки будут считаться соседние ячейки по обе стороны от нее. Ячейка и два ее соседа образуют окрестность из 3 ячеек, поэтому существует 2 3 = 8 возможных шаблонов для окрестности. Правило состоит в том, чтобы для каждого шаблона решить, будет ли ячейка иметь значение 1 или 0 в следующем поколении. Тогда существует 2 8 = 256 возможных правил. [6]
Эти 256 клеточных автоматов обычно обозначаются их кодом Wolfram — стандартным соглашением об именах, изобретенным Wolfram, которое присваивает каждому правилу номер от 0 до 255. В ряде работ эти 256 клеточных автоматов были проанализированы и сравнены. Особый интерес представляют клеточные автоматы « правило 30» , «правило 90» , «правило 110 » и «правило 184» . На изображениях ниже показана история правил 30 и 110, когда начальная конфигурация состоит из цифры 1 (вверху каждого изображения), окруженной нулями. Каждая строка пикселей представляет поколение в истории автомата, где t = 0 — верхняя строка. Каждый пиксель окрашен в белый цвет (0) и черный (1).
Правило 30 демонстрирует поведение класса 3 , то есть даже простые шаблоны ввода, подобные показанному, приводят к хаотичным, на первый взгляд случайным историям.
Правило 110, как и Игра «Жизнь», демонстрирует то, что Вольфрам называет поведением класса 4 , которое не является ни полностью случайным, ни полностью повторяющимся. Локализованные структуры возникают и взаимодействуют различными сложными на вид способами. В ходе разработки книги «Новый вид науки» , будучи научным сотрудником Вольфрама в 1994 году, Мэтью Кук доказал, что некоторые из этих структур были достаточно богатыми, чтобы поддерживать универсальность . Этот результат интересен тем, что правило 110 представляет собой чрезвычайно простую одномерную систему, и ее сложно спроектировать для выполнения определенного поведения. Таким образом, этот результат обеспечивает значительную поддержку точки зрения Вольфрама о том, что системы класса 4 по своей сути, вероятно, будут универсальными. Кук представил свое доказательство на конференции Института Санта-Фе по клеточным автоматам в 1998 году, но Вольфрам заблокировал включение доказательства в материалы конференции, поскольку Вольфрам не хотел, чтобы доказательство было объявлено до публикации « Нового вида науки» . [58] В 2004 году доказательство Кука было наконец опубликовано в журнале Вольфрама « Комплексные системы» (том 15, № 1), спустя десять лет после того, как Кук придумал его. Правило 110 легло в основу некоторых из самых маленьких универсальных машин Тьюринга. [59]
Элементарное правило клеточного автомата задается 8 битами, и можно считать, что все элементарные правила клеточного автомата расположены в вершинах 8 -мерного единичного гиперкуба . Этот единичный гиперкуб представляет собой пространство правил клеточного автомата. Для клеточных автоматов следующего ближайшего соседа правило задается 2 5 = 32 битами, а пространство правил клеточного автомата представляет собой 32-мерный единичный гиперкуб. Расстояние между двумя правилами можно определить количеством шагов, необходимых для перемещения от одной вершины, представляющей первое правило, до другой вершины, представляющей другое правило, вдоль края гиперкуба . Это расстояние между правилами также называется расстоянием Хэмминга .
Пространство правил клеточного автомата позволяет задаться вопросом, «близки» ли правила со схожим динамическим поведением друг другу. Графическое рисование многомерного гиперкуба на двухмерной плоскости остается сложной задачей, и одним из грубых указателей правил в гиперкубе является число бит-1 в 8-битной строке для элементарных правил (или 32-битной строке для элементарных правил). правила следующего ближайшего соседа). Рисование правил в разных классах Wolfram в этих срезах пространства правил показывает, что правила класса 1, как правило, имеют меньшее количество битов-1 и, таким образом, расположены в одной области пространства, тогда как правила класса 3 имеют тенденцию иметь более высокую долю (50% ) бит-1. [39]
Показано, что для большего пространства правил клеточного автомата правила класса 4 располагаются между правилами класса 1 и класса 3. [60] Это наблюдение лежит в основе фразы « край хаоса » и напоминает фазовый переход в термодинамике .
Некоторые биологические процессы происходят или могут быть смоделированы клеточными автоматами.
Вот некоторые примеры биологических явлений, моделируемых клеточными автоматами с простым пространством состояний:
Кроме того, биологические явления, которые требуют явного моделирования скоростей агентов (например, участвующих в коллективной миграции клеток ), могут моделироваться клеточными автоматами с более сложным пространством состояний и правилами, такими как биологические клеточные автоматы с решеточным газом . К ним относятся явления, имеющие большое медицинское значение, такие как:
Реакция Белоусова-Жаботинского представляет собой пространственно-временной химический осциллятор , который можно моделировать с помощью клеточного автомата. В 1950-х годах А. М. Жаботинский (продолжая работы Б. П. Белоусова ) обнаружил, что, когда тонкий однородный слой смеси малоновой кислоты , подкисленного бромата и цериевой соли смешивается и остается нетронутым, возникают увлекательные геометрические узоры, такие как концентрические круги и спирали распространяются по среде. В разделе «Компьютерные развлечения» августовского номера журнала Scientific American за 1988 год [ 69 ] А. К. Дьюдни обсуждал клеточный автомат [70] , разработанный Мартином Герхардтом и Хайке Шустером из Университета Билефельда (Германия). Этот автомат создает волновые узоры, напоминающие реакции Белоусова-Жаботинского.
Вероятностные клеточные автоматы используются в статистической физике и физике конденсированного состояния для изучения таких явлений, как гидродинамика и фазовые переходы. Модель Изинга является типичным примером, в котором каждая ячейка может находиться в одном из двух состояний, называемых «верхним» и «нижним», что представляет собой идеализированное представление магнита . Регулируя параметры модели, можно изменять долю ячеек, находящихся в одном и том же состоянии, таким образом, чтобы объяснить, как ферромагнетики размагничиваются при нагревании. Более того, результаты изучения фазового перехода размагничивания могут быть перенесены и на другие фазовые переходы, например испарение жидкости в газ; эта удобная перекрестная применимость известна как универсальность . [71] [72] Фазовый переход в двумерной модели Изинга и других системах ее класса универсальности представляет особый интерес, поскольку для его глубокого понимания требуется конформная теория поля . [73] Другие клеточные автоматы, которые сыграли важную роль в физике, включают автоматы с решеточным газом , которые моделируют потоки жидкости.
Процессоры клеточных автоматов представляют собой физическую реализацию концепций CA, которые могут обрабатывать информацию вычислительным путем. Элементы обработки расположены в виде регулярной сетки из одинаковых ячеек. Сетка обычно представляет собой квадратную мозаику или мозаику двух или трех измерений; возможны и другие замощения, но они еще не используются. Состояния ячеек определяются только взаимодействием с соседними соседними ячейками. Не существует средств для прямой связи с более удаленными клетками. [74] Одной из таких конфигураций массива процессоров клеточного автомата является систолический массив . Взаимодействие клеток может осуществляться посредством электрического заряда, магнетизма, вибрации ( фононов на квантовом уровне) или любых других физически полезных средств. Это можно сделать несколькими способами, чтобы между какими-либо элементами не требовались провода. Это очень отличается от процессоров, используемых сегодня в большинстве компьютеров ( проекты фон Неймана ), которые разделены на секции с элементами, которые могут связываться с удаленными элементами по проводам.
Правило 30 изначально предлагалось как возможный блочный шифр для использования в криптографии . Двумерные клеточные автоматы могут быть использованы для построения генератора псевдослучайных чисел . [75]
Клеточные автоматы были предложены для криптографии с открытым ключом . Односторонняя функция — это эволюция конечного КА, обратную которому, как полагают, найти трудно. Учитывая это правило, любой может легко вычислить будущие состояния, но вычислить предыдущие состояния оказывается очень сложно. Клеточные автоматы также применялись для разработки кодов с исправлением ошибок . [76]
Другие проблемы, которые можно решить с помощью клеточных автоматов, включают:
Клеточные автоматы использовались в генеративной музыке [77] , эволюционной музыкальной композиции [78] и процедурной генерации ландшафта в видеоиграх. [79]
Определенные типы клеточных автоматов можно использовать для создания лабиринтов. [80] Два хорошо известных таких клеточных автомата, Maze и Mazectric, имеют строки правил B3/S12345 и B3/S1234. [80] В первом случае это означает, что клетки выживают от одного поколения к другому, если у них есть хотя бы один и не более пяти соседей . В последнем случае это означает, что клетки выживают, если у них есть от одного до четырех соседей. Если у клетки ровно три соседа, она рождается. Это похоже на «Игру жизни» Конвея в том смысле, что модели, в которых нет живой клетки, соседствующей с 1, 4 или 5 другими живыми клетками в любом поколении, будут вести себя идентично ей. [80] Однако для больших шаблонов он ведет себя совсем не так, как Life. [80]
При случайном исходном шаблоне эти клеточные автоматы, генерирующие лабиринты, разовьются в сложные лабиринты с четко очерченными стенами, очерчивающими коридоры. Mazecetric, имеющий правило B3/S1234, имеет тенденцию создавать более длинные и прямые коридоры по сравнению с Maze с правилом B3/S12345. [80] Поскольку эти правила клеточного автомата являются детерминированными , каждый генерируемый лабиринт однозначно определяется его случайным начальным шаблоном. Это существенный недостаток, поскольку лабиринты обычно относительно предсказуемы.
Как и некоторые из описанных выше методов, основанных на теории графов, эти клеточные автоматы обычно генерируют лабиринты из одного начального шаблона; следовательно, обычно относительно легко найти путь к начальной ячейке, но труднее найти путь куда-либо еще.Конкретные правила клеточных автоматов включают:
{{cite web}}: CS1 maint: архивная копия в заголовке ( ссылка )
