Основные понятия теории клеточных автоматов

1. Основные понятия теории клеточных автоматов

Клеточный автомат (КА) представляет собой набор конечного числа элементов (клеток или ячеек), образующих регулярную структуру (сетку). Каждая клетка КА может находиться в одном из конечного числа состояний, например, «0» или «1». Сетка также имеет конечное число измерений. Для каждой клетки вводится понятие окрестности, т. е. клеток, располагающихся не более чем на заданном расстоянии от нее. Например, для одномерного клеточного автомата окрестностью клетки могут быть клетки , отстоящие от на 1 (см. рис. 1.1)

…

…

Рисунок 1.1 — Окрестность клетки в одномерном КА

Состояние КА изменяется во времени дискретно. Состояние всех клеток КА в каждый момент времени (на каждом шаге вычислений) называется конфигурацией КА. Пусть в момент времени t = 0 задана некоторая начальная конфигурация КА. На следующем шаге (t = 1) состояние каждой клетки преобразуется по заданными правилам, в зависимости от состояния самой клетки и ее окрестности. Правила эти одинаковы для всех клеток КА. Процесс изменения конфигураций КА в соответствии с правилами называется эволюцией КА.

Правила КА могут задаваться таблично, в виде математических функций (рис. 1.2) или словесно.

Рисунок 1.2 — Функциональная запись правил одномерного КА

Рассмотрим работу одномерного клеточного автомата, который можно представить в виде ленты из клеток (рис. 1). Каждая клетка может находиться в одном из двух состояний: быть активной (1) или пассивной (0).

Пример правил подобного КА приведен в табл. 1.1. Под окрестностью клетки понимается она сама и ее соседи справа и слева. Первое из восьми правил табл. 1 можно сформулировать так: если все клетки окрестности активны, то на следующем шаге центральная клетка пассивна.

Таблица 1.1 — Пример периодических правил для одномерного КА

Текущее состояние окрестности	111	110	101	100	011	010	001	000
Состояние центральной клетки на следующем шаге	0	1	0	1	1	0	1	0

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

Рисунок 1.3 — Эволюция КА, управляемого правилами из табл. 1

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

Таблица 1.2 — Пример правил, приводящих к хаотической эволюции КА

Текущее состояние окрестности	111	110	101	100	011	010	001	000
Состояние центральной клетки на следующем шаге	0	0	0	1	1	1	1	0

Рисунок 1.4 — Хаотическая эволюция одномерного КА по правилам из табл. 2

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

1.1 История

Идея клеточных автоматов была сформулирована независимо Джоном фон Нейманом (США) и Конрадом Цузе (Германия) в конце 40-х годов XX века [2]. Фон Нейман рассматривал КА как модель самовоспроизводящегося устройства. Предложенный им КА подтверждал мысль о том, что человек может создать устройство, обладающее способностью воспроизводить себе подобного. Долгое время КА рассматривался как модели самовоспроизведения, и толковались как упрощенные модели некоторого биологического сообщества, состоящего из множества клеток.

Книга «Вычислительное пространство» (нем. Rechnender Raum), изданная Цузе в 1969 г., и вскоре переведенная сотрудниками Массачусетского технологического института на английский, оказала сильное влияние на становление теоретического направления, известного как цифровая физика.

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

Так или иначе, и фон Нейман и Цузе рассматривали КА как универсальную вычислительную среду для построения алгоритмов.

Первое время КА оставались объектом для математических и компьютерных экспериментов, своеобразной «игрушкой». Самой известной из таких «игрушек» до сих пор является игра «Жизнь», предложенная в 1970-х годах британским математиком Джоном Конуэем. Конуэй, вслед за фон Нейманом, заинтересовался проблемой создания гипотетической машины, которая может воспроизводить сама себя, и попытался упростить правила, предложенные фон Нейманом. В результате ему удалось создать правила, известные теперь как правила игры «Жизнь».

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

- пустая (мёртвая) клетка рядом с тремя живыми клетками-соседями оживает;

- если у живой клетки есть две или три живые соседки, то эта клетка продолжает жить; в противном случае (если соседей меньше двух или больше трёх) клетка умирает (от «одиночества» или от «перенаселённости»).

Игрок не принимает прямого участия в игре, а лишь расставляет «живые» клетки, которые взаимодействуют согласно правилам уже без его участия. Его задача в состоит в том, чтобы найти такую начальную конфигурацию, при которой КА, эволюционировал бы желаемым образом. Все попытки решить эту задачу формально успехом не увенчались [4].

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

t = 0 шагов	t = 10 шагов	t = 50 шагов
t = 127 шагов

Рисунок 1.5 — Эволюция конфигурации из пяти точек в игре «Жизнь»

Когда в 70-ые годы прошлого века начала бурно развиваться микроэлектроника и появилась потребность в быстродействующих электронных схемах на многих элементарных автоматах, действующих параллельно, то КА приобрел важный практический смысл. Заложенные в его идее принципы параллельности и близкодействия межклеточных взаимодействий как нельзя лучше соответствуют требованиям технологии больших интегральных схем [4]. Аппаратурная реализация КА помогала решить сразу две насущные проблемы: сокращение связей на кристалле и увеличение производительности. Это пробудило новую волну интереса и сильно продвинуло теорию КА.

До сих пор развитие электроники идет по пути уменьшения размеров электронных элементов (чем меньше размеры, тем быстрее проходят сигналы между элементами компьютера). Понятно, что если эта тенденция сохранится и элементы станут сравнимы с размерами отдельных молекул, то сами элементы и соединения между ними должны стать предельно простыми. Например, такими, как в игре «Жизнь», где связаны только ближайшие соседи, а каждая клетка может находиться только в двух состояниях [5].

Это не только аналогия. Можно рассмотреть все основные компоненты современной ЭВМ — блоки памяти, логические устройства и прочее — и показать, что все они могут быть с помощью определенных конфигураций смоделированы в игре «Жизнь» [6]. Задавая различные начальные конфигурации, можно создавать самые разные компьютеры. В этой среде могут существовать все типы упорядоченности, которые можно моделировать с помощью ЭВМ.

В 2002 г. Пол Чепмен построил образец «Жизни», который эквивалентен машине Тьюринга. Таким образом, в игре «Жизнь» можно выполнить любой алгоритм, который можно реализовать на современном компьютере [7].

КА образуют общую парадигму параллельных вычислений, подобно тому, как это делают машины Тьюринга для последовательных вычислений [2]. Структура КА идеально пригодна для реализации на ЭВМ, обладающей высокой степенью параллелизма, локальными и единообразными взаимосвязями; подходящая архитектура позволяет при моделировании клеточных автоматов за сравнимую цену достигнуть эффективности по меньшей мере на несколько порядков выше, чем для обычного («последовательного») компьютера. Любопытно, что для различения подобных параллельных компьютеров и более привычных последовательных компьютеров используется термин "не-фон-неймановская архитектура", хотя теория КА разрабатывалась самим фон Нейманом примерно в то же время, когда он работал над конструированием универсальных электронных компьютеров.

Подводя итоги, выделим основные свойства классической модели КА.

• Локальность правил. На новое состояние клетки могут влиять только элементы её окрестности и, возможно, она сама.

• Однородность системы. Ни одна область сетки не может быть отличена от другой по каким-либо особенностям правил и т. п. Поскольку сетка всегда является конечным множеством клеток (ведь не возможно выделить неограниченный объём данных), в ней могут иметь место краевые эффекты: клетки стоящие на границе решётки будут отличны от остальных по числу соседей. Во избежание этого можно ввести периодические краевые условия.

• Множество возможных состояний клетки конечно. Это условие необходимо, чтобы для получения нового состояния клетки требовалось конечное число операций.

• Значения во всех клетках меняются единовременно, в конце итерации, а не по мере вычисления. В противном случае порядок перебора клеток решётки, при совершении итерации, существенно влиял бы на результат [7].

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

1.2 Клеточные автоматы как инструмент физического моделирования

Новый всплеск интереса к КА произошел в середине 80-х годов прошлого века, когда были предложены КА, эволюция которых моделирует процессы разделения фаз, химические реакции и диффузию. Но настоящим потрясением основ в моделировании (по выражению из [4]) стало появление клеточно-автоматной модели газовой динамики, названной «Gas-Lattice» («решеточный газ»). Очень важен тот факт, что было строго математически доказано соответствие Gas-Lattice-моделей уравнению Навье-Стокса [8]. В настоящее время эти модели успешно используются при моделировании потоков в пориcтых средах. Идея «решеточного газа» легла в основу более совершенной модели, так называемой «Gas-Lattice-Boltzmann» («решеточный газ Больцмана») [9], с помощью которой можно моделировать в том числе и турбулентные потоки, и которая активно для этого используется.

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

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

В сравнении с численными методами решения дифференциальных уравнений КА имеют свои достоинства и недостатки. К основным достоинствам КА-моделей относятся [4]:

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

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

Для классических КА-моделей, т. е. таких, в которых состояния клеток описываются только булевыми переменными, можно выделить также:

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

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

Главными из недостатков клеточно-автоматных алгоритмов являются:

1. Отсутствие формальных методов «предсказания» поведения КА, по заданным правилам перехода.

2. Отсутствие методов синтеза правил перехода КА по заданным свойствам его эволюции.

Литература

1. Wolfram S. A new kind of science. — Wolfram Media Inc., Champaign, Ill., USA. — 2002. — 1280 p.

2. ашины клеточных автоматов. — М.: Мир, 1990. — 278 с.

3. Википедия: Цифровая физика (http://ru. wikipedia. org/wiki/Цифровая_физика)

4. Бандман -автоматные модели пространственной динамики // Системная информатика. — Вып. 10. — C. 57—113.

5. , , Самарский в нелинейных средах // Компьютеры и нелинейные явления: Информатика и современное естествознание. — М.: Наука, 1988. — C. 5—43.

6. Berlekamp Е. В., Conway J. Н., Guy R. К. Winning Ways for Your Mathematical Plays. N. Y.: AK Peters, 2001.

7. Википедия: Клеточный автомат (http://ru. wikipedia. org/wiki/Клеточный_автомат)

8. Frish U., Hasslacher B., Pomeau Y. Lattice-gas Automata for Navier-Stokes equation // Physical Review Letter. — Vol. 56, 1986. — P. 1505—1508.

9. Ilachinski A. Cellular automata: a discrete universe. — Singapore: World Scientific, 2001. — 840 p.

Приложение

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

clear all; clc;

nx=800; % должно делитьсЯ на 2

nt=400;

z = zeros(nt, nx);

C = z;

c = zeros(1,nx);

c(nx/2) = 1;

C(1,:) = c;

imh = image(cat(3,z, C,C));

set(imh, 'erasemode', 'none')

axis equal

axis tight

x = 2:nx-1;

for t=2:nt

C(t, x) = (c(x-1)==1 & c(x)==0 & c(x+1)==0) | ...

(c(x-1)==0 & c(x)==1 & c(x+1)==1) | ...

(c(x-1)==0 & c(x)==1 & c(x+1)==0) | ...

(c(x-1)==0 & c(x)==0 & c(x+1)==1); % chaos

%  C(t, x) = (c(x-1)==1 & c(x)==1 & c(x+1)==0) | ...

%  (c(x-1)==1 & c(x)==0 & c(x+1)==0) | ...

%  (c(x-1)==0 & c(x)==1 & c(x+1)==1) | ...

%  (c(x-1)==0 & c(x)==0 & c(x+1)==1); % sierpinsky

  set(imh, 'cdata', cat(3,z, C,C) )

  drawnow

  c = C(t,:);

end

% Игра «Жизнь» Джона Конуэя

clear all; clc

%=============================================

% Рисуем GUI

% кнопка запуска (Run)

plotbutton=uicontrol('style','pushbutton',...

  'string','Run', ...

  'fontsize',12, ...

  'position',[30,280,60,30], ...

  'callback', 'run=1;');

% пауза (Stop)

erasebutton=uicontrol('style','pushbutton',...

  'string','Stop', ...

  'fontsize',12, ...

  'position',[30,230,60,30], ...

  'callback','freeze=1;');

% выход из программы (Quit)

quitbutton=uicontrol('style','pushbutton',...

  'string','Quit', ...

  'fontsize',12, ...

  'position',[30,180,60,30], ...

  'callback','stop=1;close;');

number = uicontrol('style','text', ...

  'string','1', ...

  'fontsize',12, ...

  'position',[30,350,60,25]);

%=============================================

n = 64; % размеры КА

% создадим массивы

z = zeros(n, n);

c = z; % клетки КА

sum = z;  % длЯ хранениЯ суммы живых клеток окрестности

% случайнаЯ начальнаЯ конфигурациЯ

%c = (rand(n, n))<.5 ;

% резонансное возбуждение

c(n/2-1:n/2+1,n/2) = 1;

c(n/2-1,n/2+1) = 1;

c(n/2,n/2-1) = 1;

% создадим картинку и нарисуем ее

imh = image(cat(3,c, c,z));

set(imh, 'erasemode', 'none') % рисование без морганий

axis equal

axis tight

% внутренние точки КА

x = 2:n-1;

y = 2:n-1;

% Основной цикл

stop= 0; % ждать, пока не нажато Quit

run = 0; % ожидать Run

freeze = 0; % ожидать Stop

ptime = 0.5; % времЯ задержки

while (stop==0)

  if (run==1)

  % сумма живых клеток в окрестности данной

  sum(x, y) = c(x, y-1) + c(x, y+1) + ...

  c(x-1, y) + c(x+1,y) + ...

  c(x-1,y-1) + c(x-1,y+1) + ...

  c(3:n, y-1) + c(x+1,y+1);

  % а вот и правила игры

  c = (sum==3) | (sum==2 & c);

  % рисуем картинку

  set(imh, 'cdata', cat(3,c, c,z) )

  pause(ptime) % задержка, если хотим рассмотреть подробности

  % обновим счетчик шагов и покажем его значение на экране

  stepnumber = 1 + str2num(get(number,'string'));

  set(number,'string',num2str(stepnumber))

  end

  if (freeze==1)

  run = 0;

  freeze = 0;

  end

  drawnow  % нужно чтобы рисовалось немедленно

end