✖


Jump to content

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

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

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

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

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

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

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

Красные ячейки — это окрестности Мура для синей ячейки.
Красные клетки — это окрестности фон Неймана для синей ячейки. «Перекрестное соседство» диапазона 2 также включает розовые ячейки.

Один из способов смоделировать двумерный клеточный автомат — использовать бесконечный лист миллиметровой бумаги и набор правил, которым должны следовать ячейки. Каждый квадрат называется «клеткой», и каждая ячейка имеет два возможных состояния: черное и белое. Окрестность . ячейки — это близлежащие, обычно соседние клетки Двумя наиболее распространенными типами окрестностей являются окрестности фон Неймана и окрестности Мура . [5] Первый, названный в честь основателя теории клеточных автоматов, состоит из четырех ортогонально соседних ячеек. [5] Последний включает в себя окрестность фон Неймана, а также четыре соседние по диагонали ячейки. [5] Для такой ячейки и ее окрестности Мура имеется 512 (= 2 9 ) возможные закономерности. Для каждого из 512 возможных шаблонов в таблице правил будет указано, будет ли центральная ячейка черной или белой в следующий интервал времени. «Игра жизни» Конвея — популярная версия этой модели. Другим распространенным типом соседства является расширенное соседство фон Неймана , которое включает в себя две ближайшие ячейки в каждом ортогональном направлении, всего восемь. [5] Общее уравнение для общего числа возможных автоматов: k к с , где k — количество возможных состояний ячейки, а s — количество соседних ячеек (включая саму вычисляемую ячейку), используемых для определения следующего состояния ячейки. [6] Таким образом, в двумерной системе с окрестностью Мура общее число возможных автоматов будет равно 2 2 9 , или 1,34 × 10 154 .

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

Тор . , тороидальная форма

Клеточные автоматы часто моделируются на конечной, а не на бесконечной сетке. В двух измерениях Вселенная была бы прямоугольником, а не бесконечной плоскостью. Очевидная проблема с конечными сетками — как обращаться с ячейками на краях. То, как они обрабатываются, повлияет на значения всех ячеек сетки. Один из возможных способов — оставить значения в этих ячейках постоянными. Другой метод — по-разному определить окрестности для этих ячеек. Можно было бы сказать, что у них меньше соседей, но тогда пришлось бы также определять новые правила для ячеек, расположенных на ребрах. Эти ячейки обычно обрабатываются периодическими граничными условиями, что приводит к тороидальному расположению: когда одна выходит сверху, другая входит в соответствующую позицию внизу, а когда одна выходит слева, другая входит справа. (По сути, это имитирует бесконечное периодическое замощение, и в области уравнений в частных производных это иногда называют периодическими граничными условиями.) Это можно представить как склеивание левого и правого краев прямоугольника, чтобы сформировать трубку, а затем склеивание верхней части прямоугольника. и нижние края трубки, образуя тор (форма пончика). Вселенные других измерений обрабатываются аналогично. Это решает граничные проблемы с окрестностями, но еще одним преимуществом является то, что его легко программировать с использованием модульных арифметических функций. Например, в одномерном клеточном автомате, подобном примерам ниже, окрестность ячейки x i т { x i −1 т -1 , х я т -1 , х я +1 т -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] его правила таковы:

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

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

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

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

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

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

Эти определения носят качественный характер и допускают некоторую интерпретацию. Согласно Вольфраму, «...почти в любой общей схеме классификации неизбежно возникают случаи, которые относят к одному классу по одному определению, а к другому классу по другому определению. То же самое и с клеточными автоматами: иногда существуют правила... которые показать некоторые особенности одного класса и некоторые другие». [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]

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

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

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

Один из способов — использовать что-то отличное от прямоугольной (кубической и т. д. ) сетки. Например, если плоскость покрыта правильными шестиугольниками , эти шестиугольники можно использовать в качестве ячеек. Во многих случаях полученные клеточные автоматы эквивалентны автоматам с прямоугольными сетками со специально разработанными окрестностями и правилами. Другой вариант — сделать саму сетку нерегулярной, как, например, в случае с плитками Пенроуза . [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
Правило 30 клеточный автомат
(двоичный 00011110 = десятичный 30)
текущий шаблон 111 110 101 100 011 010 001 000
новое состояние центральной ячейки 0 0 0 1 1 1 1 0

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

Правило 110
Правило 110 клеточный автомат
(двоичный 01101110 = десятичный 110)
текущий шаблон 111 110 101 100 011 010 001 000
новое состояние центральной ячейки 0 1 1 0 1 1 1 0

Правило 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] Это наблюдение является основой фразы « край хаоса» и напоминает фазовый переход в термодинамике .

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

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

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

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

Вот некоторые примеры биологических явлений, моделируемых клеточными автоматами с простым пространством состояний:

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

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

Химия [ править ]

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

Физика [ править ]

Визуализация решеточного газового автомата. Оттенки серого отдельных пикселей пропорциональны плотности частиц газа (от 0 до 4) в этом пикселе. Газ окружен оболочкой из желтых ячеек, которые действуют как отражатели, создавая замкнутое пространство.

Вероятностные клеточные автоматы используются в статистической физике и физике конденсированного состояния для изучения таких явлений, как гидродинамика и фазовые переходы. Модель Изинга является типичным примером, в котором каждая ячейка может находиться в одном из двух состояний, называемых «верхнее» и «нижнее», что представляет собой идеализированное представление магнита . Регулируя параметры модели, можно изменять долю ячеек, находящихся в одном и том же состоянии, таким образом, чтобы объяснить, как ферромагнетики размагничиваются при нагревании. Более того, результаты изучения фазового перехода размагничивания могут быть перенесены и на другие фазовые переходы, например испарение жидкости в газ; эта удобная перекрестная применимость известна как универсальность . [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] Поскольку эти правила клеточного автомата являются детерминированными , каждый генерируемый лабиринт однозначно определяется его случайным начальным шаблоном. Это существенный недостаток, поскольку лабиринты обычно относительно предсказуемы.

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

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

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


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

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

Цитаты [ править ]

  1. ^ Дэниел Деннетт (1995), Опасная идея Дарвина , Penguin Books, Лондон, ISBN   978-0-14-016734-4 , ISBN   0-14-016734-X
  2. ^ Jump up to: Перейти обратно: а б Вольфрам, Стивен (1983). «Статистическая механика клеточных автоматов» . Обзоры современной физики . 55 (3): 601–644. Бибкод : 1983РвМП...55..601Вт . дои : 10.1103/RevModPhys.55.601 . Архивировано из оригинала 21 сентября 2013 года . Проверено 28 февраля 2011 г.
  3. ^ Тоффоли, Томмазо; Марголус, Норман (1987). Клеточные автоматы: новая среда для моделирования . МТИ Пресс. п. 27. ISBN  9780262200608 .
  4. ^ Шифф, Джоэл Л. (2011). Клеточные автоматы: дискретный взгляд на мир . Wiley & Sons, Inc. с. 40. ИСБН  9781118030639 .
  5. ^ Jump up to: Перейти обратно: а б с д Кир, Сейболд, Ченг 2005 , с. 15
  6. ^ Jump up to: Перейти обратно: а б Бялыницкий-Бирула, Бялыницка-Бирула 2004 , с. 9
  7. ^ Шифф 2011 , с. 41
  8. ^ Пиковер, Клиффорд А. (2009). Книга по математике: от Пифагора до 57-го измерения, 250 вех в истории математики . Стерлинг Паблишинг Компани, Инк. 406 . ISBN  978-1402757969 .
  9. ^ Jump up to: Перейти обратно: а б Шифф 2011 , с. 1
  10. ^ Джон фон Нейман, «Общая и логическая теория автоматов», в издании Л.А. Джеффресса , «Церебральные механизмы в поведении» - Симпозиум Хиксона, John Wiley & Sons, Нью-Йорк, 1951, стр. 1–31.
  11. ^ Кемени, Джон Г. (1955). «Человек как машина». наук. Являюсь . 192 (4): 58–67. Бибкод : 1955SciAm.192d..58K . doi : 10.1038/scientificamerican0455-58 . ; наук. Являюсь. 1955 год; 192:6 (ошибка).
  12. ^ Шифф 2011 , с. 3
  13. ^ Илачинский 2001 , с. XXIX
  14. ^ Бялиницкий-Бирула, Бялыницка-Бирула 2004 , с. 8
  15. ^ Jump up to: Перейти обратно: а б Вольфрам 2002 , с. 876
  16. ^ фон Нейман 1966
  17. ^ Jump up to: Перейти обратно: а б Винер, Н.; Розенблют, А. (1946). «Математическая формулировка задачи о проведении импульсов в сети связанных возбудимых элементов, в частности в сердечной мышце». Арх. Инст. Кардиол. Мексика . 16 (3): 205–65. ПМИД   20245817 .
  18. ^ Летичевский А.А.; Решодко, Л. В. (1974). «Теория Н. Винера о деятельности возбудимых сред». Кибернетика . 8 (5): 856–864. дои : 10.1007/bf01068458 . S2CID   121306408 .
  19. ^ Давиденко Ю.М.; Перцов А.В.; Саломонс, Р.; Бакстер, В.; Джалифе, Дж. (1992). «Стоячие и дрейфующие спиральные волны возбуждения в изолированной сердечной мышце». Природа . 355 (6358): 349–351. Бибкод : 1992Natur.355..349D . дои : 10.1038/355349a0 . ПМИД   1731248 . S2CID   4348759 .
  20. ^ Хедлунд, Джорджия (1969). «Эндоморфизмы и автоморфизмы динамической системы сдвига». Математика. Теория систем . 3 (4): 320–3751. дои : 10.1007/BF01691062 . S2CID   21803927 .
  21. ^ Шифф 2011 , с. 182
  22. ^ Смит, Элви Рэй. «Компромиссы сложности клеточных автоматов» (PDF) .
  23. ^ Смит, Элви Рэй. «Простые вычисления — универсальные клеточные пространства» (PDF) .
  24. ^ Смит, Элви Рэй. «Простые нетривиальные самовоспроизводящиеся машины» (PDF) .
  25. ^ Смит, Элви Рэй. «Введение и обзор клеточных автоматов или теории полиавтоматов» (PDF) .
  26. ^ Гарднер, Мартин (1970). «Математические игры: фантастические комбинации нового пасьянса Джона Конвея «Жизнь» » . Научный американец . 223 (4): 120–123. doi : 10.1038/scientificamerican1070-120 .
  27. ^ Пол Чепмен. Жизнь универсального компьютера. http://www.igblan.free-online.co.uk/igblan/ca/ Архивировано 6 сентября 2009 г. в Wayback Machine , ноябрь 2002 г.
  28. ^ Уэйнрайт 2010 , с. 16
  29. ^ Jump up to: Перейти обратно: а б с д и Вольфрам 2002 , с. 880
  30. ^ Вольфрам 2002 , с. 881
  31. ^ Митчелл, Мелани (4 октября 2002 г.). «Является ли Вселенная универсальным компьютером?». Наука . 298 (5591): 65–68. дои : 10.1126/science.1075073 . S2CID   122484855 .
  32. ^ Jump up to: Перейти обратно: а б с Илачинский 2001 , с. 12
  33. ^ Илачинский 2001 , с. 13
  34. ^ Вольфрам 2002 , с. 231
  35. ^ Зенил, Гектор (2010). «Исследование динамических свойств клеточных автоматов и других систем на основе сжатия» (PDF) . Сложные системы . 19 (1): 1–28. arXiv : 0910.4042 . дои : 10.25088/ComplexSystems.19.1.1 . S2CID   15364755 .
  36. ^ Дж. Каттанео; Э. Форменти; Л. Маргара (1998). «Топологический хаос и КА» . У г-на Делорма; Дж. Мазойер (ред.). Клеточные автоматы: параллельная модель . Спрингер. п. 239. ИСБН  978-0-7923-5493-2 .
  37. ^ Бертон Х. Вурхис (1996). Вычислительный анализ одномерных клеточных автоматов . Всемирная научная. п. 8. ISBN  978-981-02-2221-5 .
  38. ^ Макс Гарсон (1995). Модели массового параллелизма: анализ клеточных автоматов и нейронных сетей . Спрингер. п. 149 . ISBN  978-3-540-56149-1 .
  39. ^ Jump up to: Перейти обратно: а б Ли, Вэньтянь ; Паккард, Норман (1990). «Структура элементарного пространства правил клеточных автоматов» (PDF) . Сложные системы . 4 : 281–297 . Проверено 25 января 2013 г.
  40. ^ Николис (1974). «Диссипативные структуры, катастрофы и формирование закономерностей: бифуркационный анализ» (PDF) . ПНАС . 71 (7): 2748–2751. Бибкод : 1974PNAS...71.2748N . дои : 10.1073/pnas.71.7.2748 . ПМЦ   388547 . ПМИД   16592170 . Проверено 25 марта 2017 г.
  41. ^ Jump up to: Перейти обратно: а б Кари, Яррко 1991 , стр. 379.
  42. ^ Ричардсон, Д. (1972). «Тесселяции с локальными преобразованиями» . Дж. Компьютер. Сист. Наука . 6 (5): 373–388. дои : 10.1016/S0022-0000(72)80009-6 .
  43. ^ Маргенштерн, Морис (2007). Клеточные автоматы в гиперболических пространствах – Том I, Том 1 . Архивы современников. п. 134. ИСБН  978-2-84703-033-4 .
  44. ^ Шифф 2011 , с. 103
  45. ^ Аморосо, Серафино; Патт, Йель Н. (1972). «Процедуры принятия решения о сюръективности и инъективности параллельных отображений для структур тесселяции» . Дж. Компьютер. Сист. Наука . 6 (5): 448–464. дои : 10.1016/s0022-0000(72)80013-8 .
  46. ^ Сатнер, Клаус (1991). «Графы Де Брёйна и линейные клеточные автоматы» (PDF) . Сложные системы . 5 :19–30.
  47. ^ Кари, Яркко (1990). «Обратимость двумерных клеточных автоматов неразрешима». Физика Д. 45 (1–3): 379–385. Бибкод : 1990PhyD...45..379K . дои : 10.1016/0167-2789(90)90195-У .
  48. ^ Кари, Яркко (1999). «О глубине схемы структурно обратимых клеточных автоматов». Фундамента информатики . 38 : 93–107. дои : 10.3233/FI-1999-381208 .
  49. ^ Дюран-Лозе, Жером (2001). «Представление обратимых клеточных автоматов с помощью обратимых блочных клеточных автоматов» . Дискретная математика и теоретическая информатика . АА : 145–154. Архивировано из оригинала 15 мая 2011 года.
  50. ^ Вольфрам 2002 , с. 60
  51. ^ Jump up to: Перейти обратно: а б Илачинский, Эндрю (2001). Клеточные автоматы: дискретная вселенная . Всемирная научная. стр. 44–45. ISBN  978-981-238-183-5 .
  52. ^ Фраза «живой клеточный автомат» восходит, по крайней мере, к Барралу, Шате и Манневилю (1992) , которые использовали ее в более широком смысле для обозначения внешних тоталистических автоматов, не обязательно двухмерных. Более конкретное значение, данное здесь, использовалось, например, в нескольких главах Адамацкого (2010) . Видеть: Баррал, Бернар; Шатэ, Хьюг; Манневиль, Пол (1992). «Коллективное поведение в семье многомерных клеточных автоматов». Буквы по физике А. 163 (4): 279–285. Бибкод : 1992PhLA..163..279B . дои : 10.1016/0375-9601(92)91013-H .
  53. ^ Эппштейн 2010 , стр. 72–73.
  54. ^ Джейкоб Арон. «Первые планеры путешествуют по постоянно меняющейся вселенной Пенроуза» . Новый учёный .
  55. ^ Мюррей, доктор юридических наук (2003). Математическая биология (3-е изд.). Нью-Йорк: Спрингер. ISBN  0-387-95228-4 .
  56. ^ Пивато, М.: «RealLife: предел континуума клеточных автоматов большего, чем жизнь», Theoretical Computer Science , 372 (1), март 2007 г., стр. 46–68
  57. ^ Томита, Коджи; Курокава, Харухиса; Мурата, Сатоши (2009). «Автоматы, переписывающие графы, как естественное расширение клеточных автоматов». Адаптивные сети . Понимание сложных систем. стр. 291–309. дои : 10.1007/978-3-642-01284-6_14 . ISBN  978-3-642-01283-9 .
  58. ^ Джайлз, Джим (2002). «Что это за наука?» . Природа . 417 (6886): 216–218. Бибкод : 2002Natur.417..216G . дои : 10.1038/417216a . ПМИД   12015565 . S2CID   10636328 .
  59. ^ Вайнберг, Стивен (24 октября 2002 г.). «Является ли Вселенная компьютером?» . Нью-Йоркское обозрение книг . 49 (16) . Проверено 12 октября 2012 г.
  60. ^ Вэньтянь Ли; Норман Паккард; Крис Дж. Лэнгтон (1990). «Переходные явления в пространстве правил клеточных автоматов». Физика Д. 45 (1–3): 77–94. Бибкод : 1990PhyD...45...77L . CiteSeerX   10.1.1.15.2786 . дои : 10.1016/0167-2789(90)90175-О .
  61. ^ Jump up to: Перейти обратно: а б с Кумбс, Стивен (15 февраля 2009 г.), Геометрия и пигментация морских ракушек (PDF) , стр. 3–4, заархивировано из оригинала (PDF) 7 января 2013 г. , получено 2 сентября 2012 г.
  62. ^ Пик, Запад; Мессингер, Мотт (2004). «Доказательства сложной коллективной динамики и возникающих распределенных вычислений на растениях» . Труды Национальной академии наук . 101 (4): 918–922. Бибкод : 2004PNAS..101..918P . дои : 10.1073/pnas.0307811100 . ПМК   327117 . ПМИД   14732685 .
  63. ^ «Архивная копия» (PDF) . Архивировано из оригинала (PDF) 25 июля 2010 года . Проверено 14 сентября 2008 г. {{cite web}}: CS1 maint: архивная копия в заголовке ( ссылка )
  64. ^ Илачинский 2001 , с. 275
  65. ^ Ив Булиганд (1986). «Фибробласты, морфогенез и клеточные автоматы». Неупорядоченные системы и биологическая организация . стр. 374–375.
  66. ^ Ильина, Ольга; Гриценко Павел Георгиевич; Сига, Саймон; Липпольдт, Юрген; Ла Порта, Катерина AM; Чепижко, Александр; Гроссер, Штеффен; Вуллингс, Манон; Баккер, Герт-Ян; Старрус, Йорн; Балт, Питер (сентябрь 2020 г.). «Клеточно-клеточная адгезия и ограничение трехмерной матрицы определяют застревание переходов при инвазии рака молочной железы» . Природная клеточная биология . 22 (9): 1103–1115. дои : 10.1038/s41556-020-0552-6 . ISSN   1465-7392 . ПМЦ   7502685 . ПМИД   32839548 .
  67. ^ Реер, Дэвид; Клинк, Барбара; Дойч, Андреас; Восс-Бёме, Аня (11 августа 2017 г.). «Неоднородность клеточной адгезии усиливает распространение опухолевых клеток: новые выводы из математической модели» . Биология Директ . 12 (1): 18. дои : 10.1186/s13062-017-0188-z . ISSN   1745-6150 . ПМЦ   5553611 . ПМИД   28800767 .
  68. ^ Хадзикиро, Х.; Басанта, Д.; Саймон, М.; Шаллер, К.; Дойч, А. (1 марта 2012 г.). « 'Go or Grow': ключ к возникновению инвазии при опухолевой прогрессии?» . Математическая медицина и биология . 29 (1): 49–65. дои : 10.1093/imammb/dqq011 . ISSN   1477-8599 . ПМИД   20610469 .
  69. ^ А.К. Дьюдни, Машина-солянка поднимает волну, Scientific American, стр. 104, август 1988 г.
  70. ^ Герхардт, М.; Шустер, Х. (1989). «Клеточный автомат, описывающий образование пространственно упорядоченных структур в химических системах». Физика Д. 36 (3): 209–221. Бибкод : 1989PhyD...36..209G . дои : 10.1016/0167-2789(89)90081-x .
  71. ^ Сетна, Джеймс П. (2008). Статистическая механика: энтропия, параметры порядка и сложность . Издательство Оксфордского университета . ISBN  978-0-198-56677-9 . OCLC   845714772 .
  72. ^ Кардар, Мехран (2007). Статистическая физика полей . Издательство Кембриджского университета . ISBN  978-0-521-87341-3 . OCLC   920137477 .
  73. ^ Каппелли, Андреа; Зубер, Жан-Бернар (2010). «Классификация конформных теорий поля ADE» . Схоларпедия . 5 (4): 10314. arXiv : 0911.3242 . Бибкод : 2010SchpJ...510314C . doi : 10.4249/scholarpedia.10314 . S2CID   18207779 .
  74. ^ Мухтароглу, Али (август 1996 г.). «4.1 Процессор клеточного автомата (CAP)». Системы на базе процессоров клеточных автоматов для сравнения генетических последовательностей/поиска в базах данных . Корнелльский университет. стр. 62–74.
  75. ^ Томассини, М.; Сиппер, М.; Перрено, М. (2000). «О генерации высококачественных случайных чисел двумерными клеточными автоматами». Транзакции IEEE на компьютерах . 49 (10): 1146–1151. дои : 10.1109/12.888056 . S2CID   10139169 .
  76. ^ Чоудхури, Д. Рой; Басу, С.; Гупта, И. Сен; Чаудхури, П. Пал (июнь 1994 г.). «Проектирование CAECC - кода исправления ошибок на основе клеточных автоматов». Транзакции IEEE на компьютерах . 43 (6): 759–764. дои : 10.1109/12.286310 .
  77. ^ Беррастон, Дэйв и Эрнест Эдмондс. « Клеточные автоматы в генеративной электронной музыке и звуковом искусстве: историко-технический обзор ». Цифровое творчество 16.3 (2005): 165–185.
  78. ^ Миранда, Эдуардо Рек. « Развитие музыки клеточных автоматов: от синтеза звука к композиции ». Материалы семинара 2001 г. по моделям искусственной жизни для музыкальных приложений. 2001.
  79. ^ Эшлок, Дэниел; Крейцер, Мэтью (2020). «Развитие разнообразных карт уровней на основе клеточных автоматов» . Материалы 6-й Международной конференции по разработке программного обеспечения для оборонных приложений . Достижения в области интеллектуальных систем и вычислений. Том. 925. стр. 10–23. дои : 10.1007/978-3-030-14687-0_2 . ISBN  978-3-030-14686-3 . S2CID   85562837 .
  80. ^ Jump up to: Перейти обратно: а б с д и Натаниэль Джонстон; и др. (21 августа 2010 г.). «Лабиринт — LifeWiki» . ЖизньВики . Проверено 1 марта 2011 г.

Цитируемые работы [ править ]

Дальнейшее чтение [ править ]

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

Викискладе есть медиафайлы по теме клеточных автоматов .
В Wikibooks есть книга на тему: Клеточные автоматы.
  • Mirek's Cellebration - дом для бесплатного программного обеспечения MCell и MJCell для исследования клеточных автоматов и библиотек правил. Программное обеспечение поддерживает большое количество 1D и 2D правил. На сайте представлен как обширный словарь правил, так и множество галерей изображений с примерами правил. MCell — это приложение для Windows, а MJCell — это Java-апплет. Исходный код доступен.
  • Golly поддерживает фон Неймана, Nobili, GOL и множество других систем клеточных автоматов. Разработано Томасом Рокицки и Эндрю Треворроу. Это единственный доступный в настоящее время симулятор, который может продемонстрировать самовоспроизведение типа фон Неймана.
  • Wolfram Atlas – атлас различных типов одномерных клеточных автоматов.
  • Конвей Лайф
  • Часто задаваемые вопросы по клеточному автомату из группы новостей comp.theory.cell-automata
  • «Обследование окрестностей» (включает обсуждение треугольных сеток и более крупных центров сертификации окрестностей)
  • Записная книжка Космы Шализи по клеточным автоматам содержит обширный список академических и профессиональных справочных материалов.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Cellular_automaton&oldid=1220605594"
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 2a18f9dbf0b515878e5d406fed0cda17__1713980640
URL1:https://arc.ask3.ru/arc/aa/2a/17/2a18f9dbf0b515878e5d406fed0cda17.html
Заголовок, (Title) документа по адресу, URL1:
Cellular automaton - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)