Клеточные автоматы - реализация и эксперименты

Данная статья, надеемся, привлечет внимание программистов к такой чрезвычайно увлекательной и полезной области дискретной математики, как клеточные автоматы, которые могут обладать весьма сложным поведением, несмотря на простоту описания их клеток. Один из крупнейших специалистов в области информатики — Марвин Минский [1] считает, что самым важным при этом, видимо, является изучение различных путей возникновения сложного поведения при использовании простых устройств, действий, описаний или концепций. Нам кажется, что не существует ничего более подходящего для этой цели, чем клеточные автоматы.

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

К рассматриваемой области принадлежит также теория хаоса [4], признанная, наряду с теорией относительности и квантовой теорией [5], одним из основных теоретических достижений XX в. Нельзя сказать, что математический аппарат, применяемый в ней, прост. И для этой теории весьма актуальны исследования клеточных автоматов. Такие автоматы, как отмечалось выше, зачастую порождают сложное поведение даже при использовании действительно очень простого и наглядного математического аппарата. В настоящей работе поведение каждой из клеток описывается одной булевой формулой и демонстрируются различные формы их самовоспроизведения (рост, клонирование, перемещение). Рассматриваются два класса клеток: с памятью, обладающие лишь двумя состояниями, и без памяти.

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

Клеточные автоматы были предложены в работе фон Неймана [6]. Большой интерес к ним вызван тем, что такие автоматы являются универсальной моделью параллельных вычислений подобно тому, как машины Тьюринга являются универсальной моделью для последовательных вычислений [7].

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

• Изменения значений всех клеток происходят одновременно после вычисления нового состояния каждой клетки решетки.
• Решетка однородна - невозможно различить какие-либо две области решетки по ландшафту.
• Взаимодействия локальны. Лишь клетки окрестности (как правило, соседние) способны повлиять на данную клетку.
• Множество состояний клетки конечно.

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

1. Вводятся два массива для хранения состояний клеток: первый из них содержит текущее состояние каждой клетки, второй предназначен для хранения нового ее состояния.
2. Определяется функция переходов клетки решетки. Для выявления следующего ее состояния в качестве параметров в функцию переходов передаются текущие значения состояний клеток окрестности, возможно, включая ее саму. Эта функция будет задана в виде булевой формулы.
3. На нулевом шаге решетка (первый массив) заполняется начальными данными, что полностью определяет поведение системы для выбранных решетки и функции переходов клетки.
4. вычисления новых состояний вводится цикл. На каждой итерации для любой клетки, используя в качестве переменных элементы первого массива, определяется ее новое состояние, помещаемое во второй массив. Значения аргументов функции переходов берутся из первого массива.
5. По завершении итерации значения из всех элементов второго массива переносятся в первый, что обеспечивает синхронное изменение значений состояний всех клеток решетки.
6. Визуализируется содержимое решетки. В зависимости от ее размерности (одномерная или двумерная) отображение решетки производится по-разному.
   
   6.1. Для одномерной (линейной) решетки после каждой итерации выводится соответствующая ей строка. Их расположение одна под другой позволяет наблюдать динамику системы во времени (ось времени направлена вертикально вниз).
   
   6.2. Для двумерной (плоскостной) решетки в каждый момент времени отражается результат лишь последней итерации. Последовательный переход от одной итерации к другой позволяет наблюдать динамику системы.
7. Нажатием клавиши выполняется переход к пункту 4, а нажатие на клавишу q завершает работу программы.

Чтобы облегчить понимание листингов программ, в них применяется текстовый вывод информации. Программы, использованные в примерах, можно найти на сайте http://is.ifmo.ru в разделе «Статьи».

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

В одномерном (линейном) клеточном автомате решетка представляет собой цепочку клеток (одномерный массив), в которой для любой из них, кроме крайних, имеется по два соседа. Для устранения краевых эффектов решетка «заворачивается» в тор, что позволяет для всех клеток автомата использовать следующее соотношение:

где f — функция переходов клетки;

y'[i] — состояние i-й клетки в следующий момент времени;

y[i-1] — состояние (i-1)-й клетки в данный момент времени;

y[i] — состояние i-й клетки в данный момент времени;

y[i+1] — состояние (i+1)-й клетки в данный момент времени.

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

Пример 1. Пусть функция переходов клетки имеет такой вид:

где | — символ логической операции «дизъюнкция» на языке программирования Си.

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

Рис. 1. Поведение первого одномерного клеточного автомата (пример 1)

Рис. 2. Поведение первого одномерного клеточного автомата (пример 2)

Рис. 3. Поведение второго одномерного клеточного автомата

Эта программа позволяет представить поведение клеточного автомата во времени (рис. 1). Такое поведение может быть названо «пирамида».

Пример 2. Если при сохранении функции переходов в начальном заполнении решетки изменить состояние еще одной клетки с нуля на единицу, то поведение автомата станет другим (рис. 2). Оно может быть названо «горы».

Пример 3. Второй клеточный автомат характеризуется следующей функцией переходов:

где ^ — символ логической операции «неравнозначность» («сумма по модулю два») в языке программирования Си.

Выбирая в качестве начального то же заполнение решетки, что и в примере 1, получим поведение, которое можно назвать «пробор».

Пример 4. Выберем для третьего клеточного автомата следующую функцию переходов:

Рис. 4. Поведение третьего одномерного клеточного автомата

Этот автомат при тех же начальных условиях, что и в предыдущем примере, порождает самовоспроизводящуюся структуру (рис. 4).

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

Окрестность из восьми клеток

В двумерном (плоскостном) клеточном автомате решетка реализуется двумерным массивом. В ней каждая клетка имеет восемь соседей. Для устранения краевых эффектов решетка так же, как и в предыдущем случае, «заворачивается» в тор. Это позволяет использовать для всех клеток автомата соотношение:

Пример 5. Наиболее известным из двумерных клеточных автоматов является автомат, моделирующий игру «Жизнь» [9]. В нем, как и во всех рассмотренных выше, клетки могут находиться в двух состояниях. Функция переходов клеток реализует следующие условия:

• если данная клетка мертва (находится в состоянии "ноль"), то она оживет (перейдет в состояние "единица") при условии, что у нее имеются три живых соседа;
• если данная клетка жива, то она останется живой только при условии, что у нее есть два или три живых соседа, в противном же случае она умрет.

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

Программа, реализующая игру «Жизнь», структура которой была описана выше, приведена в листинге 2. В ней решетка имеет размеры 23х23, а в качестве начальных условий выбран «планер» [9].

«Планер» был выбран в качества примера, так как является наиболее простым из «летающих» объектов. Он «летает» в том смысле, что перемещается за счет самовоспроизведения, происходящего с периодом в четыре шага.

Пример 6. В качестве примера самовоспроизведения рассмотрим клеточный автомат, функционирующий по правилу:

Данная функция принципиально не отличается от приведенной в примере 4, поскольку обе они вычисляют сумму по модулю два от состояний всех соседей и самой клетки.

Рис. 5. Начальная конфигурация	Рис. 6. Конфигурация через 8 шагов

На рис. 5 приведена начальная конфигурация решетки, а на рис. 6 — результат ее самовоспроизведения через восемь шагов.

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

где a и b — ширина и высота «зародыша» соответственно.

Для начальной конфигурации, изображенной на рис. 5, a = 3, b = 5. Поэтому T = 8, и следовательно, самовоспроизведение имеет место через 8, 16, 32, 64 и т. д. шагов.

Окрестность из четырех клеток

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

Рассмотрим в качестве окрестности данной клетки лишь те, которые имеют общую сторону с ней и называются «главными соседями».

Пример 7. Для иллюстрации самовоспроизведения при помощи автомата с такой окрестностью выберем следующую функцию переходов:

Вновь используем в качестве начального заполнения конфигурацию, изображенную на рис. 5. Самовоспроизведение может происходить независимо как по горизонтали, так и по вертикали, на шагах, номера которых определяются соотношениями:

При этом период полного самовоспроизведения вычисляется на основе соотношения:

Для рассматриваемого «зародыша» (рис. 5) период самовоспроизведения по горизонтали T_a равен 4 (рис. 7), а по вертикали, T_b равен 8 (рис. 8). Поэтому полный период самовоспроизведения T равен 8.

Рис. 7. Конфигурация через 4 шага	Рис. 8. Конфигурация через 8 шагов

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

Пример 8. Если сохранить функцию переходов и выбрать в качестве начальной конфигурации единицу в центральной точке решетки, то на 15-м шаге получится конфигурация, изображенная на рис. 9, а на 29-м — на рис. 10.

Рис. 9. Конфигурация на 15-м шаге	Рис. 10. Конфигурация на 29-м шаге

Несмотря на то что решетка размером 23х23 способна находиться в 2^23?23 состояниях, для выбранных функции переходов и начальных условий она может быть лишь в 1024 различных состояниях, периодически повторяющихся. Сокращение числа состояний в данном случае обеспечивается только за счет размеров решетки и «заворачивания» ее в тор. Если бы решетка имела большие размеры, то на этих шагах состояния были бы другими, так как после 11-го шага противоположные края рассматриваемой решетки начинают влиять друг на друга. Это объясняется тем, что информация распространяется за шаг на одну клетку, и поэтому из центральной она дойдет до границы за (23-1)/2 шагов.

Автоматы с клетками без памяти

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

Несмотря на то что в автоматах этого класса клетки памятью не обладают, за счет переобозначения переменных такие автоматы в целом имеют память. Этот класс автоматов является простейшим, применение которого обеспечивает самовоспроизведение.

Пример 9. Рассмотрим простейший клеточный автомат, обеспечивающий самовоспроизведение. Его можно построить, если в примере 4 при тех же начальных условиях упростить функцию переходов:

Рис. 11. Поведение одномерного автомата с клетками без памяти

Поведение этого автомата во времени показано на рис. 11.

Интерактивная программа, реализующая пример двумерного автомата рассматриваемого класса с функцией переходов

приведена в работе [10].

Искусственная жизнь

Сейчас на смену термину «искусственный интеллект» пришел более широкий термин — «искусственный интеллект и искусственная жизнь» [11]. По мнению авторов, настоящую работу можно рассматривать как введение в «искусственную жизнь». Кроме того, отметим, что активно развивается такая наука, как синергетика. Ее название происходит от греческих слов «син» — совместный и «эргос» — действовать [12]. Поэтому синергетика — это наука о совместном согласованном поведении многих элементов как единого целого в составе сложной системы. Из изложенного следует, что данная работа может рассматриваться также и в качестве введения в «синергетику».

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

Работа выполнена при поддержке Российского фонда фундаментальных исследований по гранту №02-07-90114 «Разработка технологий автоматного программирования»

Литература

1. Минский М. Вычисления и автоматы. М.: Мир, 1971.
2. Пайтген Х.О., Рихтер П.Х. Красота фракталов. Образы комплексных динамических систем. М.: Мир, 1993.
3. Вирт Н. Алгоритмы и структуры данных. СПб.: Невский диалект, 2001.
4. Пригожин И., Стенгерс И. Порядок из хаоса. Новый диалог человека с природой. М.: Эдиториал УРСС, 2000.
5. Пайс А. Гении науки. М.: Институт компьютерных исследований, 2002.
6. Нейман Дж фон. Теория самовоспроизводящихся автоматов. М.: Мир, 1971.
7. Шалыто А., Туккель Н. От тьюрингова программирования к автоматному // Мир ПК. 2002. №2.
8. Варшавский В.И., Мараховский В.Б., Песчанский В.А., Розенблюм Л.Я. Однородные структуры. М., 1973.
9. Гарднер М. Математические досуги. М.: Мир, 1972.
10. Федотьев А. Клеточный автомат -http://rain.ifmo.ru/~fedotiev/.
11. Тарасов В.Б. От многоагентных систем к интеллектуальным организациям: философия, психология, информатика. М.: Эдиториал УРСС, 2002.
12. Колесников А.А. Шанс для рывка // Поиск. 2002. №42.

Об авторах

Наумов Лев Александрович — студент кафедры «Компьютерные технологии» С.-Петербургского государственного института точной механики и оптики (технического университета) — СПбГИТМО (ТУ), е-mail: levnaumov@mail.ru.

Шалыто Анатолий Абрамович — профессор кафедры «Компьютерные технологии» СПбГИТМО (ТУ), е-mail: mail@avrorasystems.com (для Шалыто); : http://is.ifmo.ru.