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

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

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

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

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

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

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

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

Despite its simplicity, the system achieves an impressive diversity of behavior, fluctuating between apparent randomness and order. One of the most apparent features of the Game of Life is the frequent occurrence of gliders, arrangements of cells that essentially move themselves across the grid. It is possible to arrange the automaton so that the gliders interact to perform computations, and after much effort it has been shown that the Game of Life can emulate a universal Turing machine.[27] It was viewed as a largely recreational topic, and little follow-up work was done outside of investigating the particularities of the Game of Life and a few related rules in the early 1970s.[28]

Stephen Wolfram independently began working on cellular automata in mid-1981 after considering how complex patterns seemed formed in nature in violation of the Second Law of Thermodynamics.[29] His investigations were initially spurred by an interest in modelling systems such as neural networks.[29] He published his first paper in Reviews of Modern Physics investigating elementary cellular automata (Rule 30 in particular) in June 1983.[2][29] The unexpected complexity of the behavior of these simple rules led Wolfram to suspect that complexity in nature may be due to similar mechanisms.[29] His investigations, however, led him to realize that cellular automata were poor at modelling neural networks.[29] Additionally, during this period Wolfram formulated the concepts of intrinsic randomness and computational irreducibility,[30] and suggested that rule 110 may be universal—a fact proved later by Wolfram's research assistant Matthew Cook in the 1990s.[31]

In 2002 Wolfram published a 1280-page text A New Kind of Science, which extensively argues that the discoveries about cellular automata are not isolated facts but are robust and have significance for all disciplines of science.[32] Despite confusion in the press,[33][34] the book did not argue for a fundamental theory of physics based on cellular automata,[35] and although it did describe a few specific physical models based on cellular automata,[36] it also provided models based on qualitatively different abstract systems.[37]

Classification[edit]

Wolfram, in A New Kind of Science and several papers dating from the mid-1980s, defined four classes into which cellular automata and several other simple computational models can be divided depending on their behavior. While earlier studies in cellular automata tended to try to identify type of patterns for specific rules, Wolfram's classification was the first attempt to classify the rules themselves. In order of complexity the classes are:

  • Class 1: Nearly all initial patterns evolve quickly into a stable, homogeneous state. Any randomness in the initial pattern disappears.[38]
  • Class 2: Nearly all initial patterns evolve quickly into stable or oscillating structures. Some of the randomness in the initial pattern may filter out, but some remains. Local changes to the initial pattern tend to remain local.[38]
  • Class 3: Nearly all initial patterns evolve in a pseudo-random or chaotic manner. Any stable structures that appear are quickly destroyed by the surrounding noise. Local changes to the initial pattern tend to spread indefinitely.[38]
  • Class 4: Nearly all initial patterns evolve into structures that interact in complex and interesting ways, with the formation of local structures that are able to survive for long periods of time.[39] Class 2 type stable or oscillating structures may be the eventual outcome, but the number of steps required to reach this state may be very large, even when the initial pattern is relatively simple. Local changes to the initial pattern may spread indefinitely. Wolfram has conjectured that many class 4 cellular automata, if not all, are capable of universal computation. This has been proven for Rule 110 and Conway's Game of Life.

These definitions are qualitative in nature and there is some room for interpretation. According to Wolfram, "...with almost any general classification scheme there are inevitably cases which get assigned to one class by one definition and another class by another definition. And so it is with cellular automata: there are occasionally rules...that show some features of one class and some of another."[40] Wolfram's classification has been empirically matched to a clustering of the compressed lengths of the outputs of cellular automata.[41]

There have been several attempts to classify cellular automata in formally rigorous classes, inspired by the Wolfram's classification. For instance, Culik and Yu proposed three well-defined classes (and a fourth one for the automata not matching any of these), which are sometimes called Culik-Yu classes; membership in these proved undecidable.[42][43][44]Wolfram's class 2 can be partitioned into two subgroups of stable (fixed-point) and oscillating (periodic) rules.[45]

The idea that there are 4 classes of dynamical system came originally from nobel-prize winning chemist Ilya Prigogine who identified these 4 classes of thermodynamical systems - (1) systems in thermodynamic equilibrium, (2) spatially/temporally uniform systems, (3) chaotic systems, and (4) complex far-from-equilibrium systems with dissipative structures (see figure 1 in Nicolis' paper (Prigogine's student)).[46]

Reversible[edit]

Main article: Reversible cellular automaton

A cellular automaton is reversible if, for every current configuration of the cellular automaton, there is exactly one past configuration (preimage).[47] If one thinks of a cellular automaton as a function mapping configurations to configurations, reversibility implies that this function is bijective.[47] If a cellular automaton is reversible, its time-reversed behavior can also be described as a cellular automaton; this fact is a consequence of the Curtis–Hedlund–Lyndon theorem, a topological characterization of cellular automata.[48][49] For cellular automata in which not every configuration has a preimage, the configurations without preimages are called Garden of Eden patterns.[50]

For one-dimensional cellular automata there are known algorithms for deciding whether a rule is reversible or irreversible.[51][52] However, for cellular automata of two or more dimensions reversibility is undecidable; that is, there is no algorithm that takes as input an automaton rule and is guaranteed to determine correctly whether the automaton is reversible. The proof by Jarkko Kari is related to the tiling problem by Wang tiles.[53]

Reversible cellular automata are often used to simulate such physical phenomena as gas and fluid dynamics, since they obey the laws of thermodynamics. Such cellular automata have rules specially constructed to be reversible. Such systems have been studied by Tommaso Toffoli, Norman Margolus and others. Several techniques can be used to explicitly construct reversible cellular automata with known inverses. Two common ones are the second-order cellular automaton and the block cellular automaton, both of which involve modifying the definition of a cellular automaton in some way. Although such automata do not strictly satisfy the definition given above, it can be shown that they can be emulated by conventional cellular automata with sufficiently large neighborhoods and numbers of states, and can therefore be considered a subset of conventional cellular automata. Conversely, it has been shown that every reversible cellular automaton can be emulated by a block cellular automaton.[54][55]

Totalistic[edit]

A special class of cellular automata are totalistic cellular automata. The state of each cell in a totalistic cellular automaton is represented by a number (usually an integer value drawn from a finite set), and the value of a cell at time t depends only on the sum of the values of the cells in its neighborhood (possibly including the cell itself) at time t − 1.[56][57] If the state of the cell at time t depends on both its own state and the total of its neighbors at time t − 1 then the cellular automaton is properly called outer totalistic.[57] Conway's Game of Life is an example of an outer totalistic cellular automaton with cell values 0 and 1; outer totalistic cellular automata with the same Moore neighborhood structure as Life are sometimes called life-like cellular automata.[58][59]

Related automata[edit]

There are many possible generalizations of the cellular automaton concept.

A cellular automaton based on hexagonal cells instead of squares (rule 34/2)
An example of the Combinations cellular automata creating the Sierpiński triangle

One way is by using something other than a rectangular (cubic, etc.) grid. For example, if a plane is tiled with regular hexagons, those hexagons could be used as cells. In many cases the resulting cellular automata are equivalent to those with rectangular grids with specially designed neighborhoods and rules. Another variation would be to make the grid itself irregular, such as with Penrose tiles.[60]

Also, rules can be probabilistic rather than deterministic. Such cellular automata are called probabilistic cellular automata. A probabilistic rule gives, for each pattern at time t, the probabilities that the central cell will transition to each possible state at time t + 1. Sometimes a simpler rule is used; for example: "The rule is the Game of Life, but on each time step there is a 0.001% probability that each cell will transition to the opposite color."

The neighborhood or rules could change over time or space. For example, initially the new state of a cell could be determined by the horizontally adjacent cells, but for the next generation the vertical cells would be used.

In cellular automata, the new state of a cell is not affected by the new state of other cells. This could be changed so that, for instance, a 2 by 2 block of cells can be determined by itself and the cells adjacent to itself.

There are continuous automata. These are like totalistic cellular automata, but instead of the rule and states being discrete (e.g. a table, using states {0,1,2}), continuous functions are used, and the states become continuous (usually values in [0,1]). The state of a location is a finite number of real numbers. Certain cellular automata can yield diffusion in liquid patterns in this way.

Continuous spatial automata have a continuum of locations. The state of a location is a finite number of real numbers. Time is also continuous, and the state evolves according to differential equations. One important example is reaction–diffusion textures, differential equations proposed by Alan Turing to explain how chemical reactions could create the stripes on zebras and spots on leopards.[61] When these are approximated by cellular automata, they often yield similar patterns. MacLennan [1] considers continuous spatial automata as a model of computation.

There are known examples of continuous spatial automata, which exhibit propagating phenomena analogous to gliders in the Game of Life.[62]

Graph rewriting automata are extensions of cellular automata based on graph rewriting systems.[63]

Combinations automata function by checking if an odd/even indexed pair is equal to permutation X. If so, return X of the rulestring (for example: "120012101"). These CA work with brickwall neighborhoods. These CA types also act like Logic gate(s). For instance, the equivalent of the XOR gate in Combinations produces a Sierpiński triangle when the initial state is a single centered cell.

Elementary cellular automata[edit]

Main article: Elementary cellular automaton

The simplest nontrivial cellular automaton would be one-dimensional, with two possible states per cell, and a cell's neighbors defined as the adjacent cells on either side of it. A cell and its two neighbors form a neighborhood of 3 cells, so there are 23 = 8 possible patterns for a neighborhood. A rule consists of deciding, for each pattern, whether the cell will be a 1 or a 0 in the next generation. There are then 28 = 256 possible rules.[6]

An animation of the way the rules of a 1D cellular automaton determine the next generation.

These 256 cellular automata are generally referred to by their Wolfram code, a standard naming convention invented by Wolfram that gives each rule a number from 0 to 255. A number of papers have analyzed and compared these 256 cellular automata. The rule 30 and rule 110 cellular automata are particularly interesting. The images below show the history of each when the starting configuration consists of a 1 (at the top of each image) surrounded by 0s. Each row of pixels represents a generation in the history of the automaton, with t=0 being the top row. Each pixel is colored white for 0 and black for 1.

Rule 30


Rule 30 cellular automaton

current pattern111110101100011010001000
new state for center cell00011110

Rule 30 exhibits class 3 behavior, meaning even simple input patterns such as that shown lead to chaotic, seemingly random histories.

Rule 110


Rule 110 cellular automaton

current pattern111110101100011010001000
new state for center cell01101110

Rule 110, like the Game of Life, exhibits what Wolfram calls class 4 behavior, which is neither completely random nor completely repetitive. Localized structures appear and interact in various complicated-looking ways. In the course of the development of A New Kind of Science, as a research assistant to Wolfram in 1994, Matthew Cook proved that some of these structures were rich enough to support universality. This result is interesting because rule 110 is an extremely simple one-dimensional system, and difficult to engineer to perform specific behavior. This result therefore provides significant support for Wolfram's view that class 4 systems are inherently likely to be universal. Cook presented his proof at a Santa Fe Institute conference on Cellular Automata in 1998, but Wolfram blocked the proof from being included in the conference proceedings, as Wolfram did not want the proof announced before the publication of A New Kind of Science.[64] In 2004, Cook's proof was finally published in Wolfram's journal Complex Systems (Vol. 15, No. 1), over ten years after Cook came up with it. Rule 110 has been the basis for some of the smallest universal Turing machines.[65]

Rule space[edit]

An elementary cellular automaton rule is specified by 8 bits, and all elementary cellular automaton rules can be considered to sit on the vertices of the 8-dimensional unit hypercube. This unit hypercube is the cellular automaton rule space. For next-nearest-neighbor cellular automata, a rule is specified by 25 = 32 bits, and the cellular automaton rule space is a 32-dimensional unit hypercube. A distance between two rules can be defined by the number of steps required to move from one vertex, which represents the first rule, and another vertex, representing another rule, along the edge of the hypercube. This rule-to-rule distance is also called the Hamming distance.

Cellular automaton rule space allows us to ask the question concerning whether rules with similar dynamical behavior are "close" to each other. Graphically drawing a high dimensional hypercube on the 2-dimensional plane remains a difficult task, and one crude locator of a rule in the hypercube is the number of bit-1 in the 8-bit string for elementary rules (or 32-bit string for the next-nearest-neighbor rules). Drawing the rules in different Wolfram classes in these slices of the rule space show that class 1 rules tend to have lower number of bit-1s, thus located in one region of the space, whereas class 3 rules tend to have higher proportion (50%) of bit-1s.[45]

For larger cellular automaton rule space, it is shown that class 4 rules are located between the class 1 and class 3 rules.[66] This observation is the foundation for the phrase edge of chaos, and is reminiscent of the phase transition in thermodynamics.

Applications[edit]

Biology[edit]

Conus textile exhibits a cellular automaton pattern on its shell.[67]
Further information: Patterns in nature

Some biological processes occur—or can be simulated—by cellular automata.

Patterns of some seashells, like the ones in the genera Conus and Cymbiola, are generated by natural cellular automata. The pigment cells reside in a narrow band along the shell's lip. Each cell secretes pigments according to the activating and inhibiting activity of its neighbor pigment cells, obeying a natural version of a mathematical rule.[67] The cell band leaves the colored pattern on the shell as it grows slowly. For example, the widespread species Conus textile bears a pattern resembling Wolfram's rule 30 cellular automaton.[67]

Plants regulate their intake and loss of gases via a cellular automaton mechanism. Each stoma on the leaf acts as a cell.[68]

Moving wave patterns on the skin of cephalopods can be simulated with a two-state, two-dimensional cellular automata, each state corresponding to either an expanded or retracted chromatophore.[69]

Threshold automata have been invented to simulate neurons, and complex behaviors such as recognition and learning can be simulated.[70]

Fibroblasts bear similarities to cellular automata, as each fibroblast only interacts with its neighbors.[71]

Chemistry[edit]

The Belousov–Zhabotinsky reaction is a spatio-temporal chemical oscillator that can be simulated by means of a cellular automaton. In the 1950s A. M. Zhabotinsky (extending the work of B. P. Belousov) discovered that when a thin, homogenous layer of a mixture of malonic acid, acidified bromate, and a ceric salt were mixed together and left undisturbed, fascinating geometric patterns such as concentric circles and spirals propagate across the medium. In the "Computer Recreations" section of the August 1988 issue of Scientific American,[72] A. K. Dewdney discussed a cellular automaton[73] developed by Martin Gerhardt and Heike Schuster of the University of Bielefeld (Germany). This automaton produces wave patterns that resemble those in the Belousov-Zhabotinsky reaction.

Physics[edit]

Visualization of a lattice gas automaton. The shades of grey of the individual pixels are proportional to the gas particle density (between 0 and 4) at that pixel. The gas is surrounded by a shell of yellow cells that act as reflectors to create a closed space.

Probabilistic cellular automata are used in statistical and condensed matter physics to study phenomena like fluid dynamics and phase transitions. The Ising model is a prototypical example, in which each cell can be in either of two states called "up" and "down", making an idealized representation of a magnet. By adjusting the parameters of the model, the proportion of cells being in the same state can be varied, in ways that help explicate how ferromagnets become demagnetized when heated. Moreover, results from studying the demagnetization phase transition can be transferred to other phase transitions, like the evaporation of a liquid into a gas; this convenient cross-applicability is known as universality.[74][75] The phase transition in the two-dimensional Ising model and other systems in its universality class has been of particular interest, as it requires conformal field theory to understand in depth.[76] Other cellular automata that have been of significance in physics include lattice gas automata, which simulate fluid flows.

Computer science, coding, and communication[edit]

Cellular automaton processors are physical implementations of CA concepts, which can process information computationally. Processing elements are arranged in a regular grid of identical cells. The grid is usually a square tiling, or tessellation, of two or three dimensions; other tilings are possible, but not yet used. Cell states are determined only by interactions with adjacent neighbor cells. No means exists to communicate directly with cells farther away.[77] One such cellular automaton processor array configuration is the systolic array. Cell interaction can be via electric charge, magnetism, vibration (phonons at quantum scales), or any other physically useful means. This can be done in several ways so that no wires are needed between any elements. This is very unlike processors used in most computers today (von Neumann designs) which are divided into sections with elements that can communicate with distant elements over wires.

Rule 30 was originally suggested as a possible block cipher for use in cryptography. Two-dimensional cellular automata can be used for constructing a pseudorandom number generator.[78]

Cellular automata have been proposed for public-key cryptography. The one-way function is the evolution of a finite CA whose inverse is believed to be hard to find. Given the rule, anyone can easily calculate future states, but it appears to be very difficult to calculate previous states.

CA have been applied to design error correction codes in a paper by D. Roy Chowdhury, S. Basu, I. Sen Gupta, and P. Pal Chaudhuri. The paper defines a new scheme of building single bit error correction and double bit error detection (SEC-DED) codes using CA, and also reports a fast hardware decoder for the code.[79]

Other problems that can be solved with cellular automata include:

  • Firing squad synchronization problem
  • Majority problem

Generative art and music[edit]

Cellular automata have been used in generative music[80] and evolutionary music composition[81] and procedural terrain generation in video games.[82]

Specific rules[edit]

Specific types of cellular automata include:

  • Brian's Brain
  • Codd's cellular automaton
  • CoDi
  • Langton's ant
  • Langton's loops
  • Nobili cellular automata
  • Rule 90
  • Rule 184
  • von Neumann cellular automata
  • Wireworld

See also[edit]

  • Agent-based model
  • Automata theory – Study of abstract machines and automata
  • Bidirectional traffic – Two streams of traffic that flow in opposite directions
  • Cyclic cellular automaton
  • Excitable medium
  • Golly
  • Movable cellular automaton – A method in computational solid mechanics based on the discrete concept
  • Quantum cellular automaton – An abstract model of quantum computation
  • Spatial decision support system – Computerised aid to land use decisions
  • Turmite – A Turing machine which has an orientation as well as a current state and a "tape" that consists of an infinite two-dimensional grid of cells
  • Category:Cellular automata in popular culture
  • Discrete calculus

Notes[edit]

  1. ^ Daniel Dennett (1995), Darwin's Dangerous Idea, Penguin Books, London, ISBN 978-0-14-016734-4, ISBN 0-14-016734-X
  2. ^ a b Wolfram, Stephen (1983). "Statistical Mechanics of Cellular Automata". Reviews of Modern Physics. 55 (3): 601–644. Bibcode:1983RvMP...55..601W. doi:10.1103/RevModPhys.55.601.
  3. ^ Toffoli, Tommaso; Margolus, Norman (1987). Cellular Automata Machines: A New Environment for Modeling. MIT Press. p. 27. ISBN 9780262200608.
  4. ^ Schiff, Joel L. (2011). Cellular Automata: A Discrete View of the World. Wiley & Sons, Inc. p. 40. ISBN 9781118030639.
  5. ^ a b c d Kier, Seybold, Cheng 2005, p. 15
  6. ^ a b Bialynicki-Birula, Bialynicka-Birula 2004, p. 9
  7. ^ Schiff 2011, p. 41
  8. ^ Pickover, Clifford A. (2009). The Math Book: From Pythagoras to the 57th Dimension, 250 Milestones in the History of Mathematics. Sterling Publishing Company, Inc. p. 406. ISBN 978-1402757969.
  9. ^ a b Schiff 2011, p. 1
  10. ^ John von Neumann, "The general and logical theory of automata," in L.A. Jeffress, ed., Cerebral Mechanisms in Behavior – The Hixon Symposium, John Wiley & Sons, New York, 1951, pp. 1–31.
  11. ^ Kemeny, John G. (1955). "Man viewed as a machine". Sci. Am. 192 (4): 58–67. Bibcode:1955SciAm.192d..58K. doi:10.1038/scientificamerican0455-58.; Sci. Am. 1955; 192:6 (errata).
  12. ^ Schiff 2011, p. 3
  13. ^ Ilachinski 2001, p. xxix
  14. ^ Bialynicki-Birula, Bialynicka-Birula 2004, p. 8
  15. ^ a b Wolfram 2002, p. 876
  16. ^ von Neumann, John; Burks, Arthur W. (1966). Theory of Self-Reproducing Automata. University of Illinois Press.
  17. ^ a b Wiener, N.; Rosenblueth, A. (1946). "The mathematical formulation of the problem of conduction of impulses in a network of connected excitable elements, specifically in cardiac muscle". Arch. Inst. Cardiol. México. 16 (3): 205–65. PMID 20245817.
  18. ^ Letichevskii, A. A.; Reshodko, L. V. (1974). "N. Wiener's theory of the activity of excitable media". Cybernetics. 8 (5): 856–864. doi:10.1007/bf01068458. S2CID 121306408.
  19. ^ Davidenko, J. M.; Pertsov, A. V.; Salomonsz, R.; Baxter, W.; Jalife, J. (1992). "Stationary and drifting spiral waves of excitation in isolated cardiac muscle". Nature. 355 (6358): 349–351. Bibcode:1992Natur.355..349D. doi:10.1038/355349a0. PMID 1731248. S2CID 4348759.
  20. ^ Hedlund, G. A. (1969). "Endomorphisms and automorphisms of the shift dynamical system". Math. Systems Theory. 3 (4): 320–3751. doi:10.1007/BF01691062. S2CID 21803927.
  21. ^ Schiff 2011, p. 182
  22. ^ Smith, Alvy Ray. "Cellular Automata Complexity Trade-Offs" (PDF).
  23. ^ Smith, Alvy Ray. "Simple Computation-Universal Cellular Spaces" (PDF).
  24. ^ Smith, Alvy Ray. "Simple Nontrivial Self-Reproducing Machines" (PDF).
  25. ^ Smith, Alvy Ray. "Introduction to and Survey of Cellular Automata or Polyautomata Theory" (PDF).
  26. ^ Gardner, Martin (1970). "Mathematical Games: The fantastic combinations of John Conway's new solitaire game "life"". Scientific American. 223 (4): 120–123. doi:10.1038/scientificamerican1070-120.
  27. ^ Paul Chapman. Life universal computer. http://www.igblan.free-online.co.uk/igblan/ca/ November 2002
  28. ^ Wainwright 2010, p. 16
  29. ^ a b c d e Wolfram 2002, p. 880
  30. ^ Wolfram 2002, p. 881
  31. ^ Mitchell, Melanie (4 October 2002). "Is the Universe a Universal Computer?". Science. 298 (5591): 65–68. doi:10.1126/science.1075073. S2CID 122484855.
  32. ^ Wolfram 2002, pp. 1–7
  33. ^ Johnson, George (9 June 2002). "'A New Kind of Science': You Know That Space-Time Thing? Never Mind". The New York Times. Retrieved 22 January 2013.
  34. ^ "The Science of Everything". The Economist. 30 May 2002. Retrieved 22 January 2013.
  35. ^ Wolfram 2002, pp. 433–546
  36. ^ Wolfram 2002, pp. 51–114
  37. ^ Wolfram 2002, pp. 115–168
  38. ^ a b c Ilachinsky 2001, p. 12
  39. ^ Ilachinsky 2001, p. 13
  40. ^ Wolfram 2002, p. 231
  41. ^ Zenil, Hector (2010). "Compression-based investigation of the dynamical properties of cellular automata and other systems" (PDF). Complex Systems. 19 (1): 1–28. doi:10.25088/ComplexSystems.19.1.1. S2CID 15364755.
  42. ^ G. Cattaneo; E. Formenti; L. Margara (1998). "Topological chaos and CA". In M. Delorme; J. Mazoyer (eds.). Cellular automata: a parallel model. Springer. p. 239. ISBN 978-0-7923-5493-2.
  43. ^ Burton H. Voorhees (1996). Computational analysis of one-dimensional cellular automata. World Scientific. p. 8. ISBN 978-981-02-2221-5.
  44. ^ Max Garzon (1995). Models of massive parallelism: analysis of cellular automata and neural networks. Springer. p. 149. ISBN 978-3-540-56149-1.
  45. ^ a b Li, Wentian; Packard, Norman (1990). "The structure of the elementary cellular automata rule space" (PDF). Complex Systems. 4: 281–297. Retrieved 25 January 2013.
  46. ^ Nicolis (1974). "Dissipative Structures, Catastrophes, and Pattern Formation: A Bifurcation Analysis" (PDF). PNAS. 71 (7): 2748–2751. Bibcode:1974PNAS...71.2748N. doi:10.1073/pnas.71.7.2748. PMC 388547. PMID 16592170. Retrieved 25 March 2017.
  47. ^ a b Kari, Jarrko 1991, p. 379
  48. ^ Richardson, D. (1972). "Tessellations with local transformations". J. Computer System Sci. 6 (5): 373–388. doi:10.1016/S0022-0000(72)80009-6.
  49. ^ Margenstern, Maurice (2007). Cellular Automata in Hyperbolic Spaces – Tome I, Volume 1. Archives contemporaines. p. 134. ISBN 978-2-84703-033-4.
  50. ^ Schiff 2011, p. 103
  51. ^ Amoroso, Serafino; Patt, Yale N. (1972). "Decision Procedures for Surjectivity and Injectivity of Parallel Maps for Tessellation Structures". J. Comput. Syst. Sci. 6 (5): 448–464. doi:10.1016/s0022-0000(72)80013-8.
  52. ^ Sutner, Klaus (1991). "De Bruijn Graphs and Linear Cellular Automata" (PDF). Complex Systems. 5: 19–30.
  53. ^ Kari, Jarkko (1990). "Reversibility of 2D cellular automata is undecidable". Physica D. 45 (1–3): 379–385. Bibcode:1990PhyD...45..379K. doi:10.1016/0167-2789(90)90195-U.
  54. ^ Kari, Jarkko (1999). "On the circuit depth of structurally reversible cellular automata". Fundamenta Informaticae. 38: 93–107. doi:10.3233/FI-1999-381208.
  55. ^ Durand-Lose, Jérôme (2001). "Representing reversible cellular automata with reversible block cellular automata". Discrete Mathematics and Theoretical Computer Science. AA: 145–154. Archived from the original on 15 May 2011.
  56. ^ Wolfram 2002, p. 60
  57. ^ a b Ilachinski, Andrew (2001). Cellular automata: a discrete universe. World Scientific. pp. 44–45. ISBN 978-981-238-183-5.
  58. ^ The phrase "life-like cellular automaton" dates back at least to Barral, Chaté & Manneville (1992), who used it in a broader sense to refer to outer totalistic automata, not necessarily of two dimensions. The more specific meaning given here was used e.g. in several chapters of Adamatzky (2010). See: Barral, Bernard; Chaté, Hugues; Manneville, Paul (1992). "Collective behaviors in a family of high-dimensional cellular automata". Physics Letters A. 163 (4): 279–285. Bibcode:1992PhLA..163..279B. doi:10.1016/0375-9601(92)91013-H.
  59. ^ Eppstein 2010, pp. 72–73
  60. ^ Jacob Aron. "First gliders navigate ever-changing Penrose universe". New Scientist.
  61. ^ Murray, J. "Mathematical Biology II". Springer. Cite journal requires |journal= (help)
  62. ^ Pivato, M: "RealLife: The continuum limit of Larger than Life cellular automata", Theoretical Computer Science, 372 (1), March 2007, pp. 46–68
  63. ^ Tomita, Kohji; Kurokawa, Haruhisa; Murata, Satoshi (2009). "Graph-Rewriting Automata as a Natural Extension of Cellular Automata". Adaptive Networks. Understanding Complex Systems. pp. 291–309. doi:10.1007/978-3-642-01284-6_14. ISBN 978-3-642-01283-9.
  64. ^ Giles, Jim (2002). "What Kind of Science is This?". Nature. 417 (6886): 216–218. Bibcode:2002Natur.417..216G. doi:10.1038/417216a. PMID 12015565. S2CID 10636328.
  65. ^ Weinberg, Steven (24 October 2002). "Is the Universe a Computer?". The New York Review of Books. Retrieved 12 October 2012.
  66. ^ Wentian Li; Norman Packard; Chris G Langton (1990). "Transition phenomena in cellular automata rule space". 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.
  67. ^ a b c Coombs, Stephen (15 February 2009), The Geometry and Pigmentation of Seashells (PDF), pp. 3–4, archived from the original (PDF) on 7 January 2013, retrieved 2 September 2012
  68. ^ Peak, West; Messinger, Mott (2004). "Evidence for complex, collective dynamics and emergent, distributed computation in plants". Proceedings of the National Academy of Sciences. 101 (4): 918–922. Bibcode:2004PNAS..101..918P. doi:10.1073/pnas.0307811100. PMC 327117. PMID 14732685.
  69. ^ "Archived copy" (PDF). Archived from the original (PDF) on 4 March 2016. Retrieved 14 September 2008.CS1 maint: archived copy as title (link)
  70. ^ Ilachinsky 2001, p. 275
  71. ^ Yves Bouligand (1986). Disordered Systems and Biological Organization. pp. 374–375.
  72. ^ A. K. Dewdney, The hodgepodge machine makes waves, Scientific American, p. 104, August 1988.
  73. ^ Gerhardt, M.; Schuster, H. (1989). "A cellular automaton describing the formation of spatially ordered structures in chemical systems". Physica D. 36 (3): 209–221. Bibcode:1989PhyD...36..209G. doi:10.1016/0167-2789(89)90081-x.
  74. ^ Sethna, James P. (2008). Statistical Mechanics: Entropy, Order Parameters, and Complexity. Oxford University Press. ISBN 978-0-198-56677-9. OCLC 845714772.
  75. ^ Kardar, Mehran (2007). Statistical Physics of Fields. Cambridge University Press. ISBN 978-0-521-87341-3. OCLC 920137477.
  76. ^ Cappelli, Andrea; Zuber, Jean-Bernard (2010). "A-D-E Classification of Conformal Field Theories". Scholarpedia. 5 (4): 10314. arXiv:0911.3242. Bibcode:2010SchpJ...510314C. doi:10.4249/scholarpedia.10314. S2CID 18207779.
  77. ^ Muhtaroglu, Ali (August 1996). "4.1 Cellular Automaton Processor (CAP)". Cellular Automaton Processor Based Systems for Genetic Sequence Comparison/Database Searching. Cornell University. pp. 62–74.
  78. ^ Tomassini, M.; Sipper, M.; Perrenoud, M. (2000). "On the generation of high-quality random numbers by two-dimensional cellular automata". IEEE Transactions on Computers. 49 (10): 1146–1151. doi:10.1109/12.888056.
  79. ^ Chowdhury, D. Roy; Basu, S.; Gupta, I. Sen; Chaudhuri, P. Pal (June 1994). "Design of CAECC - cellular automata based error correcting code". IEEE Transactions on Computers. 43 (6): 759–764. doi:10.1109/12.286310.
  80. ^ Burraston, Dave, and Ernest Edmonds. "Cellular automata in generative electronic music and sonic art: a historical and technical review." Digital Creativity 16.3 (2005): 165-185.
  81. ^ Miranda, Eduardo Reck. "Evolving cellular automata music: From sound synthesis to composition." Proceedings of 2001 Workshop on Artificial Life Models for Musical Applications. 2001.
  82. ^ Miranda, Eduardo Reck. "Evolving cellular automata music: From sound synthesis to composition." Proceedings of 2001 Workshop on Artificial Life Models for Musical Applications. 2001.

References[edit]

  • Adamatzky, Andrew, ed. (2010). Game of Life Cellular Automata. Springer. ISBN 978-1-84996-216-2.
  • Bialynicki-Birula, Iwo; Bialynicka-Birula, Iwona (2004). Modeling Reality: How Computers Mirror Life. Oxford University Press. ISBN 978-0198531005.
  • Chopard, Bastien; Droz, Michel (2005). Cellular Automata Modeling of Physical Systems. Cambridge University Press. ISBN 978-0-521-46168-9.
  • Gutowitz, Howard, ed. (1991). Cellular Automata: Theory and Experiment. MIT Press. ISBN 9780262570862.
  • Ilachinski, Andrew (2001). Cellular Automata: A Discrete Universe. World Scientific. ISBN 9789812381835.
  • Kier, Lemont B.; Seybold, Paul G.; Cheng, Chao-Kun (2005). Modeling Chemical Systems using Cellular Automata. Springer. ISBN 9781402036576.
  • Kroc, Jiří; Jiménez-Morales, Francisco; Guisado, José Luis; Lemos, María Carmen; Tkáč, Jakub (December 2019). "Building Efficient Computational Cellular Automata Models of Complex Systems: Background, Applications, Results, Software, and Pathologies". Advances in Complex Systems. 22 (5): 1950013 (38 pages). doi:10.1142/S0219525919500139.
  • Wolfram, Stephen (2002). A New Kind of Science. Wolfram Media. ISBN 978-1579550080.
  • Cellular automaton FAQ from the newsgroup comp.theory.cell-automata
  • "Neighbourhood Survey" (includes discussion on triangular grids, and larger neighborhood CAs)
  • von Neumann, John, 1966, The Theory of Self-reproducing Automata, A. Burks, ed., Univ. of Illinois Press, Urbana, IL.
  • Cosma Shalizi's Cellular Automata Notebook contains an extensive list of academic and professional reference material.
  • Wolfram's papers on CAs
  • A.M. Turing. 1952. The Chemical Basis of Morphogenesis. Phil. Trans. Royal Society, vol. B237, pp. 37–72. (proposes reaction-diffusion, a type of continuous automaton).
  • Evolving Cellular Automata with Genetic Algorithms: A Review of Recent Work, Melanie Mitchell, James P. Crutchfeld, Rajarshi Das (In Proceedings of the First International Conference on Evolutionary Computation and Its Applications (EvCA'96). Moscow, Russia: Russian Academy of Sciences, 1996.)
  • The Evolutionary Design of Collective Computation in Cellular Automata, James P. Crutchfeld, Melanie Mitchell, Rajarshi Das (In J. P. Crutch¯eld and P. K. Schuster (editors), Evolutionary Dynamics|Exploring the Interplay of Selection, Neutrality, Accident, and Function. New York: Oxford University Press, 2002.)
  • The Evolution of Emergent Computation, James P. Crutchfield and Melanie Mitchell (SFI Technical Report 94-03-012)
  • Ganguly, Sikdar, Deutsch and Chaudhuri "A Survey on Cellular Automata"

External links[edit]

  • Berto, Francesco; Tagliabue, Jacopo. "Cellular Automata". In Zalta, Edward N. (ed.). Stanford Encyclopedia of Philosophy.
  • Mirek's Cellebration – Home to free MCell and MJCell cellular automata explorer software and rule libraries. The software supports a large number of 1D and 2D rules. The site provides both an extensive rules lexicon and many image galleries loaded with examples of rules. MCell is a Windows application, while MJCell is a Java applet. Source code is available.
  • Modern Cellular Automata – Easy to use interactive exhibits of live color 2D cellular automata, powered by Java applet. Included are exhibits of traditional, reversible, hexagonal, multiple step, fractal generating, and pattern generating rules. Thousands of rules are provided for viewing. Free software is available.
  • Self-replication loops in Cellular Space – Java applet powered exhibits of self replication loops.
  • A collection of over 10 different cellular automata applets (in Monash University's Virtual Lab)
  • Golly supports von Neumann, Nobili, GOL, and a great many other systems of cellular automata. Developed by Tomas Rokicki and Andrew Trevorrow. This is the only simulator currently available that can demonstrate von Neumann type self-replication.
  • Fourier Life - A collection of rules that demonstrate self-replicating patterns which spontaneously emerge from a field of random cells. Most of the rules were found using an algorithm that uses a Fourier transform to detect self-replication.
  • Wolfram Atlas – An atlas of various types of one-dimensional cellular automata.
  • Conway Life
  • First replicating creature spawned in life simulator
  • The Mathematics of the Models of Reference, featuring a general tutorial on CA, interactive applet, free code and resources on CA as model of fundamental physics
  • Fourmilab Cellular Automata Laboratory
  • Busy Boxes, a 3-D, reversible, SALT-architecture CA
  • Cellular Automata Repository (CA researchers, historic links, free software, books and beyond)
  • Cellular Automata in 256 Rules (A single sheet interactive visualization of 256 elementary rules )
  • Petri -- a Go cellular automata framework