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


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

Кле́точный автома́т — дискретная модель, изучаемая в математике, теории вычислимости, физике, теоретической биологии и микромеханике. Включает регулярную решётку ячеек, каждая из которых может находиться в одном из конечного множества состояний, таких как 1 и 0. Решетка может быть любой размерности. Для каждой ячейки определено множество ячеек, называемых соседством. К примеру, соседство может быть определено как все ячейки на расстоянии не более 2 от текущей. Для работы клеточного автомата требуется задание начального состояния всех ячеек, и правил перехода ячеек из одного состояния в другое. На каждой итерации, используя правила перехода и состояния соседних ячеек, определяется новое состояние каждой ячейки. Обычно правила перехода одинаковы для всех ячеек и применяются сразу ко всей решётке.

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

Содержание

История

Станислав Улам, работая в Лос-аламосской национальной лаборатории в 1940-е годы, изучал рост кристаллов, используя простую решёточную модель. В это же время Джон фон Нейман, коллега Улама, работал над проблемой самовоспроизводящихся систем. Первоначальная концепция фон Неймана основывалась на идее робота, собирающего другого робота. Такая модель известна как кинематическая. Разработав эту модель, фон Нейман осознал сложность создания самовоспроизводящегося робота и, в частности, обеспечения необходимого "запаса частей", из которого должен строиться робот. Улам предложил фон Нейману использовать более абстрактную математическую модель, подобную той, что Улам использовал для изучения роста кристаллов. Таким образом возникла первая клеточно-автоматная система. Подобно решётке Улама, клеточный автомат фон Неймана двухмерный, а самовоспроизводящийся робот описан алгоритмически. Результатом явился универсальный конструктор, работающий "внутри" клеточного автомата с окрестностью, включающей непосредственно прилегающие ячейки, и имеющего 29 состояний. Фон Нейман доказал, что для такой модели существует паттерн, который будет бесконечно копировать самого себя.

Также в 1940-е годы, Норберт Винер и Артуро Розенблют разработали клеточно-автоматную модель возбудимой среды. Целью было математическое описание распространения импульса в сердечных нервных узлах. Их оригинальная работа продолжает цитироваться в современных исследованиях по аритмии и возбудимым средам.

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

В 1970-е получила известность двухмерная клеточно-автоматная модель с двумя состояниями, известная как игра "Жизнь". Изобретенная Джоном Конвеем и популяризованная Мартином Гарднером, она использует следующие правила: если клетка имеет двух "живых" соседей, она остаётся в прежнем состоянии. Если клетка имеет трёх "живых" соседей, она переходит в "живое" состояние. В остальных случаях клетка "умирает". Несмотря на свою простоту, система проявляет огромное разнообразие поведения, колеблясь между очевидным хаосом и порядком. Одним из феноменов игры "Жизнь" являются глайдеры - сочетания клеток, движущиеся по сетке как единое целое. Возможно построить автомат, в котором глайдеры будут выполнять некоторые вычисления, и впоследствии было показано, что игра "Жизнь" может эмулировать универсальную машину Тьюринга.

В 1969 году немецкий инженер Конрад Цузе опубликовал книгу "Вычислимый космос", где выдвинул предположение, что физические законы дискретны по своей природе, и что вся Вселенная является гигантским клеточным автоматом. Это была первая книга из области, называемой сейчас цифровой физикой.

В 1983 Стивен Вольфрам опубликовал первую из серии статей, исследующих очень простой, но до сих пор неизученный класс клеточных автоматов, называемых элементарными клеточными автоматами. Неожиданная сложность поведения этих простых автоматов привела Вольфрама к предположению, что сложность естественных систем обусловлена сходным механизмом. Кроме того, в течение этого периода Вольфрам формулирует концепцию истинной случайности и вычислительной неприводимости, и выдвигает предположение, что Правило 110 (англ.)русск. может быть универсальным - факт, доказанный в 1990 году ассистентом Вольфрама Мэтью Куком.

В 2002 году Вольфрам публикует 1280-страничный текст "Новый тип науки" (A New Kind of Science), где широко аргументирует, что достижения в области клеточных автоматов не являются изолированными, но весьма устойчивы и имеют большое значение для всех областей науки.

11-го ноября 2002 года Пауль Чепмен (Paul Chapman) построил образец Жизни, который является РММ (Регистровой Машиной Минского). Фактически РММ эквивалентна машине Тьюринга. Первая версия образца была большой (268,096 живых ячеек на площади 4,558 x 21,469 клеток) и медленной (20 поколений/сек при использовании Life32 Иогана Бонтеса (Johan Bontes) на 400 MHz AMD K6-II). Таким образом, в игре Жизнь можно выполнить любой алгоритм, который можно реализовать на современном компьютере.

Математическое определение

Клеточный автомат можно определить как множество конечных автоматов, каждый из которых может находиться в одном из состояний

\sigma \in \Sigma \equiv \{0,1,2 ... k-1, k\}.

Изменение состояний автоматов происходит согласно правилу перехода

\sigma_{i,j}(t+1)=\phi(\sigma_{k,l}(t)|\sigma_{k,l}(t) \in {\mathcal N}),

где {\mathcal N} - множество автоматов, составляющих соседство. К примеру, соседство фон Неймана определяется как

{\mathcal N}_N^1(i,j)=\{\sigma_{k,l}|~|i-k|+|j-l|\le 1\},

а соседство Мура

{\mathcal N}_M^1(i,j)=\{\sigma_{k,l}|~|i-k|\le 1, |j-l|\le 1\}.

Число всех возможных правил перехода определяется числом состояний \sigma и количеством соседей n и составляет

N_r=\sigma^{\sigma^n} [1]

Свойство обратимости

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

Для одномерных клеточных автоматов существуют алгоритмы определения обратимости или необратимости. Однако для клеточных автоматов с двумя и более измерениями таких алгоритмов нет.

Обратимые клеточные автоматы часто используют для моделирования таких физических феноменов, как динамика жидкости и газа, поскольку они подчиняются законам термодинамики. Такие автоматы специально создаются обратимыми. Такие системы изучались Томасо Тоффоли (Tommaso Toffoli) и Норманом Марголусом (Norman Margolus). Существует несколько типов обратимых конечных автоматов. Наиболее известными являются клеточный автомат второго порядка и блочный клеточный автомат. Обе эти модели следуют несколько модифицированному варианту определения клеточного автомата, однако доказано, что они могут быть эмулированы традиционным клеточным автоматом со значительно большим размером соседства и числом состояний. Также, было доказано, что любой обратимый клеточный автомат может быть сэмулирован блочным клеточным автоматом.

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

Узор на поверхности раковины Conus textile формируется по механизму клеточного автомата

Некоторые живые организмы проявляют свойства клеточных автоматов. Раскраска некоторых морских ракушек, таких как Conus или Cymbiola, генерируется естественным клеточным автоматом. Их пигментные клетки располагаются тонкой полоской вдоль края раковины. Секреция пигмента каждой клетки зависит от активирующей и ингибиторной активности соседних клеток. В процессе роста полоса клеток оставляет цветной узор на поверхности ракушки.

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

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

Реакция Белоусова-Жаботинского представляет собой пространственно-временной химический осциллятор, который может быть смоделирован клеточным автоматом. В 1950-х годах А.М.Жаботинский, продолжая работу Б.П.Белоусова, обнаружил, что тонкий однородный слой смеси определённых химических веществ способен образовывать движущиеся геометрические узоры, такие как концентрические круги и спирали.

См. также

Примечания

  1. A.G.Hoekstra, J.Kroc, P.Sloot. Simulating complex systems by cellular automata. Springer, 2010. ISBN 978-3-642-12202-6

Ссылки


Wikimedia Foundation. 2010.

Смотреть что такое "Клеточный автомат" в других словарях:

  • клеточный автомат — — [http://www.rfcmd.ru/glossword/1.8/index.php?a=index d=23] Тематики защита информации EN cellular automaton …   Справочник технического переводчика

  • Клеточный автомат Нобили — Клеточный автомат Нобили  разновидность клеточного автомата фон Неймана, в который введены дополнительные состояния для обеспечения памяти и возможности пересечения сигналов без интерференции. Является изобретением Ренато Нобили, профессора… …   Википедия

  • Фронтальный клеточный автомат — (англ. frontal cellular automata, FCA) специальный тип вычислительных алгоритмов, основанных на моделях клеточных автоматов. Название «фронтальный» происходит от одного из популярных применений, а именно, рост кристаллов, когда граница… …   Википедия

  • Циклический клеточный автомат — Циклический клеточный автомат  Класс клеточных автоматов. Система правил, определяющая волнообразное порождение клеток в циклическом клеточном автомате (Cyclic Cellular Automata, CCA), может определять генерацию паттернов, имитирующих… …   Википедия

  • Автомат фон Неймана — Одна из простых конфигураций в клеточном автомате фон Неймана. Двоичный сигнал циркулирует вдоль петли из синих ячеек, используя переход между обычным и возбужденным состоянием передающих ячеек. Коммутирующая ячейка дублирует сигнал в красную… …   Википедия

  • Автомат — В Викисловаре есть статья «автомат» Автомат: Автомат  устройство, самостоятельно выполняющее некоторые действия …   Википедия

  • Клеточные автоматы — Клеточный автомат (КА)  набор клеток, образующих некоторую периодическую решетку с заданными правилами перехода, определяющими состояние клетки в следующий момент времени через состояние клеток, находящимися от нее на расстоянии не больше… …   Википедия

  • Метод подвижных клеточных автоматов — Подвижные клеточные автоматы активно меняют своих соседей за счет разрыва существующих связей между автоматами и образования новых связей (моделирование контактного взаимодействи …   Википедия

  • Теория хаоса — У этого термина существуют и другие значения, см. Теория хаоса (значения). Диаграмма раздвоения логистической карт …   Википедия

  • Цифровая физика — Цифровая физика, в физике и космологии,  совокупность теоретических взглядов, проистекающих из допущения, что Вселенная по сути описывается информацией и, следовательно, является вычислимой. Из данных предположений следует то, что… …   Википедия

Книги