В статье “Тьюрмиты — двумерные машины Тьюринга” (опубликована в журнале “Мой компьютер” №28(303) за 2004 год) я познакомил Вас с некоторыми существами, обитающими на клеточной плоскости. Они передвигались по ней, окрашивая эту плоскость в разные цвета по определенным правилам. Эти объекты представляли собой автоматы с несколькими состояниями. А теперь обратим свой взгляд на другой тип автоматов – на клеточные автоматы (КА). Если тьюрмитами заселялась плоскость, разбитая на клетки, то теперь автоматом у нас будет сама эта плоскость, состояние клеток которой будет изменятся по определенным правилам. Итак, что же нужно для клеточного автомата? Во-первых, это бесконечная (или конечная) плоскость, разделенная на клетки (квадратные или другой формы). Каждая из клеток может быть в одном из состояний из определенного набора состояний (то есть состояние клетки дискретно). Во-вторых, часы. Время в клеточном автомате тоже дискретно. И в-третьих, набор правил, который определяет поведение автомата. Автомат работает так:
  1. Задается начальное состояние всех клеток КА
  2. Для каждой из клеток по определенным правилам из состояния клеток-соседей и самой клетки вычисляется следующее её состояние.
  3. На каждом шаге клетки меняют свое состояние одновременно.
Дальше будем рассматривать автоматы с квадратными клетками, а треугольные, шестиугольные и другие оставим в покое. (Удивительно, но КА с клетками неквадратной формы можно моделировать с помощью КА с квадратными клетками) Особо надо определить соседей клетки (или её окрестность). Если в расчет берутся сама клетка и клетки,соприкасающиеся с ней только сторонами (их четыре), такая окрестность называется окрестностью фон Неймана (рисунок 1).

1

Если же в расчет берутся сама клетка и клетки, соприкасающиеся с ней не только сторонами, но и углами, такая окрестность называется окрестностью Мура (рисунок 2).

2

Самый известный из всех КА – это конечно же игра “Жизнь”, изобретенная Дж.Конвеем.
Мы рассматриваем клеточные автоматы в двухмерном пространстве (на плоскости), однако, никто не ограничивает автоматы двумя измерениями. Правила игры можно перенести и в три, и в большее количество измерений. Например, существуют трехмерные версии игры “Жизнь”.
Правила игры “Жизнь” очень просты:
  1. Клетки могут находится в двух состояниях — “живая” или “мертвая” клетка
  2. Окрестность клетки – окрестность Мура (сама клетка и 8 соседей)
  3. Живая клетка, имеющая 2 или 3 живых соседей остается живой на следующем шаге.
  4. Любая клетка, имеющая менее 2 или более 3 живых соседей, умирает.
  5. Мертвая клетка, имеющая 3 живых соседей на следующем шаге превращается в живую.
Казалось бы, ничего сложного. Однако, в процессе моделирование такого КА возникают очень интересные конфигурации клеток (например, планеры, передвигающиеся по клеточному полю, пульсары, планерные ружья и т.д.). Кстати, доказано, что в пространстве этой игры можно построить универсальный компьютер, в котором информация представляется потоком планеров. Не буду сильно распространяться на тему игры Конвея, любой желающий может найти в сети замечательную статью Мартина Гарднера — Игра «ЖИЗНЬ». Позже мы перейдем к рассмотрению менее известных, но не менее красивых клеточных автоматов, а пока попробуем написать программу к игре “Жизнь”, которая послужит нам основой для других клеточных автоматов.

Каркас программы

Как обычно, буду писать на некотором гипотетическом языке. Для начала нам нужен массив, который будет хранить состояние каждой клетки. Назовем его
1
old[0..sizeX-1,0..sizeY-1]
(sizeX, sizeY – размер поля соответственно по горизонтали и вертикали. Можно было бы использовать координаты клеток начиная с 1, но с нуля начинать удобнее). Затем, нам нужен еще один массив new (такой же как и old), где мы будем хранить значения, которые получат наши клетки на следующем шаге. Итак:
1
2
3
4
5
6
7
8
ЗадатьНачальнуюКонфигурацию(old)
Начать
    для i:=0 до sizeX-1
        для j:=0 до sizeY-1
            new[i,j]:=Правило(i,j)
    old:=new
    Вывести(new)
Снова
Некоторые пояснения. Сначала нужно задать начальную конфигурацию клеток. Как – не буду расписывать. Это может быть и заполнение массива случайным образом, может из файла, или пользователем вручную. Основной цикл программы такой: проходим по каждой клетке, по определенному правилу вычисляем новое состояние клетки и записываем его в массив new. Затем переписываем массив new в массив old и выводим на экран состояние клеток. Остается только написать функцию Правило(i,j). Обозначим 0 – мертвая клетка, 1 – живая. Нам нужно вычислить сумму состояний всех соседей нашей клетки, она же будет количеством живых клеток в окрестности. А как быть, если клетка находится на границе массива (то есть i=0 или i=sizeX-1, j=0 или j=sizeY-1). Можно, конечно, проверять все эти условия, но мы схитрим. Свернем наше клеточное поле в тор. То есть левый край поля будет соприкасаться с правым, а верхний – с нижним. На рисунке 2 изображено поле размером 10х10 клеток. Для клетки с координатами (i,j) показаны все ее 8 соседей. Посмотрите, какие соседи у клеток с координатами (0,3) и (5,9).
1
2
3
4
5
6
7
8
9
10
11
12
Функция Правило(i,j)
    im1:=((i-1)+sizeX) mod sizeX
    ip1:=(i+1) mod sizeX
    jm1:=((j-1)+sizeY) mod sizeY
    jp1:=(j+1) mod sizeY
    sum:=old[im1,jm1]+old[im1,j]+old[im1,jp1]+
        old[i,jm1]+old[i,jp1]+
        old[ip1,jm1]+old[ip1,j]+old[ip1,jp1]
    если sum=3 то результат:=1
    иначе если sum=2 то результат:=old[i,j]
    иначе результат:=0
КонецФункции
Здесь у нас im1 – это (i-1) в наших координатах, ip1 – это (i+1), jm1 – (j-1), jp1 – (j+1), mod обозначает взятие остатка от деления. Результат функции вычисляем по вышеприведенному правилу для игры “Жизнь”.

Машина клеточных автоматов 1.2

Вы можете написать программу для моделирования КА и сами, но если такого желания у вас нет, можете скачать мою “Машину клеточных автоматов” и экспериментировать с ней. Программа моделирует все клеточные автоматы, о которых я собираюсь рассказать. Скриншот на рисунке 3.

3

Управлять программой просто. Сначала выбираете тип клеточного автомата, затем задаете его параметры, нажимая соответствующую кнопку. Если программа позволит, можно редактировать начальную конфигурацию (кнопка “Редактировать”). Для запуска нажимаем “Пуск”, для остановки — “Стоп”. Можно изменять размеры поля по горизонтали и вертикали (надо перед этим остановить моделирование), а также увеличение. Также можно выбирать различные цветовые гаммы. Ну вот, теория закончена, можно переходить к исследованию конкретных клеточных автоматов.

Циклический автомат

Циклический автомат был открыт Девидом Гриффитом. Начиная работу со случайным образом выбранным клеточным пространством, такой автомат постепенно преобразует поле клеток во вращающиеся ромбовидные спирали (рисунок 4).

4

Циклический автомат – это клеточный автомат с количеством состояний n (от 0 до n-1). Правило его очень простое. Если клетка на данный момент находится в состоянии k, то на следующем шаге все соседние с ней клетки, находящиеся в состоянии k-1, переходят в состояние k. Можно сказать, что эта клетка “съедает” все клетки по соседству, которые находятся на “низшем” уровне развития. Если клетка находится в состоянии 0, то она “поглощает” все клетки с состоянием n-1. Давайте напишем функцию “Правило” для такого автомата (используем окрестность Фон Неймана):
1
2
3
4
5
6
7
8
9
10
Функция Правило(i,j)
    im1:=((i-1)+sizeX) mod sizeX
    ip1:=(i+1) mod sizeX
    jm1:=((j-1)+sizeY) mod sizeY
    jp1:=(j+1) mod sizeY
    sp1:=(old[i,j]+1) mod n
    если (old[im1,j]=sp1) или (old[ip1,j]=sp1) или (old[i,jm1]=sp1) или (old[i,jp1]=sp1) то
        результат:=sp1
    иначе результат:=old[i,j]
КонецФункции
Первые четыре строки этой функции стандартны – вычисляются координаты соседних клеток на торе. Переменная sp1 – это номер состояния клетки, которая может “съесть” нашу текущую клетку. Этот номер больше текущего состояния клетки на 1 по модулю n. То есть если клетка находится в состоянии n-1, то “съесть” ее может клетка в состоянии 0. Далее проверяется, может ли какая либо из соседних клеток “съесть” нашу клетку, и если это так, то состояние текущей клетки становится равным состоянию клетки, которя ее “съела”. Понаблюдайте за поведением автомата при разных значениях n. В моей программе задавать значение n по умолчанию равно 15. Для изменения n нажимайте кнопку “Параметры”.

Коврик

Вот еще один простой КА, который называется Коврик (рисунок 5).

5

В нем следующее состояние клетки определяется так:
1
2
3
4
5
6
7
8
Функция Правило(i,j)
    im1:=((i-1)+sizeX) mod sizeX
    ip1:=(i+1) mod sizeX
    jm1:=((j-1)+sizeY) mod sizeY
    jp1:=(j+1) mod sizeY
    результат:=(((old[im1,jm1]+old[i,m1]+old[ip1,jm1]+old[im1,j]+old[ip1,j]+
        old[im1,jp1]+old[i,jp1]+old[ip1,jp1])/8+shift) and mask) mod n;
КонецФункции
Мы определяем среднее значение состояния соседних клеток, добавляем сдвиг shift, маскируем маской mask (то есть выполняем логическое сложение с маской) и затем делаем так, чтобы полученное значение не превышало n-1 при помощи взятия остатка от деления.

Перемешивающая машина

Этот автомат уже гораздо сложнее. Он моделирует химические реакции, в которых два разных вещества реагируют с помощью катализатора, например знаменитую реакцию Белоусова-Жаботинского. В этой реакции взаимодействующие вещества образуют сложные волнообразные структуры (см. рисунок 3). Примем за n+1 количество состояний клетки в КА. Клетку в состоянии 0 будем считать “здоровой”, в состоянии n – больной. Промежуточные состояния отражают степень зараженности клетки – чем ближе к n, тем сильнее клетка больна. Если клетка здорова, то на следующем шаге она перейдет в состояние, зависящее от состояния окружающих ее соседей. Пусть А – число зараженных клеток вокруг текущей клетки, В – число больных клеток вокруг нее. Тогда следующее состояние данной клетки определится так: A/k1 + B/k2. Причем деление здесь целочисленное, то есть дробная часть отбрасывается. Результат не должен превышать n. Если же клетка заражена, ее состояние вычисляется так: S/(A+1)+g, где S – сумма состояний самой клетки и всех ее соседей, A – количество зараженных соседей, g – скорость распространения инфекции среди зараженных клеток. Точно так же результат не должен превышать n. Ну и если клетка больна, на следующем шаге она выздоравливает (переходит в состояние 0). Как запрограммировать это? Например, так:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Функция Правило(i,j)
    im1:=((i-1)+sizeX) mod sizeX
    ip1:=(i+1) mod sizeX
    jm1:=((j-1)+sizeY) mod sizeY
    jp1:=(j+1) mod sizeY
    a:=КоличествоЗараженныхКлеток(i,j)
    b:=КоличествоБольныхКлеток(i,j)
    s:=СуммаВсехСоседей(i,j)
    если old[i,j]=N то
        результат:=0
    иначе если old[i,j]=0 то
        результат:=min((a div k1)+(b div k2),N)
    иначе
        результат:=min((s div (a+1))+g,N);
КонецФункции
Сначала посчитаем количество зараженных и больных клеток в окрестности, а также сумму состояний всех соседей и самой клетки (я думаю, нет смысла описывать соответствующие функции, читатели могут написать их сами). Далее, проверяем, по каким формулам вычислять следующее состояние клетки. В формулах вместо того, чтобы проверять, не превышает ли результат n, воспользуемся функцией min, избавляясь таким образом от лишнего условного оператора. Внимательный читатель может еще оптимизировать этот код. Ведь если текущее состояние клетки равно n, нет смысла вычислять переменные a, b и s. По умолчанию значения параметров такие:
1
n:=100, k1:=2, k2:=3, g:=30
.

Произвольные клеточные автоматы

Написав предыдущие программы, я задался мыслью, нельзя ли сделать так, чтобы не перекомпилируя программу, добавлять новые клеточные автоматы. Оказывается можно, правда для автоматов с небольшим количеством состояний. Специально для этого в мою программу включен небольшой C-подобный интерпретатор правил клеточных автоматов. Однако, интерпретаторы не отличаются скоростью вычислений. Поэтому при инициализации автомата только один раз вычисляется специальная таблица. Пользоваться программой в таком случае надо так: выбираем тип автомата “Произвольный клеточный автомат”, нажимаем кнопку “Параметры”. В появившемся окне задаем количество состояний автомата, тип окрестности и вписываем скрипт, с помощью которого и будет расчитана таблица нашего автомата. Формат скриптового языка очень простой и описан в справке (окно “Параметры”, кнопка “Справка”). Лучше всего познакомиться с ним, открыв какой-нибудь из примеров, которые лежат в папке “demos/tabular”, это файлы с расширением .cam. Кроме того, необходимо задать начальную конфигурацию клеточного автомата, нажав кнопку “Редактировать”. Файлы с готовыми начальными конфигурациями лежат в той же папке, но имеют расширение .tab. Чтобы их открыть, в главном окне программы нажмите кнопку “Редактировать”, затем “Открыть”. Выберите файл и “ОК”.
Количество состояний каждой клетки равно n. Следовательно, всех возможных вариантов состояний самой клетки и всех ее соседей равно 9^n (9 в степени n) для окрестности Фон Неймана и 5^n для окрестности Мура. Расчет таблицы при большом значении n занимает очень долгое время. Поэтому специально для больших n в программе есть еще и компилятор. Это компилятор языка Форт (SP-Forth Андрея Черезова, версия 4.016). Он гораздо быстрее.

Wire World

Сейчас я расскажу об одном очень интересном автомате, в некоторых источниках называемом “Wire World”. С его помощью можно моделировать цифровые электронные схемы и теоретически на его основе можно создать компьютер любой мощности (как известно, любой компьютер можно собрать, используя лишь логические схемы только одного типа, например “логическое и-не”). Каждая клетка этого автомата может находиться в одном из четырех состояний: фон, проводник, голова электрона, хвост электрона. Голова и хвост электрона, расположенные рядом, образуют электрон, который движется по проводнику в направлении от хвоста к голове. Правила автомата просты:
  1. На следующем шаге клетка головы электрона переходит в клетку хвоста электрона
  2. Клетка хвоста электрона становится клеткой проводника
  3. Клетка фона всегда остается без изменений
  4. Клетка проводника, вокруг которой только 1 или 2 головы электрона, становится клеткой головы электрона.
Чтобы начать конструирование электронных схем, на клетках фона нужно нарисовать клетки проводника, по которым будут двигаться электроны, а затем ввести электрон. После запуска автомата электрон будет двигаться вдоль проводника справа налево (рисунок 6).

6

Таким образом, логический “0” будет изображаться отсутствием электрона, а “1” — его наличием. На рисунке 7 изображены диоды, пропускающие электроны только в одном направлении, на рисунке 8 – генераторы логической “1”, бесконечно испускающие электроны. Для полного счастья нам нужен какой-нибудь логический элемент, например, “И” (рисунок 9) и инвертор, который, я надеюсь, нетрудно придумать самому. На этих элементах можно построить все, что угодно.

7

8

8

Файл со скриптом этого автомата electro.cam лежит в папке demos/tabular/electro. Однако, просчитывается он очень долго, поэтому лучше открывать файл electro_FORTH.cam – он намного быстрее. В этой же папке лежат и примеры (файлы с расширением .tab). Вы можете посмотреть также и на другие КА в папке demos/tabular.

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

Ну и на закуску – одномерные клеточные автоматы. Представьте, что у клетки есть только соседи слева и справа и все клетки выстроены в одну линию – и получите одномерный КА. Конечно, если состояние клеток будет просто меняться от шага к шагу, ничего интересного вы не увидите, поэтому “развернем” эту строку клеток во времени. Состояние КА в начальный момент времени нарисуем сверху, в следующий момент – чуть ниже и так далее. Получим диаграмму развития КА во времени в направлении сверху вниз (рисунок 10).

10

Пусть количество состояний каждой клетки одномерного КА равно n, а радиус окрестности – r (то есть количество соседних клеток слева или справа. Например для r=1 у клетки два соседа – слева и справа, при r=2 у клетки уже 4 соседа – 2 справа и 2 слева). Следующее состояние клетки зависит от состояния самой клетки и состояния ее соседей. Количество возможных клеточных автоматов колоссально. Попробуем ограничить его. Возьмем автоматы, в которых состояние клетки зависит от суммы состояний самой клетки и клеток окрестности (такие КА называют тоталистическими). Наибольшее значение этой суммы s=n*(r*2-1)-1. Тогда описание самого КА можно свести к одномерной таблице. Очень интересный автомат получается, например, для n=2 и r=2 (s изменяется от 0 до 5) и такой таблице правил:
Сумма 5 4 3 2 1 0
Следующее состояние 0 1 0 1 0 0
Заметьте, что число в двоичной системе, записанное во второй строке – это 20. Этот автомат вы уже видели на рисунке 10. Как и в двумерных клеточных автоматах, например, игре “Жизнь”, в таком автомате могут существовать конфигурации клеток, которые постоянно движутся в одном направлении – планеры. Для автомата “20” — это комбинации 10111011 и 1001111011, они движутся вправо, если их развернуть наоборот, они будут двигаться влево. Есть еще несколько интересных КА, например автомат с n=2, r=3, кодовый номер 88. В нем есть катапульта, которая через каждые 238 шагов стреляет планерами влево и вправо (рисунок 11).

11

Начальная конфигурация катапульты такая: 111111111101. Я думаю, читателям на основе скелета двумерного КА не составит труда написать свою программу и для одномерных клеточных автоматов. Скачать мою программу:
Машина клеточных автоматов
524.5 KiB
736 Downloads
Детали
Если вы захотите воспользоваться моей программой, то примеры одномерных КА лежат в папке demos/1d.

Заключение

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

P.S.

Если вам не хватит примеров из моей статьи, советую загрузить удивительную программу Mirek’s Cellebration с сайта http://www.mirekw.com/ — в ней вы найдете примеры сотен (!!!) разнообразнейших клеточных автоматов, а также почитать книжку Т.Тоффоли, Н.Марголус. Машины клеточных автоматов. М.:Мир, 1991, она есть в интернете в формате Djvu, да и в библиотеке должна быть. Возникнут вопросы – пишите, отвечу всем!

Страница просмотрена 13194 раз(а)