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

Составим цепочку из квадратных клеток, пронумеруем их слева направо от 1 до n:

В этой цепочке у каждой клетки с номером i (кроме двух крайних, с номерами 1 и n) есть две соседних клетки - слева (с номером i-1) и справа (с номером i+1), назовем их окрестностью клетки:

Для того, чтобы и у крайних клеток была "правильная" окрестность, мысленно склеим цепочку в кольцо. При этом у клетки с номером 1 окрестность будет состоять из клеток с номерами n и 2, а у клетки с номером n окрестность будет состоять из клеток с номерами n-1 и 1.

Окрестность клетки 1

Окрестность клетки n

Введем понятие состояния клетки - целое число 0, 1, 2, 3, 4. Состояние клетки будем обозначать цветом по следующей шкале:

Для каждой клетки введем число s - сумму состояний клетки и ее окрестности. Рассмотрим пример:

• для клетки 3 s=2+0+4=6;

• для клетки 4 s=0+4+3=7;

• для клетки 2 s=1+2+0=3.

Очевидно, что диапазон s составит: 0 (все три клетки имеют состояние 0) ... 12 (все три клетки имеют состояние 4).

Для удобства будем значения s записывать в шестнадцатеричной системе. Тогда перечисление всех возможных значений s, записанное в порядке их возрастания будет цепочкой из 13 шестнадцатеричных цифр (от 0 до C):

Одномерный массив k1(n) применим для записи состояния всех клеток. Для каждой клетки вычислим значения s, просмотрев массив слева - направо.

Введем еще один массив k2(n) в который будем записывать новые состояния клеток в соответствии с состояниями их окрестностей по следующему правилу:

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

Рассмотрим пример клеточного автомата у которого все клетки кроме одной имеют состояние 0, а одна клетка имеет состояние 1. В этом случае в соответствии с правилом изменения состояния клеток на следующем такте мы получим следующую картину его жизненного цикла из 18 тактов:

Видно, что у этого клеточного автомата в соответствии с его правилом изменения состояния возможны только два состояния 0 и 1. Такой автомат называется бинарным. Так как у бинарного автомата значения s могут быть только 0, 1, 2, 3:

Для бинарного одномерного клеточного автомата правило можно записывать в следующей форме:

Так как в нижней строке таблицы правила могут стоять только 0 и 1, всего возможно 2⁴=16 правил:

0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111

Легко видеть, что это двоичная запись шестнадцатеричных цифр от 0000₂=0₁₆ до 1111₂=F₁₆ . Поэтому удобно записывать правило в виде соответствующей шестнадцатеричной цифры. Так, в нашем примере это правило 6, так как 0110₂=6₁₆.

Если отбросить тривиальные случаи правил 0₁₆ и F₁₆ (очевидно, что при этом никакого развития жизненные циклы таких клеточных автоматов не будут иметь место), остальные правила от 1₁₆ до E₁₆ могут быть последовательно исследованы. Некоторые интересные результаты приведены ниже:

Вполне очевидно, что вручную исследовать жизненные циклы одномерного клеточного автомата весьма затруднительно. Поэтому я написал на языке Visual Basic специальную программу. С ее помощью можно исследовать одномерные клеточные автоматы с состояниями 0...4 задавая различные правила (закон КА) в виде соответствующей строки. Программа работает с массивами размером до 499 клеток, можно задавать различный масштаб изображения, количество тактов жизненного цикла от 499 до 4990, а также задавать начальную конфигурацию в виде одиночной клетки или псевдослучайной последовательности состояний клеток с номерами от 1 до 499. Ниже показано окно программы с примером клеточного автомата с 5 состояниями:

Зададимся вопросом: сколько возможно одномерных клеточных автоматов с 5 состояниями? Очевидно, что это число сочетаний из 13 цифр каждая из которых может быть: 0, 1, 2, 3, 4.

5¹³=1 220 703 125

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

типичным являются следующие жизненные циклы:

• Развивающиеся регулярные структуры:

• Хаотические структуры:

• Периодические структуры:

• Особый интерес представляют бесконечно развивающиеся структуры:

Исследование одномерных клеточных автоматов доставляет и чисто эстетическое удовольствие. Многие жизненные циклы просто красивы, вызывают у исследователя разные ассоциации. Вот, например, клеточный автомат "Новогодняя ёлка":

Еще несколько примеров:

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

Дальнейшим развитием клеточного автомата является так называемый обратимый клеточный автомат. В нем новое состояние клеток зависит от значений s на двух смежных тактах:

s=(s₁+s₂) mod sos, где:

s₁ - сумма состояний клетки и ее окрестности на такте i-2

s₂ - сумма состояний клетки и ее окрестности на такте i-1

sos - число состояний клетки.

новое состояние на такте i рассчитывается аналогично предыдущему клеточному автомату по таблице правила.

В обратимом клеточном автомате используются три массива: k1(499), k2(499) и k3(499) для хранения состояний клеток на тактах i-2, i-1, i.

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

Универсальный одномерный клеточный автомат

Далее мною была создана программа, которая объединяет необратимый и обратимый клеточные автоматы - универсальный одномерный клеточный автомат. В нем можно не только включать и выключать его обратимость (команда меню Обратимость КА), но и для обратимого КА менять способ сочетания состояния окрестностей на i-2 и i-1 тактах:

Кроме сложения можно выбрать вычитание состояний окрестностей на двух предыдущих тактах: s=Abs(s₁-s₂) mod sos, а также:

• умножение: s=(s₁*s₂) mod sos

• приоритет max - учитывается большее состояние из s₁ и s₂

• приоритет min - учитывается меньшее состояние из s₁ и s₂.

Примеры структур, образованных в универсальном одномерном клеточном автомате:

Еще одна интересная конфигурация  - обратимый КА с приоритетом max и законом КА 004302144202:

 

и ее увеличенный фрагмент:

 

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

В следующей версии программы "Одномерный универсальный клеточный автомат включена система вывода на отдельных небольших экранах 30 изображений клеточных автоматов в режиме "Автомат" для последующего более детального исследования интересных конфигураций (законы КА выводятся на отдельной панели):

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

Исследование супрамолекулярных структур в настоящее время производится по нескольким направлениям:

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

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

• компьютерное моделирование супрамолекулярных структур с трехмерной визуализацией их динамики; цель - дальнейшее конструирование таких структур.

Слайд из лекции академика А.И.Коновалова "Супрамолекулярные системы - мост между неживой и живой материей", прочитанной и обсужденной на научном коллоквиуме кафедры неорганической химии химического факультета МГУ.

Ученые, занимающиеся в этом научном направлении, приходят к выводу, что образование супрамолекулярных структур так же неизбежно, как образование элементарных частиц, а из них химических элементов на определенных этапах эволюции вселенной. А, следовательно, жизнь, как дальнейшая эволюция супрамолекулярных структур, так же неизбежный этап всеобщей эволюции нашего мира. А, учитывая современные представления о масштабах вселенной, в которой насчитывается миллиарды галактик с сотнями миллиардов звезд в каждой и открытие планет, подобных Земле, у ближайших к нам звездных систем, окончательно уходят в прошлое наивные представления об исключительности жизни и разума. Скорее всего, жизнь возникает всякий раз, как только создаются для этого подходящие условия, то есть, даже только в нашей галактике, вероятно наличие огромного числа планет с жизнью на них (и, не исключено, и существование разумных существ, как определенного этапа развития живых существ, как это произошло на Земле).

 

 

 

 

 

 

 

 

 

Сайт создан в системе uCoz