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

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

Интересующие нас клеточные автоматы как инструмент математического моделирования ввёл в конце 1940 годов фон Нейман, следуя идее Улама. В качестве основной цели преследовалась необходимость обеспечения более реалистичных моделей поведения сложных и распределённых в двух- или трёхмерном пространстве систем. В его клеточных автоматах и объекты, характеризующиеся массивами пассивных данных, и объекты, описывающиеся как вычислительные устройства, собираются из одного типа структурных элементов и подчиняются одним и тем же законам.

При том, что фон Нейман был ведущим физиком и математиком, точные физические рассуждения в его работах по клеточным автоматам отсутствуют. Учёного в большей степени интересовало объяснение определенных аспектов биологии. И в самом деле, принципы межклеточного взаимодействия, которые им были предложены для реализации с помощью клеточного автомата, оказались схожими с открытыми в следующем десятилетии механизмами, реально наблюдаемыми в биологических системах.

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

Работа фон Неймана по самовоспроизводящимся автоматам была завершена и описана одним из конструкторов первого электронного компьютера Бёрксом, который сохранил активный интерес к этой области и на протяжении последующих лет. Его «Очерки по клеточным автоматам» являлись хорошим обобщением знаний того времени в данной области. Одновременно с работами Бёркса его коллега по Мичиганскому университету Голланц приступил к использованию клеточных автоматов для решения задач адаптации и оптимизации. Им был разработан программный имитатор универсальных клеточных автоматов общего назначения.

Тем временем специалисты-математики начали пристально изучать итерационные преобразования в пространственно-распределённых структурах с дискретным набором состояний – по сути, клеточных автоматах. Узкий круг научного общения, изолированность отдельных научных сообществ и, как следствие, отсутствие единой терминологии вели, с одной стороны, к частичному дублированию работ, а с другой стороны, – к их замедлению.

Игра английского математика Конуэя «Жизнь», основанная на принципах клеточного автомата, была представлена широкой общественности в 1970 году. Благодаря её популяризации с помощью ряда научных и научно-популярных изданий, в том числе в журнале Scientific American, она довольно продолжительное время пользовалась особым успехом и закрепила понятие «клеточный автомат» в научной терминологии исследователей.

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

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

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

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

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