Клеточные автоматы: дискретная модель вычислений.

Введение

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

Discrete model studied in computer science

A cellular automaton (pl. cellular automata, abbrev. CA) is a discrete model of computation studied in automata theory. Cellular automata are also called cellular spaces, tessellation automata, homogeneous structures, cellular structures, tessellation structures, and iterative arrays. Cellular automata have found application in various areas, including physics, theoretical biology and microstructure modeling. A cellular automaton consists of a regular grid of cells, each in one of a finite number of states, such as on and off (in contrast to a coupled map lattice). The grid can be in any finite number of dimensions. For each cell, a set of cells called its neighborhood is defined relative to the specified cell. An initial state (time t = 0) is selected by assigning a state for each cell. A new generation is created (advancing t by 1), according to some fixed rule (generally, a mathematical function) that determines the new state of each cell in terms of the current state of the cell and the states of the cells in its neighborhood. Typically, the rule for updating the state of cells is the same for each cell and does not change over time, and is applied to the whole grid simultaneously, though exceptions are known, such as the stochastic cellular automaton and asynchronous cellular automaton. The concept was originally discovered in the 1940s by Stanislaw Ulam and John von Neumann while they were contemporaries at Los Alamos National Laboratory. While studied by some throughout the 1950s and 1960s, it was not until the 1970s and Conway's Game of Life, a two dimensional cellular automaton, that interest in the subject expanded beyond academia. In the 1980s, Stephen Wolfram engaged in a systematic study of one dimensional cellular automata, or what he calls elementary cellular automata; his research assistant Matthew Cook showed that one of these rules is Turing complete. The primary classifications of cellular automata, as outlined by Wolfram, are numbered one to four. They are, in order, automata in which patterns generally stabilize into homogeneity, automata in which patterns evolve into mostly stable or oscillating structures, automata in which patterns evolve in a seemingly chaotic fashion, and automata in which patterns become extremely complex and may last for a long time, with stable local structures. This last class is thought to be computationally universal, or capable of simulating a Turing machine. Special types of cellular automata are reversible, where only a single configuration leads directly to a subsequent one, and totalistic, in which the future value of individual cells only depends on the total value of a group of neighboring cells. Cellular automata can simulate a variety of real world systems, including biological and chemical ones.

Обзор

Один из способов моделирования двухмерного клеточного автомата – бесконечный лист графической бумаги вместе с набором правил, которым должны следовать клетки. Каждый квадрат называется «клеткой», и каждая клетка имеет два возможных состояния: чёрный и белый. Окрестность клетки – это соседние, обычно смежные, клетки. Два наиболее распространённых типа окрестностей – окрестность фон Неймана и окрестность Мура. Первая, названная в честь основателя теории клеточных автоматов, состоит из четырёх ортогонально смежных клеток. Таким образом, в двухмерной системе с окрестностью Мура общее количество возможных автоматов будет 229, или 1,34 x 108. Обычно предполагается, что каждая клетка во Вселенной начинается в одном и том же состоянии, за исключением конечного числа клеток в других состояниях; назначение значений состояния называется конфигурацией. В более общем смысле, иногда предполагается, что Вселенная начинается с периодического рисунка, и только конечное число клеток нарушает этот рисунок. Последнее предположение распространено в одномерных клеточных автоматах. Клеточные автоматы часто моделируются на конечной сетке, а не на бесконечной. В двух измерениях Вселенная будет представлять собой прямоугольник, а не бесконечную плоскость. Очевидная проблема с конечными сетками – как обрабатывать клетки на краях. Способ обработки клеток на краях повлияет на значения всех клеток в сетке. Один из возможных методов – позволить значениям в этих клетках оставаться постоянными. Другой метод – определить окрестности по-разному для этих клеток. Можно сказать, что у них меньше соседей, но тогда потребуется определить новые правила для клеток, расположенных на краях. Эти клетки обычно обрабатываются с использованием периодических граничных условий, что приводит к тороидальной организации: когда клетка выходит за верхний край, она появляется в соответствующей позиции внизу, а когда выходит за левый край, она появляется справа. (Это по сути имитирует бесконечную периодическую плитку, и в области дифференциальных уравнений в частных производных иногда называется периодическими граничными условиями.) Это можно представить как склеивание левого и правого краёв прямоугольника для образования трубки, а затем склеивание верхнего и нижнего краёв трубки для образования тора (формы пончика). Вселенные других измерений обрабатываются аналогично. Это решает проблемы границ с окрестностями, но ещё одно преимущество заключается в том, что это легко программируется с использованием функций модульной арифметики. Например, в одномерном клеточном автомате, как в примерах ниже, окрестность клетки xit – это {xi-1t-1, xit-1, xi+1t-1}, где t – шаг времени (вертикальный), а i – индекс (горизонтальный) в одном поколении.

One way to simulate a two dimensional cellular automaton is with an infinite sheet of graph paper along with a set of rules for the cells to follow. Each square is called a "cell" and each cell has two possible states, black and white. The neighborhood of a cell is the nearby, usually adjacent, cells. The two most common types of neighborhoods are the von Neumann neighborhood and the Moore neighborhood. The former, named after the founding cellular automaton theorist, consists of the four orthogonally adjacent cells. Thus, in the two dimensional system with a Moore neighborhood, the total number of automata possible would be 229, or 1.34. It is usually assumed that every cell in the universe starts in the same state, except for a finite number of cells in other states; the assignment of state values is called a configuration. More generally, it is sometimes assumed that the universe starts out covered with a periodic pattern, and only a finite number of cells violate that pattern. The latter assumption is common in one dimensional cellular automata. Cellular automata are often simulated on a finite grid rather than an infinite one. In two dimensions, the universe would be a rectangle instead of an infinite plane. The obvious problem with finite grids is how to handle the cells on the edges. How they are handled will affect the values of all the cells in the grid. One possible method is to allow the values in those cells to remain constant. Another method is to define neighborhoods differently for these cells. One could say that they have fewer neighbors, but then one would also have to define new rules for the cells located on the edges. These cells are usually handled with periodic boundary conditions resulting in a toroidal arrangement: when one goes off the top, one comes in at the corresponding position on the bottom, and when one goes off the left, one comes in on the right. (This essentially simulates an infinite periodic tiling, and in the field of partial differential equations is sometimes referred to as periodic boundary conditions.) This can be visualized as taping the left and right edges of the rectangle to form a tube, then taping the top and bottom edges of the tube to form a torus (doughnut shape). Universes of other dimensions are handled similarly. This solves boundary problems with neighborhoods, but another advantage is that it is easily programmable using modular arithmetic functions. For example, in a 1 dimensional cellular automaton like the examples below, the neighborhood of a cell xit is {xi−1t−1, xit−1, xi+1t−1}, where t is the time step (vertical), and i is the index (horizontal) in one generation.

История

Станислав Улам, работая в Национальной лаборатории Лос-Аламоса в 1940-х годах, изучал рост кристаллов, используя в качестве модели простую решётчатую сеть. В то же время Джон фон Нейман, коллега Улама в Лос-Аламосе, работал над проблемой самовоспроизводящихся систем. Первоначальный проект фон Неймана основывался на идее робота, создающего другого робота. Эта конструкция известна как кинематическая модель. В процессе разработки этого проекта фон Нейман осознал значительную сложность создания самовоспроизводящегося робота и высокую стоимость обеспечения робота "запасом деталей", из которых он мог бы построить свою копию. Фон Нейман опубликовал статью под названием "Общая и логическая теория автоматов" для Симпозиума Хиксона в 1948 году. Нильс Алл Барричелли выполнил многие из первых исследований этих моделей искусственной жизни. Улам и фон Нейман разработали метод расчета движения жидкости в конце 1950-х годов. Основная концепция метода заключалась в рассмотрении жидкости как группы дискретных элементов и вычислении движения каждого из них на основе поведения его соседей. Так возникла первая система клеточных автоматов. Как и решётчатая сеть Улама, клеточные автоматы фон Неймана двумерны, а его саморепликатор реализован алгоритмически. Результатом стал универсальный копировальщик и конструктор, работающий в клеточном автомате с небольшим радиусом действия (соседями считаются только непосредственно прилегающие клетки; для клеточных автоматов фон Неймана – только ортогональные клетки) и с 29 состояниями на клетку. Фон Нейман доказал существование конфигурации, способной создавать бесконечное количество своих копий в заданной клеточной вселенной, спроектировав конфигурацию из 200 000 клеток. Также в 1940-х годах Норберт Винер и Артуро Розенблют разработали модель возбудимых сред, обладающих некоторыми характеристиками клеточного автомата. Их основной целью было математическое описание проведения импульсов в сердечных системах. Однако их модель не является клеточным автоматом, поскольку среда, в которой распространяются сигналы, непрерывна, а фронты волн – кривые. Истинная модель клеточного автомата возбудимых сред была разработана и изучена Дж. М. Гринбергом и С. П. Гастингсом в 1978 году; см. клеточный автомат Гринберга-Гастингса. Оригинальная работа Винера и Розенблюта содержит множество ценных идей и продолжает цитироваться в современных исследовательских публикациях по сердечной аритмии и возбудимым системам. В 1960-х годах клеточные автоматы изучались как особый тип динамической системы, и впервые была установлена связь с математической областью символической динамики. В 1969 году Густав А. Хедлунд собрал множество результатов, основанных на этой точке зрения, в статье, которая до сих пор считается основополагающей для математического изучения клеточных автоматов. Наиболее фундаментальным результатом является характеризация в теореме Кертиса — Хедлунда — Линдона множества глобальных правил клеточных автоматов как множества непрерывных эндоморфизмов пространств сдвига. В 1969 году немецкий пионер в области вычислительной техники Конрад Цузе опубликовал свою книгу "Вычислительное пространство", в которой предположил, что физические законы Вселенной дискретны по своей природе и что вся Вселенная является результатом детерминированного вычисления на одном клеточном автомате; "Теория Цузе" стала основой области исследований, называемой цифровой физикой. Также в 1969 году ученый-компьютерщик Элви Рэй Смит завершил докторскую диссертацию в Стэнфордском университете на тему "Теория клеточных автоматов", представляющую собой первое математическое рассмотрение CA как общего класса компьютеров. Из этой диссертации вышло множество работ: он показал эквивалентность соседств различных форм, способы сведения соседства Мура к соседству фон Неймана или сведения любого соседства к соседству фон Неймана. Он доказал, что двумерные CA являются универсальными вычислительными устройствами, представил одномерные CA и показал, что они также являются универсальными вычислительными устройствами, даже с простыми соседствами. Он показал, как включить сложное доказательство фон Неймана универсальности конструкции (и, следовательно, самовоспроизводящихся машин) в следствие универсальности вычислений в одномерном CA. Написанная в качестве введения к немецкому изданию книги фон Неймана о CA, он подготовил обзор области, содержащий десятки ссылок на работы многих авторов из разных стран за десятилетие исследований, часто упускаемые из виду современными исследователями CA. В 1970-х годах двумерный клеточный автомат с двумя состояниями, названный "Игра Жизни", получил широкую известность, особенно в раннем вычислительном сообществе. Изобретенная Джоном Конвеем и популяризированная Мартином Гарднером в статье в журнале Scientific American, её правила следующие:
Любая живая клетка с менее чем двумя живыми соседями умирает, как будто от недостатка популяции. Любая живая клетка с двумя или тремя живыми соседями продолжает жить в следующем поколении. Любая живая клетка с более чем тремя живыми соседями умирает, как будто от перенаселения. Любая мертвая клетка с ровно тремя живыми соседями становится живой клеткой, как будто от размножения. Несмотря на свою простоту, система демонстрирует впечатнительное разнообразие поведения, колеблющееся между кажущейся случайностью и порядком. Одной из наиболее заметных особенностей "Игры Жизни" является частое появление планеров – конфигураций клеток, которые фактически перемещают себя по сетке. Можно организовать автомат таким образом, чтобы планеры взаимодействовали и выполняли вычисления, и после значительных усилий было показано, что "Игра Жизни" может эмулировать универсальную машину Тьюринга. Она рассматривалась как в основном развлекательная тема, и мало работы было выполнено за пределами изучения особенностей "Игры Жизни" и нескольких связанных с ней правил в начале 1970-х годов. Стивен Вольфрам независимо начал работать над клеточными автоматами в середине 1981 года, размышляя о том, как сложные закономерности, по-видимому, формируются в природе в нарушение Второго закона термодинамики. Неожиданная сложность поведения этих простых правил заставила Вольфрама предположить, что сложность в природе может быть обусловлена аналогичными механизмами, и предположил, что правило 110 может быть универсальным, что позже было доказано помощником Вольфрама Мэтью Куком в 1990-х годах.

Stanislaw Ulam, while working at the Los Alamos National Laboratory in the 1940s, studied the growth of crystals, using a simple lattice network as his model. At the same time, John von Neumann, Ulam's colleague at Los Alamos, was working on the problem of self replicating systems. Von Neumann's initial design was founded upon the notion of one robot building another robot. This design is known as the kinematic model. As he developed this design, von Neumann came to realize the great difficulty of building a self replicating robot, and of the great cost in providing the robot with a "sea of parts" from which to build its replicant. Neumann wrote a paper entitled "The general and logical theory of automata" for the Hixon Symposium in 1948. Nils Aall Barricelli performed many of the earliest explorations of these models of artificial life. Ulam and von Neumann created a method for calculating liquid motion in the late 1950s. The driving concept of the method was to consider a liquid as a group of discrete units and calculate the motion of each based on its neighbors' behaviors. Thus was born the first system of cellular automata. Like Ulam's lattice network, von Neumann's cellular automata are two dimensional, with his self replicator implemented algorithmically. The result was a universal copier and constructor working within a cellular automaton with a small neighborhood (only those cells that touch are neighbors; for von Neumann's cellular automata, only orthogonal cells), and with 29 states per cell. Von Neumann gave an existence proof that a particular pattern would make endless copies of itself within the given cellular universe by designing a 200,000 cell configuration that could do so. Also in the 1940s, Norbert Wiener and Arturo Rosenblueth developed a model of excitable media with some of the characteristics of a cellular automaton. Their specific motivation was the mathematical description of impulse conduction in cardiac systems. However their model is not a cellular automaton because the medium in which signals propagate is continuous, and wave fronts are curves. A true cellular automaton model of excitable media was developed and studied by J. M. Greenberg and S. P. Hastings in 1978; see Greenberg Hastings cellular automaton. The original work of Wiener and Rosenblueth contains many insights and continues to be cited in modern research publications on cardiac arrhythmia and excitable systems. In the 1960s, cellular automata were studied as a particular type of dynamical system and the connection with the mathematical field of symbolic dynamics was established for the first time. In 1969, Gustav A. Hedlund compiled many results following this point of view in what is still considered as a seminal paper for the mathematical study of cellular automata. The most fundamental result is the characterization in the Curtis–Hedlund–Lyndon theorem of the set of global rules of cellular automata as the set of continuous endomorphisms of shift spaces. In 1969, German computer pioneer Konrad Zuse published his book Calculating Space, proposing that the physical laws of the universe are discrete by nature, and that the entire universe is the output of a deterministic computation on a single cellular automaton; "Zuse's Theory" became the foundation of the field of study called digital physics. Also in 1969 computer scientist Alvy Ray Smith completed a Stanford PhD dissertation on Cellular Automata Theory, the first mathematical treatment of CA as a general class of computers. Many papers came from this dissertation: He showed the equivalence of neighborhoods of various shapes, how to reduce a Moore to a von Neumann neighborhood or how to reduce any neighborhood to a von Neumann neighborhood. He proved that two dimensional CA are computation universal, introduced 1 dimensional CA, and showed that they too are computation universal, even with simple neighborhoods. He showed how to subsume the complex von Neumann proof of construction universality (and hence self reproducing machines) into a consequence of computation universality in a 1 dimensional CA. Intended as the introduction to the German edition of von Neumann's book on CA, he wrote a survey of the field with dozens of references to papers, by many authors in many countries over a decade or so of work, often overlooked by modern CA researchers. In the 1970s a two state, two dimensional cellular automaton named Game of Life became widely known, particularly among the early computing community. Invented by John Conway and popularized by Martin Gardner in a Scientific American article, its rules are as follows:
Any live cell with fewer than two live neighbours dies, as if caused by underpopulation. Any live cell with two or three live neighbours lives on to the next generation. Any live cell with more than three live neighbours dies, as if by overpopulation. Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction. 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. 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. 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. The unexpected complexity of the behavior of these simple rules led Wolfram to suspect that complexity in nature may be due to similar mechanisms. and suggested that rule 110 may be universal—a fact proved later by Wolfram's research assistant Matthew Cook in the 1990s.

Классификация

В своей книге «Новая наука» и ряде работ, датируемых серединой 1980-х годов, Вольфрам определил четыре класса, на которые можно разделить клеточные автоматы и несколько других простых вычислительных моделей в зависимости от их поведения. В то время как более ранние исследования клеточных автоматов, как правило, стремились выявить типы паттернов для конкретных правил, классификация Вольфрама стала первой попыткой классифицировать сами правила. В порядке возрастания сложности классы следующие:
Класс 1: Почти все начальные паттерны быстро эволюционируют в стабильное, однородное состояние. Любая случайность в начальном паттерне исчезает. Класс 2: Почти все начальные паттерны быстро эволюционируют в стабильные или колеблющиеся структуры. Часть случайности в начальном паттерне может отфильтровываться, но часть сохраняется. Локальные изменения в начальном паттерне, как правило, остаются локальными. Стабильные или колеблющиеся структуры типа класса 2 могут быть конечным результатом, но число шагов, необходимых для достижения этого состояния, может быть очень большим, даже если начальный паттерн относительно прост. Локальные изменения в начальном паттерне могут распространяться неограниченно. Вольфрам предположил, что многие клеточные автоматы класса 4, если не все, способны к универсальным вычислениям. Это было доказано для правила 110 и игры «Жизнь» Конвея. Эти определения носят качественный характер и допускают некоторую интерпретацию. По словам Вольфрама, «при почти любой общей схеме классификации неизбежно возникают случаи, которые относят к одному классу по одному определению, а к другому классу – по другому. И то же самое справедливо для клеточных автоматов: иногда встречаются правила, демонстрирующие некоторые признаки одного класса и некоторые признаки другого». Классификация Вольфрама эмпирически сопоставлена с кластеризацией сжатых длин выходных данных клеточных автоматов. Было предпринято несколько попыток классифицировать клеточные автоматы в формально строгие классы, вдохновленные классификацией Вольфрама. Например, Кулик и Ю предложили три четко определенных класса (и четвертый для автоматов, не соответствующих ни одному из них), которые иногда называют классами Кулика — Ю; принадлежность к этим классам оказалась неразрешимой задачей. Класс 2 Вольфрама можно разделить на две подгруппы: стабильных (фиксированных точек) и колеблющихся (периодических) правил. Идея о том, что существует 4 класса динамических систем, изначально возникла у химика Ильи Пригожина, лауреата Нобелевской премии, который выделил эти 4 класса термодинамических систем: (1) системы в термодинамическом равновесии, (2) пространственно-временные однородные системы, (3) хаотические системы и (4) сложные системы, далекие от равновесия, с диссипативными структурами (см. рисунок 1 в статье 1974 года Николиса, ученика Пригожина).

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 types 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. 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. 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." Wolfram's classification has been empirically matched to a clustering of the compressed lengths of the outputs of cellular automata. There have been several attempts to classify cellular automata in formally rigorous classes, inspired by 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. Wolfram's class 2 can be partitioned into two subgroups of stable (fixed point) and oscillating (periodic) rules. 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 the 1974 paper of Nicolis, Prigogine's student).

Возвратимый

Клеточный автомат обратим, если для каждой текущей конфигурации клеточного автомата существует ровно одна конфигурация прошлого (прообраз). Если рассматривать клеточный автомат как функцию, отображающую конфигурации в конфигурации, то обратимость подразумевает, что эта функция является биекцией. Для клеточных автоматов, в которых не каждая конфигурация имеет прообраз, конфигурации без прообразов называются узорами Эдемского сада. Для одномерных клеточных автоматов существуют известные алгоритмы для определения, является ли правило обратимым или необратимым. Однако для клеточных автоматов двух и более измерений обратимость неразрешима; то есть, не существует алгоритма, который принимает на вход правило автомата и гарантированно правильно определяет, является ли автомат обратимым. Доказательство Яркко Кари связано с задачей о покрытии плитками Ванга. Обратимые клеточные автоматы часто используются для моделирования таких физических явлений, как динамика газов и жидкостей, поскольку они подчиняются законам термодинамики. Правила таких клеточных автоматов специально конструируются таким образом, чтобы обеспечивать обратимость. Такие системы изучались Томасо Тоффоли, Норманом Марголусом и другими исследователями. Для явного построения обратимых клеточных автоматов с известными обратными можно использовать несколько методов. Два распространенных метода – клеточный автомат второго порядка и блочный клеточный автомат, оба из которых подразумевают модификацию определения клеточного автомата. Хотя такие автоматы не строго соответствуют приведенному выше определению, можно показать, что они могут быть эмулированы обычными клеточными автоматами с достаточно большими окрестностями и количеством состояний, и поэтому могут рассматриваться как подмножество обычных клеточных автоматов. И наоборот, было показано, что любой обратимый клеточный автомат может быть эмулирован блочным клеточным автоматом.

Тоталистический

Особый класс клеточных автоматов — тоталистические клеточные автоматы. Состояние каждой клетки в тоталистическом клеточном автомате представляется числом (обычно целым числом из конечного множества), и значение клетки в момент времени t зависит только от суммы значений клеток в её окрестности (возможно, включая саму клетку) в момент времени t − 1. Если состояние клетки в момент времени t зависит как от её собственного состояния, так и от суммы значений её соседей в момент времени t − 1, то клеточный автомат корректно называется внешним тоталистическим.

Связанные автоматы

Существует множество возможных обобщений концепции клеточного автомата. Один из способов — использовать нечто иное, чем прямоугольная (кубическая и т. д.) сетка. Например, если плоскость покрыта правильными шестиугольниками, эти шестиугольники можно использовать в качестве ячеек. Во многих случаях полученные клеточные автоматы эквивалентны тем, которые имеют прямоугольные сетки со специально разработанными окрестностями и правилами. Другой вариант — сделать саму сетку нерегулярной, например, с использованием плиток Пенроуза. Кроме того, правила могут быть вероятностными, а не детерминированными. Такие клеточные автоматы называются вероятностными клеточными автоматами. Вероятностное правило задает, для каждого шаблона в момент времени t, вероятности перехода центральной ячейки в каждое возможное состояние в момент времени t + 1. Иногда используется более простое правило; например: «Правило — Игра Жизни, но на каждом шаге времени существует вероятность 0,001%, что каждая ячейка перейдет в противоположный цвет». Окрестность или правила могут меняться со временем или в пространстве. Например, первоначально новое состояние ячейки может определяться горизонтально соседними ячейками, но для следующего поколения будут использоваться вертикальные ячейки. В клеточных автоматах новое состояние ячейки не зависит от нового состояния других ячеек. Это можно изменить так, чтобы, например, блок ячеек 2x2 определялся самим собой и соседними с ним ячейками. Существуют также непрерывные автоматы. Они похожи на тоталистические клеточные автоматы, но вместо дискретных правил и состояний (например, таблицы, использующей состояния {0, 1, 2}), используются непрерывные функции, а состояния становятся непрерывными (обычно значения в [0, 1]). Состояние местоположения представляется конечным числом действительных чисел. Определенные клеточные автоматы могут таким образом моделировать диффузию в жидких структурах. Непрерывные пространственные автоматы имеют континуум местоположений. Состояние местоположения представляется конечным числом действительных чисел. Время также непрерывно, и состояние эволюционирует в соответствии с дифференциальными уравнениями. Важным примером являются реакционно-диффузионные текстуры — дифференциальные уравнения, предложенные Аланом Тьюрингом для объяснения того, как химические реакции могут создавать полосы на зебрах и пятна на леопардах. При аппроксимации этими уравнениями клеточных автоматов часто получаются схожие структуры. МакЛеннан рассматривает непрерывные пространственные автоматы как модель вычислений. Известны примеры непрерывных пространственных автоматов, демонстрирующих распространяющиеся явления, аналогичные планерам в Игре Жизни. Автоматы переписывания графов являются расширениями клеточных автоматов, основанными на системах переписывания графов.

There are many possible generalizations of the cellular automaton concept. 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. 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. When these are approximated by cellular automata, they often yield similar patterns. MacLennan 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. Graph rewriting automata are extensions of cellular automata based on graph rewriting systems.

Элементарные клеточные автоматы

Самый простой нетривиальный клеточный автомат был бы одномерным, с двумя возможными состояниями для каждой клетки, а соседями клетки считаются непосредственно прилегающие клетки с обеих сторон. Клетка и её два соседа образуют окрестность из 3 клеток, поэтому существует 2³ = 8 возможных конфигураций окрестности. Правило заключается в определении, будет ли клетка содержать 1 или 0 в следующем поколении, для каждой конфигурации. Таким образом, существует 2⁸ = 256 возможных правил. В 2004 году доказательство Кука было наконец опубликовано в журнале Complex Systems издательства Wolfram (Vol. 15, No. 1), более чем через десять лет после того, как Кук его сформулировал. Правило 110 послужило основой для некоторых из самых компактных универсальных машин Тьюринга.

Пространство правил

Элементарное правило клеточного автомата задается 8 битами, и все элементарные правила клеточного автомата можно рассматривать как расположенные в вершинах 8-мерного гиперкуба. Этот гиперкуб и является пространством правил клеточного автомата. Для клеточных автоматов со следующими ближайшими соседями правило задается 25 = 32 битами, а пространство правил клеточного автомата – 32-мерным гиперкубом. Расстояние между двумя правилами можно определить как число шагов, необходимых для перехода от одной вершины, представляющей первое правило, к другой вершине, представляющей другое правило, по ребру гиперкуба. Это расстояние между правилами также называется расстоянием Хэмминга. Пространство правил клеточного автомата позволяет задаться вопросом, находятся ли правила с похожим динамическим поведением "близко" друг к другу. Графическое представление высокомерного гиперкуба на двумерной плоскости остается сложной задачей, и одним из способов приблизительного определения положения правила в гиперкубе является количество единичных битов в 8-битной строке для элементарных правил (или в 32-битной строке для правил с учетом следующих ближайших соседей). Изображение правил, относящихся к различным классам Вольфрама, на этих срезах пространства правил показывает, что правила класса 1, как правило, имеют меньшее количество единичных битов и, следовательно, расположены в одной области пространства, в то время как правила класса 3, как правило, имеют более высокую долю (50%) единичных битов. Это наблюдение является основой для выражения «край хаоса» и напоминает фазовый переход в термодинамике.

Биология

[[Файл:Текстильный конус. JPG|мини|слева|Конус текстильный демонстрирует рисунок, напоминающий клеточный автомат, на своей раковине. Полоса клеток оставляет цветной узор на раковине по мере её медленного роста. Например, широко распространенный вид *Conus textile* имеет узор, напоминающий клеточный автомат по правилу 30 Вольфрама. Движущиеся волновые узоры на коже головоногих моллюсков можно смоделировать с помощью двухсостоятельного двумерного клеточного автомата, где каждое состояние соответствует расширенному или сокращенному хроматофору. Пороговые автоматы были разработаны для моделирования нейронов, и с их помощью можно моделировать сложные поведения, такие как распознавание и обучение. Фибробласты обладают сходством с клеточными автоматами, поскольку каждый фибробласт взаимодействует только со своими ближайшими соседями. Кроме того, биологические явления, требующие явного моделирования скоростей агентов (например, связанные с коллективной миграцией клеток), могут быть смоделированы клеточными автоматами с более сложным пространством состояний и правилами, такими как биологические решетчатые газовые клеточные автоматы. К ним относятся явления, имеющие большое медицинское значение, такие как:

Характеристика различных механизмов метастатического вторжения. Роль гетерогенности в развитии агрессивных карцином. Фенотипическое переключение во время пролиферации опухоли.

Химия

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

Физика

Визуализация клеточного газового автомата. Оттенки серого отдельных пикселей пропорциональны плотности частиц газа (от 0 до 4) в данном пикселе. Газ окружен оболочкой из желтых ячеек, которые действуют как отражатели, создавая замкнутое пространство. Вероятностные клеточные автоматы используются в статистической физике и физике конденсированного состояния для изучения явлений, таких как гидродинамика и фазовые переходы. Модель Изинга является прототипическим примером, в котором каждая ячейка может находиться в одном из двух состояний, называемых "вверх" и "вниз", представляя собой идеализированную модель магнита. Путем настройки параметров модели можно изменять долю ячеек, находящихся в одном и том же состоянии, что помогает понять, как ферромагнетики теряют намагниченность при нагревании. Более того, результаты изучения фазового перехода демагнетизации могут быть применены к другим фазовым переходам, например, к испарению жидкости в газ; эта удобная универсальность известна как универсальность. Фазовый переход в двухмерной модели Изинга и других системах, принадлежащих к ее классу универсальности, представляет особый интерес, поскольку для его глубокого понимания требуется конформная теория поля. Другие клеточные автоматы, имеющие значение для физики, включают решетчатые газовые автоматы, которые моделируют потоки жидкости.