Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

Пистолет-планер Госпера создает « планеры » в «Игре жизни» Конвея [1]

Клеточный автомат (пл. Клеточных автоматов , Abbrev. CA ) представляет собой дискретную модель вычислений изучена в теории автоматов . Клеточные автоматы также называют клеточными пространствами , автоматами тесселяции , однородными структурами , клеточными структурами , тесселяционными структурами и итерационными массивами . [2] Клеточные автоматы нашли применение в различных областях, включая физику , теоретическую биологию и моделирование микроструктур .

Клеточный автомат состоит из регулярной сетки ячеек , каждая из которых находится в одном из конечного числа состояний , таких как включено и выключено (в отличие от решетки связанных карт ). Сетка может быть любого конечного числа измерений. Для каждой ячейки определяется набор ячеек, называемый ее окрестностью, относительно указанной ячейки. Начальное состояние (время t  = 0) выбирается путем назначения состояния для каждой ячейки. Новое поколение создается (увеличивая t на 1) согласно некоторому фиксированному правилу (обычно математической функции) [3]который определяет новое состояние каждой ячейки с точки зрения текущего состояния ячейки и состояний ячеек в ее окрестности. Как правило, правило обновления состояния ячеек одинаково для каждой ячейки и не меняется со временем, и применяется ко всей сетке одновременно [4], хотя известны исключения, такие как стохастический клеточный автомат и асинхронный клеточный автомат. .

Эта концепция была первоначально открыта в 1940-х годах Станиславом Уламом и Джоном фон Нейманом, когда они были современниками в Национальной лаборатории Лос-Аламоса . Хотя некоторые изучали эту тему в 1950-х и 1960-х годах, только в 1970-х годах и до игры Конвея «Игра жизни» , двумерного клеточного автомата, интерес к этому предмету расширился за пределы академических кругов. В 1980-х Стивен Вольфрам занялся систематическим изучением одномерных клеточных автоматов, или того, что он называет элементарными клеточными автоматами ; его научный сотрудник Мэтью Кук показал, что одно из этих правил является полным по Тьюрингу . Вольфрам опубликовалНовый вид науки в 2002 году, в котором утверждается, что клеточные автоматы находят применение во многих областях науки . К ним относятся компьютерные процессоры и криптография .

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

Обзор [ править ]

Красные клетки - это район фон Неймана для синей клетки. Расширенный район также включает розовые клетки.

Один из способов смоделировать двумерный клеточный автомат - использовать бесконечный лист миллиметровой бумаги вместе с набором правил, которым должны следовать клетки. Каждый квадрат называется «ячейкой», и каждая ячейка имеет два возможных состояния: черное и белое. Окрестности ячейки является рядом, как правило , смежно клетки. Двумя наиболее распространенными типами районов являются район фон Неймана и район Мура . [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]Фон Нейман представил доказательство существования того, что определенный паттерн будет создавать бесконечные копии самого себя в данной клеточной вселенной, разработав конфигурацию из 200000 клеток, которая могла бы это сделать. [15] Этот дизайн известен как модель тесселяции и называется универсальным конструктором фон Неймана . [16]

Также в 1940-х годах Норберт Винер и Артуро Розенблют разработали модель возбудимых сред с некоторыми характеристиками клеточного автомата. [17] Их особой мотивацией было математическое описание проведения импульсов в сердечных системах. Однако их модель не является клеточным автоматом, потому что среда, в которой распространяются сигналы, непрерывна, а волновые фронты кривые. [17] [18] Настоящая клеточно-автоматная модель возбудимых сред была разработана и изучена Дж. М. Гринбергом и С. П. Гастингсом в 1978 г .; см. клеточный автомат Гринберга-Гастингса . Оригинальная работа Винера и Розенблюта содержит много идей и продолжает цитироваться в современных исследовательских публикациях посердечная аритмия и возбудимые системы. [19]

К концу 1950-х годов было замечено, что клеточные автоматы можно рассматривать как параллельные компьютеры , и особенно в 1960-х годах была доказана последовательность все более подробных и технических теорем - часто аналогичных теоремам о машинах Тьюринга - об их формальных вычислительных возможностях. [20]

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

В 1969 году немецкий пионер компьютеров Конрад Цузе опубликовал свою книгу « Расчет пространства» , в которой предположил, что физические законы Вселенной дискретны по своей природе и что вся Вселенная является результатом детерминированных вычислений на одном клеточном автомате; «Теория Цузе» легла в основу области исследований, называемой цифровой физикой . [22]

Также в 1969 году компьютерный ученый Элви Рэй Смит защитил Стэнфордскую докторскую диссертацию по теории клеточных автоматов, первое математическое рассмотрение СА как общего класса компьютеров. На основе этой диссертации появилось много статей: он показал эквивалентность окрестностей различной формы, как свести Мура к соседству фон Неймана или как свести любое соседство к соседству фон Неймана. [23] Он доказал, что двумерные CA универсальны для вычислений, ввел одномерные CA и показал, что они также универсальны для вычислений, даже с простыми окрестностями. [24]Он показал, как включить комплексное доказательство фон Неймана универсальности конструкции (и, следовательно, самовоспроизводящихся машин) в следствие универсальности вычислений в одномерном СА. [25] Задуманный как введение к немецкому изданию книги фон Неймана о ЦА, он написал обзор в этой области с десятками ссылок на статьи многих авторов во многих странах в течение примерно десяти лет работы, часто игнорируемой современными специалистами. Исследователи СА. [26]

В 1970-х годах двумерный клеточный автомат с двумя состояниями под названием Game of Life стал широко известен, особенно среди первых компьютерных сообществ. Изобретенный Джоном Конвеем и популяризированный Мартином Гарднером в статье в Scientific American [27], его правила заключаются в следующем:

  1. Любая живая клетка с менее чем двумя живыми соседями умирает, как если бы это было вызвано недостаточным населением.
  2. Любая живая клетка с двумя или тремя живыми соседями доживает до следующего поколения.
  3. Любая живая клетка с более чем тремя живыми соседями умирает, как будто от перенаселения.
  4. Любая мертвая клетка с ровно тремя живыми соседями становится живой клеткой, как бы путем размножения.

Несмотря на свою простоту, система достигает впечатляющего разнообразия поведения, колеблющегося между кажущейся случайностью и порядком. Одной из наиболее очевидных особенностей Игры Жизни является частое появление планеров , ячеек, которые по существу перемещаются по сетке. Можно организовать автомат так, чтобы планеры взаимодействовали для выполнения вычислений, и после значительных усилий было показано, что «Игра жизни» может имитировать универсальную машину Тьюринга . [28] Это рассматривалось в основном как развлекательная тема, и в начале 1970-х годов было проведено мало дополнительной работы, за исключением исследования особенностей Игры Жизни и нескольких связанных с ней правил. [29]

Стивен Вольфрам независимо начал работать над клеточными автоматами в середине 1981 года после того, как рассмотрел, как сложные закономерности, казалось, сформировались в природе в нарушение Второго закона термодинамики . [30] Первоначально его исследования были вызваны интересом к моделированию таких систем, как нейронные сети . [30] Он опубликовал свою первую статью в « Обзоре современной физики», в которой исследуются элементарные клеточные автоматы ( в частности, Правило 30 ) в июне 1983 года. [2] [30] Неожиданная сложность поведения этих простых правил заставила Вольфрама подозревать, что сложность в природа может быть обусловлена ​​схожими механизмами. [30]Его исследования, однако, привели его к выводу, что клеточные автоматы плохо моделируют нейронные сети. [30] Кроме того, в этот период Вольфрам сформулировал концепции внутренней случайности и вычислительной несводимости , [31] и предположил, что правило 110 может быть универсальным - факт, доказанный позже научным сотрудником Вольфрама Мэтью Куком в 1990-х. [32]

В 2002 году Вольфрам опубликовал 1280-страничный текст «Новый вид науки» , в котором широко утверждается, что открытия о клеточных автоматах не являются изолированными фактами, а являются надежными и имеют значение для всех научных дисциплин. [33] Несмотря на путаницу в прессе, [34] [35] книга не выступала в поддержку фундаментальной теории физики, основанной на клеточных автоматах, [36] и хотя она описывала несколько конкретных физических моделей, основанных на клеточных автоматах, [ 37] он также предоставил модели, основанные на качественно различных абстрактных системах. [38]

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

Вольфрам в книге «Новый вид науки» и нескольких статьях середины 1980-х годов определил четыре класса, на которые можно разделить клеточные автоматы и несколько других простых вычислительных моделей в зависимости от их поведения. В то время как более ранние исследования клеточных автоматов имели тенденцию определять тип паттернов для конкретных правил, классификация Вольфрама была первой попыткой классификации самих правил. Классы по сложности следующие:

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

Эти определения носят качественный характер и могут быть интерпретированы. Согласно Вольфраму, «... почти в любой общей схеме классификации неизбежно встречаются случаи, когда одному классу присваивается одно определение, а другому классу - другое определение. То же самое и с клеточными автоматами: иногда существуют правила ... показать некоторые особенности одного класса, а некоторые - другого ". [41] Классификация Вольфрама была эмпирически сопоставлена ​​с кластеризацией сжатых длин выходных данных клеточных автоматов. [42]

Было предпринято несколько попыток классифицировать клеточные автоматы по формально строгим классам, вдохновленным классификацией Вольфрама. Например, Кулик и Ю предложили три четко определенных класса (и четвертый для автоматов, не соответствующих ни одному из них), которые иногда называют классами Кулика-Ю; членство в них оказалось неразрешимым . [43] [44] [45] Класс Вольфрама 2 можно разделить на две подгруппы стабильных (с фиксированной точкой) и осциллирующих (периодических) правил. [46]

Идея о том, что существует 4 класса динамических систем, первоначально пришла от химика, лауреата Нобелевской премии Ильи Пригожина, который выделил эти 4 класса термодинамических систем: (1) системы в термодинамическом равновесии, (2) пространственно / временные однородные системы, (3) хаотические системы. системы, и (4) сложные далекие от равновесия системы с диссипативными структурами (см. рисунок 1 в статье Николиса (ученика Пригожина)). [47]

Реверсивный [ править ]

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

Клеточный автомат обратим, если для каждой текущей конфигурации клеточного автомата существует ровно одна прошедшая конфигурация ( прообраз ). [48] Если рассматривать клеточный автомат как функцию, отображающую конфигурации в конфигурации, обратимость подразумевает, что эта функция биективна . [48] Если клеточный автомат обратим, его обращенное во времени поведение также можно описать как клеточный автомат; этот факт является следствием теоремы Кертиса – Хедлунда – Линдона , топологической характеристики клеточных автоматов. [49] [50]Для клеточных автоматов, в которых не каждая конфигурация имеет прообраз, конфигурации без прообраза называются паттернами Эдемского сада . [51]

Для одномерных клеточных автоматов известны алгоритмы определения того, является ли правило обратимым или необратимым. [52] [53] Однако для клеточных автоматов двух или более измерений обратимость неразрешима ; то есть не существует алгоритма, который принимает на вход автоматическое правило и гарантированно правильно определяет, является ли автомат обратимым. Доказательство Яркко Кари связано с проблемой тайлов Ванга . [54]

Обратимые клеточные автоматы часто используются для моделирования таких физических явлений, как газовая и гидродинамика, поскольку они подчиняются законам термодинамики . Такие клеточные автоматы имеют правила, специально построенные для обратимости. Такие системы изучали Томмазо Тоффоли , Норман Марголус и другие. Для явного построения обратимых клеточных автоматов с известными обратными можно использовать несколько методов. Двумя общими являются клеточный автомат второго порядка и блочный клеточный автомат., оба из которых включают в себя некоторое изменение определения клеточного автомата. Хотя такие автоматы не строго удовлетворяют приведенному выше определению, можно показать, что они могут быть эмулированы обычными клеточными автоматами с достаточно большими окрестностями и числом состояний и, следовательно, могут рассматриваться как подмножество обычных клеточных автоматов. Наоборот, было показано, что любой обратимый клеточный автомат может быть эмулирован блочным клеточным автоматом. [55] [56]

Тоталистический [ править ]

Особый класс клеточных автоматов - тоталистические клеточные автоматы. Состояние каждой ячейки в тоталитарном клеточном автомате представлено числом (обычно целым значением, взятым из конечного набора), а значение ячейки в момент времени t зависит только от суммы значений ячеек в ее окрестности (возможно, включая саму клетку) в момент времени  t  - 1. [57] [58] Если состояние клетки в момент времени t зависит как от ее собственного состояния, так и от общего количества ее соседей в момент времени  t  - 1, то клеточный автомат является правильное название - внешний тоталитарный . [58] Игра жизни Конвеяпример внешнего тоталистического клеточного автомата со значениями ячеек 0 и 1; Внешние тоталистические клеточные автоматы с той же структурой соседства Мура, что и Жизнь, иногда называют живыми клеточными автоматами . [59] [60]

Связанные автоматы [ править ]

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

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

Один из способов - использовать не прямоугольную (кубическую и т. Д. ) Сетку. Например, если плоскость выложена правильными шестиугольниками , эти шестиугольники можно использовать в качестве ячеек. Во многих случаях полученные клеточные автоматы эквивалентны автоматам с прямоугольными сетками со специально разработанными окрестностями и правилами. Другой вариант - сделать саму сетку неправильной, например, с плиткой Пенроуза . [61]

Кроме того, правила могут быть скорее вероятностными, чем детерминированными. Такие клеточные автоматы называются вероятностными клеточными автоматами . Вероятностное правило дает для каждого шаблона в момент времени t вероятности того, что центральная ячейка перейдет в каждое возможное состояние в момент времени t  + 1. Иногда используется более простое правило; например: «Правило - Игра Жизни, но на каждом временном шаге с вероятностью 0,001% каждая ячейка перейдет в противоположный цвет».

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

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

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

У непрерывных пространственных автоматов есть континуум местоположений. Состояние локации - это конечное число действительных чисел. Время также непрерывно, и состояние изменяется согласно дифференциальным уравнениям. Одним из важных примеров являются текстуры реакции-диффузии , дифференциальные уравнения, предложенные Аланом Тьюрингом для объяснения того, как химические реакции могут создавать полосы на зебрах и пятна на леопардах. [62] Когда они аппроксимируются клеточными автоматами, они часто дают похожие модели. МакЛеннан [2] рассматривает непрерывные пространственные автоматы как модель вычислений.

Известны примеры непрерывных пространственных автоматов, которые демонстрируют явления распространения, аналогичные планерам в Игре Жизни. [63]

Автоматы перезаписи графов - это расширения клеточных автоматов, основанные на системах перезаписи графов . [64]

Комбинации автоматов работают, проверяя, равна ли нечетная / четная проиндексированная пара перестановке X. Если это так, вернуть X строки правил (например: «120012101»). Эти CA работают с кварталами из кирпичной стены . Эти типы CA также действуют как логические вентили . Например, эквивалент логического элемента XOR в Комбинации создает треугольник Серпинского, когда исходное состояние представляет собой одну центрированную ячейку.

Элементарные клеточные автоматы [ править ]

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

Простейший нетривиальный клеточный автомат будет одномерным, с двумя возможными состояниями на ячейку и соседями ячейки, определяемыми как соседние ячейки по обе стороны от нее. Ячейка и два ее соседа образуют окрестность из 3 ячеек, поэтому существует 2 3  = 8 возможных шаблонов для соседства. Правило состоит из решения для каждого шаблона, будет ли ячейка 1 или 0 в следующем поколении. Тогда существует 2 8  = 256 возможных правил. [6]

Анимация того, как правила одномерного клеточного автомата определяют следующее поколение.

Эти 256 клеточных автоматов обычно называются кодом Wolfram , стандартным соглашением об именах, изобретенным Вольфрамом, который присваивает каждому правилу номер от 0 до 255. В ряде статей эти 256 клеточных автоматов анализировались и сравнивались. В правиле 30 и правило 110 клеточные автоматы особенно интересны. На изображениях ниже показана история каждого из них, когда начальная конфигурация состоит из 1 (вверху каждого изображения), окруженного нулями. Каждая строка пикселей представляет собой поколение в истории автомата, причем t = 0 является верхней строкой. Каждый пиксель окрашен в белый цвет для 0 и черный для 1.

Правило 30


Правило 30 клеточный автомат

текущий образец111110101100011010001000
новое состояние для центральной ячейки00011110

Правило 30 демонстрирует поведение класса 3 , что означает, что даже простые шаблоны ввода, такие как показанный, приводят к хаотическим, на первый взгляд случайным историям.

Правило 110


Правило 110 клеточного автомата

текущий образец111110101100011010001000
новое состояние для центральной ячейки01101110

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

Пространство правил [ править ]

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

Пространство правил клеточного автомата позволяет нам задать вопрос о том, являются ли правила с подобным динамическим поведением «близкими» друг другу. Графическое рисование многомерного гиперкуба на 2-мерной плоскости остается сложной задачей, и одним грубым указателем правила в гиперкубе является число бит-1 в 8-битной строке для элементарных правил (или 32-битной строке для правила следующего ближайшего соседа). Рисование правил в разных классах Wolfram в этих срезах пространства правил показывает, что правила класса 1 обычно имеют меньшее количество бит-1, поэтому расположены в одной области пространства, тогда как правила класса 3 имеют более высокую долю (50% ) бит-1. [46]

Для большего пространства правил клеточного автомата показано, что правила класса 4 расположены между правилами класса 1 и класса 3. [67] Это наблюдение является основой фразы « край хаоса» и напоминает фазовый переход в термодинамике .

Биология [ править ]

Текстиль Conus демонстрирует узор клеточного автомата на своей оболочке. [68]
Дополнительная информация: Образцы в природе

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

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

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

Движущиеся волновые паттерны на коже головоногих моллюсков можно моделировать с помощью двумерных клеточных автоматов с двумя состояниями, каждое состояние соответствует либо расширенному, либо втянутому хроматофору . [70]

Пороговые автоматы были изобретены для имитации нейронов , а также можно моделировать сложное поведение, такое как распознавание и обучение. [71]

Фибробласты имеют сходство с клеточными автоматами, поскольку каждый фибробласт взаимодействует только со своими соседями. [72]

Типы химикатов [ править ]

Реакция Белоусова – Жаботинского - это пространственно-временной химический осциллятор, который можно моделировать с помощью клеточного автомата. В 1950-х годах А.М. Жаботинский (продолжая работу Б.П. Белоусова ) обнаружил, что когда тонкий однородный слой смеси малоновой кислоты , подкисленного бромата и цериевой соли смешивался вместе и оставался нетронутым, получались захватывающие геометрические узоры, такие как концентрические круги и т. Д. спирали распространяются по среде. В разделе «Компьютерные развлечения» августовского выпуска журнала Scientific American за 1988 г. [73] А.К. Дьюдни обсуждал клеточный автомат [74]разработан Мартином Герхардтом и Хайке Шустером из Университета Билефельда (Германия). Этот автомат производит волновые картины, похожие на те, что в реакции Белоусова-Жаботинского.

Приложения [ править ]

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

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

Криптография [ править ]

Правило 30 изначально было предложено как возможный блочный шифр для использования в криптографии . Двумерные клеточные автоматы можно использовать для построения генератора псевдослучайных чисел . [76]

Клеточные автоматы были предложены для криптографии с открытым ключом . Односторонняя функция является эволюция конечной CA которой обратное , как полагают , будет трудно найти. Учитывая правило, любой может легко вычислить будущие состояния, но, похоже, очень сложно вычислить предыдущие состояния.

Кодирование с исправлением ошибок [ править ]

CA были применены для разработки кодов исправления ошибок в статье Д. Роя Чоудхури, С. Басу, И. Сен Гупты и П. Пала Чаудхури. В документе определяется новая схема построения кодов с исправлением однобитовых ошибок и обнаружением двойных битовых ошибок (SEC-DED) с использованием CA, а также описывается быстрый аппаратный декодер для кода. [77]

Генеративное искусство и музыка [ править ]

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

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

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

Как указывает Эндрю Илачинский в своей книге « Клеточные автоматы» , многие ученые подняли вопрос о том, является ли Вселенная клеточным автоматом. [81] Илачинский утверждает, что важность этого вопроса можно лучше оценить с помощью простого наблюдения, которое можно сформулировать следующим образом. Рассмотрим эволюцию правила 110 : если бы это была некая «физика пришельцев», что было бы разумным описанием наблюдаемых закономерностей? [82] Если наблюдатель не знал, как были созданы изображения, этот наблюдатель мог бы в конечном итоге предположить о движении некоторых частиц, подобных объектам. Действительно, физик Джеймс Кратчфилдпостроил строгую математическую теорию на основе этой идеи, доказав статистическое появление «частиц» из клеточных автоматов. [83] Тогда, согласно аргументам, можно задаться вопросом, может ли наш мир, который в настоящее время хорошо описывается, на нашем нынешнем уровне понимания, физикой с подобными частицам объектами , быть CA на самом фундаментальном уровне с пробелами в информации или неполном понимании фундаментальных данных, появляющихся в произвольном случайном порядке, что может показаться противоречащим CA.

Хотя полная теория в этом направлении не была разработана, развлечение и развитие этой гипотезы привело ученых к интересным размышлениям и плодотворным догадкам о том, как мы можем понять наш мир в дискретных рамках. Марвин Мински , пионер искусственного интеллекта, исследовал, как понять взаимодействие частиц с четырехмерной решеткой КА; [84] Конрад Цузе - изобретатель первого рабочего компьютера Z3 - разработал нерегулярно организованную решетку для решения вопроса об информационном содержании частиц. [85] Совсем недавно Эдвард Фредкинраскрыл то, что он называет «гипотезой конечной природы», т. е. идею о том, что «в конечном итоге каждое физическое количество, включая пространство и время, окажется дискретным и конечным». [86] Фредкин и Вольфрам - сильные сторонники физики, основанной на КА. В 2016 году Жерар Т Хоофт опубликовал целую книгу о развитии идеи перестроить квантовую механику с использованием клеточных автоматов. [87]

В последние годы в литературе по нестандартным вычислениям появились и другие предложения в этом направлении. Вольфрам « Новый вид науки» считает CA ключом к пониманию множества предметов, включая физику. В Математика Моделей задания -created по iLabs [88] основатель Габриэле Росси разработал Франческо Берто и Якопо Tagliabue-имеет оригинальную 2D / 3D Вселенной на основе нового «ромбического додекаэдра на основе» решетки и уникальное правило. Эта модель удовлетворяет универсальности (она эквивалентна машине Тьюринга) и полной обратимости ( желаемоеесли кто-то хочет легко сохранять различные величины и никогда не терять информацию), и он встроен в теорию первого порядка, позволяя вычислить качественные утверждения об эволюции Вселенной. [89]

Особые правила [ править ]

Конкретные типы клеточных автоматов включают:

  • Мозг Брайана
  • Клеточный автомат Кодда
  • CoDi
  • Муравей Лэнгтона
  • Петли Лэнгтона
  • Клеточные автоматы нобили
  • Правило 90
  • Правило 184
  • клеточные автоматы фон Неймана
  • Wireworld

Проблемы решены [ править ]

Проблемы, которые можно решить с помощью клеточных автоматов, включают:

  • Проблема синхронизации расстрельной команды
  • Проблема большинства

См. Также [ править ]

  • Агент-ориентированная модель
  • Теория автоматов  - Изучение абстрактных машин и автоматов
  • Двунаправленный трафик  - два потока трафика, которые текут в противоположных направлениях.
  • Циклический клеточный автомат
  • Возбудимая среда
  • Господи
  • Подвижный клеточный автомат  - метод вычислительной механики твердого тела, основанный на дискретной концепции.
  • Квантовый клеточный автомат  - абстрактная модель квантовых вычислений
  • Система поддержки пространственных решений  - Компьютеризированная помощь в принятии решений по землепользованию
  • Turmite  - машина Тьюринга, которая имеет ориентацию, а также текущее состояние и «ленту», состоящую из бесконечной двумерной сетки ячеек.
  • Категория: Клеточные автоматы в массовой культуре
  • Дискретное исчисление

Примечания [ править ]

  1. Перейти ↑ Daniel Dennett (1995), Dangerous Idea Darwin , Penguin Books, London, ISBN  978-0-14-016734-4 , ISBN 0-14-016734-X 
  2. ^ a b Вольфрам, Стивен (1983). «Статистическая механика клеточных автоматов» . Обзоры современной физики . 55 (3): 601–644. Bibcode : 1983RvMP ... 55..601W . DOI : 10.1103 / RevModPhys.55.601 .
  3. ^ Тоффоли, Томмазо; Марголус, Норман (1987). Клеточные автоматы: новая среда для моделирования . MIT Press. п. 27. ISBN 9780262200608.
  4. ^ Шифф, Джоэл Л. (2011). Клеточные автоматы: дискретный взгляд на мир . Wiley & Sons, Inc. стр. 40. ISBN 9781118030639.
  5. ^ a b c d Кир, Сейболд, Ченг 2005 , стр. 15
  6. ^ a b Bialynicki-Birula, Bialynicka-Birula 2004 , стр. 9
  7. Перейти ↑ Schiff 2011 , p. 41 год
  8. ^ Пиковер, Клиффорд А. (2009). Книга по математике: от Пифагора до 57-го измерения, 250 вех в истории математики . Sterling Publishing Company, Inc. стр. 406 . ISBN 978-1402757969.
  9. ^ а б Шифф 2011 , стр. 1
  10. ↑ Джон фон Нейман, «Общая и логическая теория автоматов», в LA Jeffress , ed., Cerebral Mechanisms in Behavior - The Hixon Symposium, John Wiley & Sons, New York, 1951, pp. 1–31.
  11. ^ Кемени, Джон Г. (1955). «Человек рассматривается как машина». Sci. Am . 192 (4): 58–67. Bibcode : 1955SciAm.192d..58K . DOI : 10.1038 / Scientificamerican0455-58 .; Sci. Являюсь. 1955; 192: 6 (опечатки).
  12. Перейти ↑ Schiff 2011 , p. 3
  13. ^ Ilachinski 2001 , стр. XXIX
  14. ^ Бялыницкий-Бируля, Беляницкой-Бируля 2004 , стр. 8
  15. ^ a b Вольфрам 2002 , стр. 876
  16. ^ фон Нейман, Джон; Беркс, Артур В. (1966). Теория самовоспроизводящихся автоматов . Университет Иллинойса Press .
  17. ^ a b Wiener, N .; Розенблют, А. (1946). «Математическая постановка задачи о проведении импульсов в сети связанных возбудимых элементов, в частности, в сердечной мышце». Arch. Inst. Кардиол. Мексика . 16 (3): 205–65. PMID 20245817 . 
  18. ^ Летичевский, АА; Решодько Л. В. (1974). "Теория Н. Винера о деятельности возбудимых сред". Кибернетика . 8 (5): 856–864. DOI : 10.1007 / bf01068458 . S2CID 121306408 . 
  19. ^ Давиденко, JM; Перцов, А.В.; Salomonsz, R .; Baxter, W .; Джалиф, Дж. (1992). «Стационарные и дрейфующие спиральные волны возбуждения в изолированной сердечной мышце». Природа . 355 (6358): 349–351. Bibcode : 1992Natur.355..349D . DOI : 10.1038 / 355349a0 . PMID 1731248 . S2CID 4348759 .  
  20. ^ Вольфрам, Стивен (2002). Новый вид науки . Wolfram Media, Inc. стр. 877 . ISBN 978-1-57955-008-0.
  21. ^ Хедлунд, Джорджия (1969). «Эндоморфизмы и автоморфизмы динамической системы сдвига». Математика. Теория систем . 3 (4): 320–3751. DOI : 10.1007 / BF01691062 . S2CID 21803927 . 
  22. Перейти ↑ Schiff 2011 , p. 182
  23. ^ Смит, Элви Рэй. "Компромиссы сложности сотовых автоматов" (PDF) .
  24. ^ Смит, Элви Рэй. «Простые вычисления - универсальные клеточные пространства» (PDF) .
  25. ^ Смит, Элви Рэй. «Простые нетривиальные самовоспроизводящиеся машины» (PDF) .
  26. ^ Смит, Элви Рэй. «Введение и обзор клеточных автоматов или теории полиавтоматов» (PDF) .
  27. ^ Гарднер, Мартин (1970). «Математические игры: фантастические комбинации нового пасьянса Джона Конвея« жизнь » » . Scientific American . 223 (4): 120–123. DOI : 10.1038 / Scientificamerican1070-120 .
  28. ^ Пол Чепмен. Жизнь универсального компьютера. http://www.igblan.free-online.co.uk/igblan/ca/ ноябрь 2002 г.
  29. Перейти ↑ Wainwright 2010 , p. 16
  30. ^ a b c d e Wolfram 2002 , стр. 880
  31. Перейти ↑ Wolfram 2002 , p. 881
  32. ↑ Митчелл, Мелани (4 октября 2002 г.). «Является ли Вселенная универсальным компьютером?». Наука . 298 (5591): 65–68. DOI : 10.1126 / science.1075073 . S2CID 122484855 . 
  33. Перейти ↑ Wolfram 2002 , pp. 1–7
  34. ↑ Джонсон, Джордж (9 июня 2002 г.). « « Новый вид науки »: вы знаете, что пространство-время? Неважно» . Нью-Йорк Таймс . Компания New York Times . Проверено 22 января 2013 года .
  35. ^ "Наука обо всем" . Экономист . 30 мая 2002 . Проверено 22 января 2013 года .
  36. ^ Вольфрам 2002 , стр. 433-546
  37. ^ Вольфрам 2002 , стр. 51-114
  38. ^ Вольфрам 2002 , стр. 115-168
  39. ^ a b c Илачинский 2001 , с. 12
  40. ^ Ilachinsky 2001 , стр. 13
  41. Перейти ↑ Wolfram 2002 , p. 231
  42. ^ Зенил, Гектор (2010). «Исследование динамических свойств клеточных автоматов и других систем на основе сжатия» (PDF) . Сложные системы . 19 (1): 1–28. DOI : 10,25088 / ComplexSystems.19.1.1 . S2CID 15364755 .  
  43. ^ Г. Каттанео; Э. Форменти; Л. Маргара (1998). «Топологический хаос и КА» . В М. Делорм; J. Mazoyer (ред.). Клеточные автоматы: параллельная модель . Springer. п. 239. ISBN 978-0-7923-5493-2.
  44. ^ Бертон Х. Вурхиз (1996). Вычислительный анализ одномерных клеточных автоматов . World Scientific. п. 8. ISBN 978-981-02-2221-5.
  45. ^ Макс Гарсон (1995). Модели массового параллелизма: анализ клеточных автоматов и нейронных сетей . Springer. п. 149 . ISBN 978-3-540-56149-1.
  46. ^ a b Ли, Вэньтянь ; Паккард, Норман (1990). «Структура пространства правил элементарных клеточных автоматов» (PDF) . Сложные системы . 4 : 281–297 . Проверено 25 января 2013 года .
  47. ^ Nicolis (1974). «Диссипативные структуры, катастрофы и образование моделей: бифуркационный анализ» (PDF) . PNAS . 71 (7): 2748–2751. Bibcode : 1974PNAS ... 71.2748N . DOI : 10.1073 / pnas.71.7.2748 . PMC 388547 . PMID 16592170 . Проверено 25 марта 2017 года .   
  48. ^ a b Кари, Яррко 1991 , стр. 379
  49. ^ Ричардсон, Д. (1972). «Мозаики с локальными преобразованиями». J. Computer System Sci . 6 (5): 373–388. DOI : 10.1016 / S0022-0000 (72) 80009-6 .
  50. ^ Мардженштерн, Морис (2007). Клеточные автоматы в гиперболических пространствах - Том I, том 1 . Архивы современников. п. 134. ISBN 978-2-84703-033-4.
  51. Перейти ↑ Schiff 2011 , p. 103
  52. ^ Аморосо, Серафино; Патт, Йель Н. (1972). «Процедуры принятия решений для сюръективности и инъективности параллельных карт для тесселяционных структур». J. Comput. Syst. Sci . 6 (5): 448–464. DOI : 10.1016 / s0022-0000 (72) 80013-8 .
  53. ^ Сатнер, Клаус (1991). «Графы Де Брейна и линейные клеточные автоматы» (PDF) . Сложные системы . 5 : 19–30.
  54. Перейти ↑ Kari, Jarkko (1990). «Обратимость 2D клеточных автоматов неразрешима». Physica D . 45 (1–3): 379–385. Bibcode : 1990PhyD ... 45..379K . DOI : 10.1016 / 0167-2789 (90) 90195-U .
  55. ^ Кари, Джаркко (1999). «О глубине схемы структурно обратимых клеточных автоматов». Fundamenta Informaticae . 38 : 93–107. DOI : 10,3233 / FI-1999-381208 .
  56. Перейти ↑ Durand-Lose, Jérôme (2001). «Представление обратимых клеточных автоматов с помощью обратимых блочных клеточных автоматов» . Дискретная математика и теоретическая информатика . AA : 145–154. Архивировано из оригинального 15 мая 2011 года.
  57. Перейти ↑ Wolfram 2002 , p. 60
  58. ^ a b Илачинский, Андрей (2001). Клеточные автоматы: дискретная вселенная . World Scientific. С. 44–45. ISBN 978-981-238-183-5.
  59. ^ Фраза « жизнеподобный клеточный автомат» восходит, по крайней мере, к Барралу, Чате и Манневиллю (1992) , которые использовали его в более широком смысле для обозначения внешних тоталистических автоматов, не обязательно двухмерных. Более конкретное значение, данное здесь, использовалось, например, в нескольких главах Adamatzky (2010) . См .: Баррал, Бернард; Шате, Хьюг; Манневиль, Пол (1992). «Коллективное поведение в семье многомерных клеточных автоматов». Физика Буквы A . 163 (4): 279–285. Bibcode : 1992PhLA..163..279B . DOI : 10.1016 / 0375-9601 (92) 91013-H .
  60. ^ Эпштайна 2010 , стр. 72-73
  61. ^ Джейкоб Арон. «Первые планеры путешествуют по постоянно меняющейся вселенной Пенроуза» . Новый ученый .
  62. ^ Мюррей, Дж. «Математическая биология II». Springer. Cite journal requires |journal= (help)
  63. ^ Pivato, М: "RealLife: Предельный континуум большечем жизнь клеточных автоматов", Теоретическая информатика ., 372 (1), март 2007, стр 46-68
  64. ^ Томита, Kohji; Курокава, Харухиса; Мурата, Сатоши (2009). «Автоматы, переписывающие графы как естественное расширение клеточных автоматов». Адаптивные сети . Понимание сложных систем. С. 291–309. DOI : 10.1007 / 978-3-642-01284-6_14 . ISBN 978-3-642-01283-9.
  65. ^ Джайлз, Джим (2002). «Что это за наука?». Природа . 417 (6886): 216–218. Bibcode : 2002Natur.417..216G . DOI : 10.1038 / 417216a . PMID 12015565 . S2CID 10636328 .  
  66. ↑ Вайнберг, Стивен (24 октября 2002 г.). «Является ли Вселенная компьютером?» . Нью-Йоркское обозрение книг . Проверено 12 октября 2012 года .
  67. ^ Вэньтянь Ли; Норман Паккард; Крис Дж. Лэнгтон (1990). «Переходные явления в пространстве правил клеточных автоматов». Physica D . 45 (1–3): 77–94. Bibcode : 1990PhyD ... 45 ... 77L . CiteSeerX 10.1.1.15.2786 . DOI : 10.1016 / 0167-2789 (90) 90175-O . 
  68. ^ a b c Кумбс, Стивен (15 февраля 2009 г.), Геометрия и пигментация морских ракушек (PDF) , стр. 3–4, заархивировано из оригинала (PDF) 7 января 2013 г. , извлечено 2 сентября 2012 г.
  69. ^ Пик, Запад; Мессинджер, Мотт (2004). «Доказательства сложной коллективной динамики и возникающих распределенных вычислений в растениях» . Труды Национальной академии наук . 101 (4): 918–922. Bibcode : 2004PNAS..101..918P . DOI : 10.1073 / pnas.0307811100 . PMC 327117 . PMID 14732685 .  
  70. ^ «Архивная копия» (PDF) . Архивировано 4 марта 2016 года из оригинального (PDF) . Проверено 14 сентября 2008 года . CS1 maint: archived copy as title (link)
  71. ^ Ilachinsky 2001 , стр. 275
  72. ^ Ив Булиган (1986). Неупорядоченные системы и биологическая организация . С. 374–375.
  73. ^ AK Dewdney, The солянка машина делает волны, Scientific American, стр. 104, август 1988 г.
  74. ^ Герхардт, М .; Шустер, Х. (1989). «Клеточный автомат, описывающий образование пространственно упорядоченных структур в химических системах». Physica D . 36 (3): 209–221. Bibcode : 1989PhyD ... 36..209G . DOI : 10.1016 / 0167-2789 (89) 90081-х .
  75. ^ Muhtaroglu Али (август 1996). «4.1 Процессор сотового автомата (CAP)». Системы на базе процессоров сотовых автоматов для сравнения генетических последовательностей / поиска в базе данных . Корнелл Университет. С. 62–74.
  76. ^ Tomassini, M .; Сиппер, М .; Перрену, М. (2000). «О генерации качественных случайных чисел двумерными клеточными автоматами». Транзакции IEEE на компьютерах . 49 (10): 1146–1151. DOI : 10.1109 / 12.888056 .
  77. ^ Чоудхури, Д. Рой; Basu, S .; Гупта, И. Сен; Чаудхури, П. Пал (июнь 1994 г.). «Дизайн CAECC - кода исправления ошибок на основе клеточных автоматов». Транзакции IEEE на компьютерах . 43 (6): 759–764. DOI : 10.1109 / 12.286310 .
  78. ^ Burraston, Дэйв, и Эрнест Эдмондс. « Клеточные автоматы в генеративной электронной музыке и звуковом искусстве: исторический и технический обзор ». Цифровое творчество 16.3 (2005): 165-185.
  79. ^ Миранда, Эдуардо Рек. « Музыка эволюционирующих клеточных автоматов: от синтеза звука к композиции ». Труды семинара 2001 г. по искусственным моделям жизни для музыкальных приложений. 2001 г.
  80. ^ Миранда, Эдуардо Рек. « Музыка эволюционирующих клеточных автоматов: от синтеза звука к композиции ». Труды семинара 2001 г. по искусственным моделям жизни для музыкальных приложений. 2001 г.
  81. ^ Ilachinsky 2001 , стр. 660
  82. ^ Ilachinsky 2001 , стр. 661-662
  83. ^ JP Crutchfield, "Исчисления возникновения: вычисление, динамика и индукция" , Physica D 75, 11–54, 1994.
  84. Перейти ↑ Minsky, M. (1982). «Сотовый вакуум». Международный журнал теоретической физики . 21 (537–551): 1982. Bibcode : 1982IJTP ... 21..537M . DOI : 10.1007 / bf02650183 . S2CID 189845773 . 
  85. ^ К. Цузе, "Вычислительная вселенная", Int. Jour. Тео. Phy. 21, 589–600, 1982.
  86. ^ Е. Фредкин, "Цифровая механика: информационный процесс, основанный на обратимых универсальных клеточных автоматах", Physica D 45, 254–270, 1990
  87. ^ Джерард 'т Хоофт, 2016, Интерпретация квантовой механики клеточным автоматом , Springer International Publishing, DOI 10.1007 / 978-3-319-41285-6, Открытый доступ - [1]
  88. ^ "Ilabs" .
  89. ↑ F. Berto, G. Rossi, J. Tagliabue, The Mathematics of the Models of Reference. Архивировано 11 марта 2012 г. в Wayback Machine , College Publications , 2010.

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

  • Адамацкий, Андрей , изд. (2010). Игра жизни в клеточных автоматах . Springer. ISBN 978-1-84996-216-2.
  • Бялыницки-Бирула, Иво; Бялыницка-Бирула, Ивона (2004). Моделирование реальности: как компьютеры отражают жизнь . Издательство Оксфордского университета . ISBN 978-0198531005.
  • Chopard, Bastien; Дро, Мишель (2005). Моделирование физических систем клеточными автоматами . Издательство Кембриджского университета . ISBN 978-0-521-46168-9.
  • Гутовиц, Говард, изд. (1991). Клеточные автоматы: теория и эксперимент . MIT Press . ISBN 9780262570862.
  • Илачинский, Андрей (2001). Клеточные автоматы: дискретная вселенная . World Scientific . ISBN 9789812381835.
  • Kier, Lemont B .; Сейболд, Пол Дж .; Ченг, Чао-Кун (2005). Моделирование химических систем с использованием клеточных автоматов . Springer. ISBN 9781402036576.
  • Крок, Иржи; Хименес-Моралес, Франсиско; Гуисадо, Хосе Луис; Лемос, Мария Кармен; Ткач, Якуб (декабрь 2019 г.). "Построение эффективных вычислительных моделей сотовых автоматов сложных систем: история вопроса, приложения, результаты, программное обеспечение и патологии" . Достижения в сложных системах . 22 (5): 1950013 (38 страниц). DOI : 10.1142 / S0219525919500139 .
  • Вольфрам, Стивен (2002). Новый вид науки . Wolfram Media . ISBN 978-1579550080.
  • FAQ по сотовым автоматам от группы новостей comp.theory.cell-automata
  • «Обследование района» (включает обсуждение треугольных сеток и крупных соседних центров сертификации)
  • фон Нейман, Джон, 1966, Теория самовоспроизводящихся автоматов , изд. A. Burks, Univ. из Иллинойс Пресс, Урбана, Иллинойс.
  • Записная книжка Космы Шализи по клеточным автоматам содержит обширный список академических и профессиональных справочных материалов.
  • Статьи Вольфрама по CA
  • AM Тьюринг. 1952. Химические основы морфогенеза. Фил. Пер. Королевское общество , т. B237, стр. 37–72. (предлагает реакцию-диффузию, тип непрерывного автомата).
  • Развитие клеточных автоматов с помощью генетических алгоритмов: обзор последних работ, Мелани Митчелл, Джеймс П. Кратчфельд, Раджарши Дас (В трудах Первой международной конференции по эволюционным вычислениям и их приложениям (EvCA'96). Москва, Россия: Российская академия Наук, 1996.)
  • Эволюционный дизайн коллективных вычислений в клеточных автоматах, Джеймс П. Кратчфельд, Мелани Митчелл, Раджарши Дас (в Дж. П. Крачелд и П. К. Шустер (редакторы), Evolutionary Dynamics | Изучение взаимодействия отбора, нейтральности, случайности и функции. Новое Йорк: Oxford University Press, 2002.)
  • Эволюция новых вычислений, Джеймс П. Кратчфилд и Мелани Митчелл (Технический отчет SFI 94-03-012)
  • Гангули, Сикдар, Дойч и Чаудхури «Обзор клеточных автоматов»

Внешние ссылки [ править ]

  • Берто, Франческо; Тальябу, Якопо. «Клеточные автоматы» . В Залте, Эдвард Н. (ред.). Стэнфордская энциклопедия философии .
  • Mirek's Cellebration - Дом бесплатного программного обеспечения для обозревателя клеточных автоматов MCell и MJCell и библиотек правил. Программа поддерживает большое количество одномерных и двухмерных правил. На сайте есть как обширный словарь правил, так и множество галерей изображений, загруженных примерами правил. MCell - это приложение для Windows, а MJCell - это Java-апплет. Исходный код доступен.
  • Современные клеточные автоматы - Простые в использовании интерактивные экспонаты живых цветных двумерных клеточных автоматов на базе Java-апплета. Включены экспонаты традиционных, обратимых, гексагональных, многошаговых правил генерации фракталов и шаблонов. Для просмотра предусмотрены тысячи правил. Доступно бесплатное программное обеспечение.
  • Циклы саморепликации в сотовом пространстве - Java-апплет демонстрирует циклы саморепликации.
  • Коллекция из более чем 10 различных апплетов клеточных автоматов (в виртуальной лаборатории Университета Монаша)
  • Голли поддерживает фон Неймана, Нобили, GOL и многие другие системы клеточных автоматов. Разработано Томасом Рокицки и Эндрю Треворроу. Это единственный доступный в настоящее время симулятор, который может продемонстрировать самовоспроизведение типа фон Неймана.
  • Жизнь Фурье - набор правил, демонстрирующих самовоспроизводящиеся паттерны, спонтанно возникающие из поля случайных клеток. Большинство правил было найдено с помощью алгоритма, который использует преобразование Фурье для обнаружения саморепликации.
  • Атлас Вольфрама - атлас различных типов одномерных клеточных автоматов.
  • Конвей жизнь
  • Первое воспроизводящееся существо, созданное в симуляторе жизни
  • Математика эталонных моделей , включающая общий учебник по СА, интерактивный апплет, бесплатный код и ресурсы по СА как модели фундаментальной физики
  • Лаборатория клеточных автоматов Fourmilab
  • Занятые ящики , 3-D, обратимая, SALT- архитектура CA
  • Репозиторий сотовых автоматов (исследователи CA, исторические ссылки, бесплатное программное обеспечение, книги и не только)
  • Клеточные автоматы в 256 правилах (интерактивная визуализация 256 элементарных правил на одном листе)
  • Петри - структура клеточного автомата Go