Модель клеточного автомата онлайн

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

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

Правила клеточного автомата определяют что поместить в отдельно взятую клетку в следующий момент времени. Состояние клетки в следующий момент времени определяется состоянием соседних клеток к данной.

Так правило 90 по классификации Вольфрама звучит так: если соседние (справа и слева) клетки к данной одинаковые (все содержат нули или все единицы), то в клетку помещаем ноль, в противном случае (ноль справа, единица слева или наоборот) помещаем единицу.

Обратите внимание

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

Если рисовать строчки друг под другом и кодировать синим цветом единицы, а белым нули, временная эволюция такого клеточного автомата будет выглядеть как:

Мы получили фрактал — треугольник Серпинского. Это общая идея всех клеточных автоматов:

Простые правила приводят к сложной, часто непредсказуемой эволюции.

Рассмотрим, например, клеточный автомат Муравей Лэнгтона в котором «муравей» движется по двумерной дискретной поверхности согласно правилам:

  • Если в клетке единица — записать в нее ноль, повернуться на 90° влево, сделать шаг вперед на следующую клетку.
  • Если в клетке ноль —  записать в нее единицу, повернуться на 90° вправо, сделать шаг вперед на следующую клетку.

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

Клеточными автоматами можно моделировать различные физические процессы. Возьмем модель DLA (Diffusion-limited aggregation), имитирующая рост кристаллов, снежинок и т.п. Правила данного клеточного автомата также очень просты:

  • Частица генерируется в случайной клетке поверхности.
  • Частица совершает броуновское движение до тех пор пока в одной из соседних клеток не окажется другая частица.
  • Частица закрепляется в данной клетке и процесс повторяется с первого шага.

Что получается при исходной конфигурации в виде одной частицы в центре показано на видео:

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

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

При случайном начальном заполнении получаем что-то вроде этого:

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

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

  Знаменитый математик Джон фон Нейман решил данную задачу предложив клеточный автомат, способный создать собственную копию.

Клеточный автомат получился довольно сложный: 29 допустимых состояний клетки вместо двух (единица и ноль) нами до сих пор рассматриваемых и множество правил.

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

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

Важно

Заметьте, внутри кольца находится «ДНК», кодирующая действия автомата. То есть клеточные автоматы несмотря на свою простоту могут выполнять инструкции. Их можно программировать на определенные действия. Вот еще один, более сложный, репликатор:

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

  • Пустая клетка → Пустая клетка;
  • Голова электрона → Хвост электрона;
  • Хвост электрона → Проводник;
  • Проводник → Голова электрона при условии, что на соседних клетках есть ровно 1 или 2 головы электронов, иначе остаются проводниками.

Реализация двух тактовых генераторов  и вентиля XOR выглядит так:

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

Такой компьютер конечно будет по архитектуре совершенно не похож на современные, основанные на полупроводниковых транзисторах. Вот одна из таких попыток — клеточный автомат на квантовых точках:

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

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

Приведенная ниже конфигурация представляет собой инвертор, то есть операцию NOT:

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

Источник: http://LightCone.ru/cellular-automaton/

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

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

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

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

Совет

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

Классической системой с мелкозернистым параллелизмом является клеточный автомат, а игра Джона Конвея «Жизнь» — типичный пример клеточного автомата, представляющего собой дискретную динамическую систему. Клеточные автоматы фактически являются синтетическими мирами, поведение которых определяется простыми локально действующими правилами.

В этих мирах пространство представляет собой равномерную сетку, каждая ячейка которой (клетка) содержит информацию о своем состоянии.

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

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

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

В физике, например, клеточные автоматы применяются для анализа явлений переноса (теплопроводности, диффузии и вязкости) и моделирования твердого тела.

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

Обратите внимание

Жизнь, как естественный процесс — явление настолько сложное и увлекательное, что тысячи ученых пытались раскрыть ее тайны.

Свой вклад в решение этой проблемы внес и человек, не имевший к биологии никакого отношения, английский математик Джон Хортон Конвей.

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

Действие игры происходит на плоскости, разделенной на клетки. Каждая клетка окружена 8 такими же клетками (так называемая окрестность Мура) и может находиться в двух состояниях — живом или мертвом (быть пустой).

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

Во времени эти состояния дискретно изменяются в соответствии со следующими правилами (генетическими законами Конвея).

  1. Выживание или гибель. Если живая клетка имеет менее 2 или более 3 соседей в окрестности из 8 клеток, то в следующем поколении она умирает (моделирование реальных условий — недостатка питания или перенаселенности), в противном случае она выживает.
  2. Рождение. В пустой клетке появляется новая живая клетка, если у нее ровно 3 соседа.

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

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

Познать «Жизнь» на практике проще всего с помощью листа бумаги в клеточку и ручки. Можно воспользоваться также шахматной доской и обычными шашками двух цветов. Еще проще — использовать для этой цели компьютер. Уже на заре развития компьютерной техники были написаны многочисленные программы, моделирующие «Жизнь».

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

Важно

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

Более подробную информацию о игре «Жизнь» и программы для наблюдения за эволюцией объектов можно найти по следующему URL: elvisti.kiev.ua/skl/conwey1/w_life_n.htm.

Как уже было сказано, игра «Жизнь»описывается с помощью теории автоматов. На основе этого примера можно сформулировать общие правила построения клеточных автоматов.

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

Представим себе некую исходную фигуру на плоскости, к которой начинают применяться правила «Жизни».

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

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

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

Задания

1. Постройте модель процесса распространения инфекции стригущего лишая по участку кожи размером n x n (n-нечетное) клеток. Заражение начинается с центральной клетки.

В каждый интервал времени пораженная инфекцией клетка может с вероятностью 1/2 заразить любую из соседних здоровых клеток. Через шесть единиц времени зараженная клетка становится невосприимчивой к инфекции.

Возникший иммунитет действует в течение последующих четырех единиц времени, а затем клетка выздоравливает.

Совет

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

Читайте также:  Ученые создали робота-бактерию

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

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

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

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

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

Источник: http://www.linuxcookbook.ru/books/informatika1/ch_09_modell/01_model/02_life/index.html

Клеточный автомат: возможна ли автоматическая жизнь?

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

Правила «Жизни»

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

Если у мертвой клетки три живых соседа, она становится живой. Учитывается соседство по вертикали, горизонтали и диагонали.

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

Типичные структуры, возникающие в «Жизни» Конвея. Если игра начинается со случайной конфигурации, скорее всего, она закончится появлением устойчивого набора таких живучих форм.

Обратите внимание

Но в общем случае эволюция системы непредсказуема, и чтобы выяснить, чем закончится такая «Жизнь», нужно ее «прожить», то есть смоделировать

Правила «Жизни» были опубликованы кембриджским математиком Джоном Конвеем в 1970 году и сразу сделали клеточные автоматы невероятно популярными.

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

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

Планер (глайдер) — перемещающаяся конфигурация из пяти клеток

Сегодня в «Жизни» известны миллионы таких существ: с ростом «размеров», то есть числа ячеек, количество возможных «натюрмортов» и «осцилляторов» увеличивается стремительно.

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

Например, «крепкий орешек» состоит из семи живых клеток, которые мучительно выживают на протяжении 130 поколений, после чего все разом аннигилируют.

Автомат становится машиной

Сам Конвей предполагал, что такая смертная судьба ждет любую нестационарную и непериодическую форму «Жизни», и даже объявил символическую премию тому, кто сможет доказать или опровергнуть идею о том, что на этом клетчатом поле возможно бесконечное размножение.

Однако с обещанной суммой в $50 ему пришлось расстаться довольно быстро. В том же 1970 году Билл Госпер обнаружил периодическую структуру — «ружье», которое каждые 30 шагов возвращается к исходной конфигурации, рождая улетающий в сторону «планер».

А вот это уже очень и очень любопытно…

Важно

Подобные «планерные ружья» можно рассматривать как генераторы импульсов, которыми обмениваются логические элементы любой вычислительной машины: ушел планер — единица, планера нет — ноль.

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

Остается их скомбинировать — и игра станет вычислительным устройством.

«Планерное ружье» — основа многих комбинаций, которые воплощают логические элементы вычислительной машины. Такие крупные конфигурации автомата Конвея по большей части состоят из пустых клеток. По этому поводу математик Пол Чэпмен заметил: «Возможно, в „Жизни» так много пустого пространства по той же причине, по которой его так много и в нашей жизни. Атомы должны иметь достаточно места для того, чтобы делать свою работу»

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

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

Бесконечное рождение

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

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

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

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

Совет

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

Зато соседями — окрестностью каждой ячейки — в автомате фон Неймана считаются лишь те четыре, что расположены по вертикали и горизонтали от нее, тогда как у Конвея учитываются целых восемь ячеек, в том числе и находящиеся по диагонали от исходной (окрестность Мура).

«Сады Эдема» — один из вариантов конфигурации клеточного автомата, которые не могут появиться в результате эволюции и должны быть заданы с самого начала, с «сотворения» этого искусственного мирка

Локальная зависимость поведения ячеек — такое же базовое свойство клеточных автоматов, как и глобальность правил, которые действуют совершенно одинаково в любой точке сетки. Это напоминает реальный мир: насколько нам известно, законы физики одинаковы в любой его точке, а вот взаимодействия распространяются с конечной скоростью, максимально — световой.

В мире клеточных автоматов этот предел скорости еще заметнее. Любые изменения в «Жизни» в принципе не могут происходить быстрее скорости шахматного короля — на одну клетку за один интервал времени.

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

https://www.youtube.com/watch?v=GsNA0edVtUc

Хищники и жертвы

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

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

Например: течение увлекает молекулу вниз, пока она не встретит препятствие — стол или другую молекулу — в этом случае она перемещается в случайную незанятую ячейку сбоку. Мы получим нехитрый клеточный автомат, который способен с приемлемой точностью имитировать реальность.

Обратите внимание

Схожие правила позволяют моделировать поведение толпы. Если есть возможность, человек движется вперед; встретив препятствие, повернет в сторону; если по сторонам стоят другие люди, останется на месте.

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

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

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

С определенной периодичностью она оставляет в исходной клетке потомка, с определенной — сама умирает от старости. Хищная особь может проглотить соседнее травоядное, а если не сделает этого в течение некоторого времени, то погибнет от голода.

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

Клетчатый мир

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

Эти идеи максимально развиты у Конрада Цузе, а позднее — у Эдварда Фредкина, сформулировавшего свою «конечную гипотезу»: «Всякая физическая величина, включая время и пространство, является конечной и дискретной».

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

Отсюда остается сделать последний шаг.

Важно

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

Эволюцию одномерного клеточного автомата можно представить на плоскости, одним из измерений которой будет время. Один из таких автоматов создает фрактальную структуру «салфетки Серпинского»

Матрица «шахматной доски» Конвея превращается в глобальную матрицу нашего мира — динамичную и завораживающую.

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

«Монитор вашего компьютера, изображение на котором состоит из точек-пикселей, доказывает, что такой мир может выглядеть вполне реалистично, — пишет нобелевский лауреат Фрэнк Вильчек. — Но в нем обязательно что-то будет немного не так».

Роман Фишман
«Популярная механика» №3, 2016

P.S.

Предложенный Конвеем свод правил, или ЗАКОН, — лишь один из многих возможных. При данных начальных условиях существует «два в степени два в степени девять» т.е. около 10154 различных «жизнеподобных» законов, из которых, похоже, только ОДИН, установленный Конвеем, оказался жизнеспособен.

М. Шредер «Фракталы, хаос, степенные законы»

P.P.S.

Очень простые правила образуют очень сложные структуры, примеры которых в динамике на видео. Может кому-то что-то они напоминают?

Источник: http://universe-tss.su/main/nepoz/41643-kletochnyy-avtomat-v…

Источник: https://cosmos.mirtesen.ru/blog/43215608104

Клеточные автоматы в криптографии. Часть 2

Пожалуй, нет такого раздела математики, который не применяли или хотя бы не пытались применить в криптографических исследованиях. Не осталась в стороне и теория клеточных автоматов. После первого приложения теории КлА к криптографии [Wol85] и последовавшей в период середины 80-х – начала 90-х гг.

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

Алексей ЖуковПредседатель совета директоров ассоциации

“РусКрипто», к.ф.-м.н., доцент, МГТУ им. Н.Э. Баумана

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

Однако в последнее время вновь наблюдается рост интереса криптографического сообщества к использованию в криптографии клеточно-автоматных моделей. Количество работ, посвященных приложению КлА к криптографии, за последние годы вновь резко выросло. Все это объясняется самой природой КлА и прежде всего свойствами параллельности и локальности.

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

Совет

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

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

Гпсп на основе классических клеточных автоматов

Первые исследования в области клеточных автоматов, их свойств и возможностей их применения как генераторов псевдослучайных последовательностей (ГПСП) принадлежат С. Вольфраму и относятся к одномерным клеточным автоматам [Wol85]. Вольфрамом и рядом других авторов была рассмотрена возможность применения подобных одномерных КлА в качестве генераторов гаммы поточного шифрования.

Гпсп на основе одномерных клеточных автоматов

Рассмотрим предложенный Вольфрамом ГПСП подробнее. Одномерный клеточный автомат представляет собой массив из N циклически соединенных ячеек памяти s=[m0, m1,…,mn-1], каждая из которых может принимать значения из множества Ω={0,1}.

В процессе функционирования КлА все ячейки меняют свои значение синхронно и одновременно. Значение i-й ячейки на t-м такте работы будем обозначать mi(t).

Тогда значение i-й ячейки на (?+1)-м такте работы определяется локальной функцией связи

где вычисление индексов осуществляются по модулю N (т.к. массив ячеек памяти «закольцован»). Вектором инициализации генератора является набор s(0) = [m0(0), m1(0),…,mn-1(0)], образованный начальным заполнением ячеек памяти.

Для формирования выходной последовательности {y(t)} генератора используется съем с одной зафиксированной ячейки: y(t) = mk(t),t = 1,2… .

Таким образом, генератор вырабатывает выходную последовательность со скоростью 1 бит за 1 такт работы.

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

Обратите внимание

Через некоторое время Мейер (Meier W.) и Стаффельбах (Staffel-bach O.) представили атаку на этот шифр [Mei91]. Для значений N

Читайте также:  Искусственный интеллект научился распознавать человека даже среди других сложных предметов

Источник: http://itsec.ru/articles2/crypto/kletochnye-avtomaty-v-kriptografii-chast-2

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

?evan_gcrm (evan_gcrm) wrote,
2017-06-15 00:18:00evan_gcrm
evan_gcrm
2017-06-15 00:18:00Categories:

  • наука
  • it
  • технологии

Оригинал взят у lexpartizan

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

И по которым они изменяются с каждым циклом.

Например, у нас есть громадное поле клеток и несколько простых правил:

1. В пустой (мёртвой) клетке, рядом с которой ровно три живые клетки, зарождается жизнь;

2. Если у живой клетки есть две или три живые соседки, то эта клетка продолжает жить;
3. В противном случае, если соседей меньше двух или больше трёх, клетка умирает («от одиночества» или «от перенаселённости»).Эти правила придумал математик Джон Конвей в 1970 году и назвал их игрой «жизнь». Это наиболее известный пример клеточного автомата. Дело в том, что несмотря на простейшие правила, лежащие в основе, игра жизнь неожиданно смогла воспроизвести и поддерживать очень сложные структуры. Всего 2-3 правила, а там есть чрезвычайно сложное поведение некоторых структур. Есть стабильные фигуры, есть динамические фигуры (глайдеры, которые повторяют форму через несколько итераций, но смещаются), есть фигуры, порождающие эти глайдеры, есть фигуры, принимающие глайдеры и порождающие столько же глайдеров, сколько приняли. Есть много чего. Настолько много, что в этой игре удалось реализовать «машину Тьюринга».

Поль Рендель 2 апреля 2000 года создал модель машины Тьюринга с помощью клеточного автомата Джона Хортона Конвея, а 10 февраля 2010 года повторил свой замечательный опыт. В первой модели использовалась решетка 1714 х 1647, с помощью конечных автоматов которой была создана машина Тьюринга.

Она имела три возможных состояния и могла обрабатывать на ленте памяти три разных символа. В эксперименте 2010 года была создана модель универсальной машины Тьюринга.

Существуют и другие успешные примеры создания машин Тьюринга с помощью игры «Жизнь», некоторые из них даже получили собственные названия: MRM (Minsky Register Machine) или ее универсальная версия URM, а также CoreWorld, LogiCell и другие.

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

Жители виртуальной Вселенной игры «Жизнь» могли бы создать собственную виртуальную реальность! В которой могли бы изменить правила и клетки бы не умирали))Конечно, правила для игры «жизнь» могут быть и другими и это будет уже другой клеточный автомат.

Как задать правила? Да теми же таблицами!

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

Сколько значений надо заполнить?

2 в 9 степени = 512. 3Х3 клетки могут принять 512 значений и каждому из этих значений нужно поставить результат. То есть какой цвет примет клетка для каждого значения. А вот комбинаций таких результатов уже будет 2 в степени 512. В общем, больше атомов во Вселенной. И у каждого будет своё поведение (не факт, что интересное). И это только для одного плоского клеточного автомата 3Х3.А ведь можно взять другую окрестность точек, например, не 8 точек вокруг, а 4 точки по каждой стороне, проигнорировав диагональные. Или считать не только ближайшие точки, но и точки за ними, то есть не квадрат 3Х3, а квадрат 5Х5. Или ввести третье измерение. А ещё можно для этих правил ввести вероятность, сделав их вероятностными, когда клетка имеет шанс жить вопреки. Или двигаться в случайную сторону. Например, это имеет место для модели диффузии.Простой клеточный автомат с правилами (движемся хаотично, при столкновении меняемся местами) даёт вполне себе реалистичную картину диффузии.Чуть хитрее поведение газов. Ещё хитрее — поведение жидкости в полном соответствии с системой дифференциальных уравнений Навье-Стокса, которые довольно трудно считаются в лоб, легко симулируются практически с абсолютной точностью простым (но довольно большим по размеру) клеточным автоматом.Так что клеточные автоматы применяются в газо и гидродинамике. А также в оптике. По весьма схожим правилам.

А также в физике при моделировании столкновений элементарных частиц, в квантовой физике, даже в теории световых полей.

И ещё много где применяются.

При моделировании социальных процессов (вообще схожих с гидродинамикой). Например, распространение информации в соцсетях можно промоделировать.

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

Во-первых, для необратимых клеточных автоматов очень трудно подобрать предыдущее состояние. То есть эти состояния могут служить криптографическими ключами.

Во-вторых, если использовать правило 30
для простейшего одномерного клеточного автомата (состояние клетки определяется своим состоянием и двумя соседями), то мы получим такую картину:Сам автомат одномерный, просто результаты записывали в каждую новую строчку для удобства. Если в левой части мы ещё видим регулярные структуры, то в левой — практически белый шум. И это используется для генератора псевдослучайных чисел.Ну и раз уж мы упомянули правило 30 (его особенность в том, что простое правило даёт просто непредсказуемое сложное поведение), то у одного ядовитого моллюска секреция пигмента каждой клетки зависит от активирующей и ингибиторной активности соседних клеток.

То есть, практически представляет собой клеточный автомат.

В процессе роста раковины полоса клеток формирует цветной узор на её поверхности. Угадайте с трёх раз по какому правилу))Многие биологические процессы, популяции, генетики и тд тоже моделируются клеточными автоматами.

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

Однако многие учёные считали, да и сейчас считают, что мозг близок к клеточному автомату.

Ведь и правда, если представить каждую клетку, как нейрон…

Поэтому есть проекты, вроде Клеточных Нейронных Сетей, которые значительно проще в реализации.

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

Важно

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

Например, есть так называемые L-системы.

Где начальный набор постоянно переписывается в соответствии с некоторыми правилами и порождает фрактальные (это скучно, хотя снежинки же) и древовидные (а это интересно) структуры.

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

Сейчас L-системы применяются для процедурной генерации растений для 3D-пакетов и игр.

И для создания гипножаб:

Принцип один: Простые правила — сложное поведение.

Всё это не могло не натолкнуть учёных на мысль:

А что если вся наша Вселенная на самом деле работает по простым правилам?И в 1969 году немецкий инженер Конрад Цузе опубликовал книгу «Вычислимый космос», где выдвинул предположение, что физические законы дискретны по своей природе, и что вся Вселенная является гигантским клеточным автоматом.

Это была первая книга из области, называемой сейчас цифровой физикой.

Что если вся наша Вселенная — громадный клеточный автомат? И кажется такой сложной (ньютонова физика, противоречащие друг другу ОТО, СТО и квантовая физика), но на самом деле где-то глубоко внутри, подчиняется простейшим правилам.

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

Эту теорию продолжает развивать расовый жид Стивен Вольфрам, выпустивший книгу «New kind of science». Вольфрам нашел способ из графов и комбинаторики создавать такие сети, которые могли бы соответствовать нашему пространству-времени, гравитации и прочим законам. Это клеточный автомат, но не из цифр и не из клеток.

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

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

Для этого не существует математического аппарата. Некоторые можно подобрать логикой (как транспортные потоки, диффузию, поведение идеальных газов). Но некоторые являются результатом везения и перебора. Их поведение практически случайно совпадает с желаемым. Трудно вычислить правила.

Совет

Часто просто наблюдают за поведением при случайных правилах. А область правил просто невероятно огромна даже для модели игры «Жизнь»(область определения 3Х3 клетки, плоскость). Так что Вольфраму будет нелегко.

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

А теперь натянем сову на глобус.

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

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

Ведь матрица — основа клеточного автомата.

Картинка кликабельна.

Источник: https://evan-gcrm.livejournal.com/978425.html

Классификация моделей клеточных автоматов. Основные правила

ТРАНСПОРТ

УДК 519.6: 656.13: 537.8

А.Ю. Кретов, магистр,

8-953-428-62-70, alex yurich@mail.ru (Россия, Тула, ТулГУ)

КЛАССИФИКАЦИЯ МОДЕЛЕЙ КЛЕТОЧНЫХ АВТОМАТОВ. ОСНОВНЫЕ ПРАВИЛА

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

Ключевые слова: клеточный автомат, транспортный поток, затор, микроскопические модели.

Введение

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

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

Недостатком же оказалась относительно низкая точность в микроскопических масштабах. Причиной этого является то, что эти так называемые транспортные клеточные автоматы (TКA), являются динамическими системами, которые дискретны по своей природе — время представляет собой дискретную величину, а пространство разбито на клетки [1].

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

449

средствами, а скорость — в количестве клеток, на которое может переместиться автомобиль за одну итерацию.

Обратите внимание

Классификация КЛ правил. Рассматриваемое пространство КА представляет собой поле (матрицу) разбитое на клетки. При рассмотрении достаточно большого поля для получения траекторий движения транспортных средств может потребоваться множество или даже бесконечное число итераций.

Поэтому с целью повышения точности результатов размеры поля системы должны быть приняты бесконечно большими, но даже рассмотрение 1000 клеток двоичного элементарного клеточного автомата (ЭКА) приводит к увеличению размера рассматриваемого пространства до 21000 ~ 10300 конфигураций.

Стивен Вольфрам эмпирически изучил множество конфигураций бинарных правил ЭКА, рассматривая поле состоящее

23

из трех ячеек, что составило 2 = 256 различных правил. В 1984 году на

основе этого исследования Вольфрам выделил четыре различных класса КА [2]:

Класс I: Развитие происходит с конечным числом итераций до уникального однородного состояния, то есть до предельной точки.

Класс II: Генерируются регулярные, периодические узоры, переходящие в предельный цикл.

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

Класс IV: В этот класс входят все КА, которые развиваются по сложным траекториям. Такие автоматы имеют возможность универсальных вычислений.

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

Важно

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

Читайте также:  Искусственный интеллект с интуицией dms сможет оказать помощь людям

1) Кулик и Юи выделили формальные классы Вольфрама [4].

2) Ли и Паккард привели структуру пространства правил ЭКА в соответствие с некоторыми метрическими расстояниями, в результате чего появился пятый класс [5].

3) Брага и др. систематизировали модели на 3 класса, основанные на развитии узоров наблюдаемых в КА моделях [6].

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

4) Дубак и др. классифицировали КА модели по уровню их алгоритмической сложности путем измерения информационного наполнения местных саморегулирующихся переходов [8].

5) Фэйтс, используя макроскопические параметры, отделил хаотические правила ЭКА от нехаотических [9].

Все модели можно разделить на одноклеточные и многоклеточные. Одноклеточными называют автоматы, в которых транспортные средства занимают одну клетку пространства модели.

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

Совет

Одноклеточные модели КА. В данном типе КА ячейка может быть либо пустой, либо занятой ровно одним автомобилем. Все транспортные средства имеют одинаковую длину L{ = 1 клетке. Поток считается однородным, то есть характеристики всех транспортных средств приняты одинаковыми. Рассмотрим следующие модели ТКА:

1) Детерминированные модели:

правило Вольфрама 184 (СА-184);

детерминированные ТКА Фукуи-Итттибаши (DFI-TCA).

2) Стохастические модели:

ТКА Нагель-Шрекенберг (STCA);

СТКА с круиз-контролем (STCA-CC);

Стохастические ТКА Фукуи-Ишибаши (SFI-TCA);

ТКА Эммериха-Ранга (ER-TCA).

Для других обзоров ТКА моделей, рекомендуем обратиться к работам Чоудхури и соавт. [10], Кносп и соавт. [11], Нагель [12], Нагель и со-авт. [13], Шадшнайдер [14, 15].

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

В данной модели частицы, представляющие автомобили, перемещаются в одном направлении, останавливаясь и проезжая в зависимости от наличия машин рядом с ними. Число частиц остается неизменным на всем протяжении моделирования.

Из-за такого применения Правило 184 называется «Правилом трафика»

На каждом шаге автомат Правила 184 применяет к массиву ячеек определенный закон для определения нового состояния: 111- *11; 110 -*11; 101 — *10; 100 — *10; 011 — *01; 010 — *01; 001 — *00; 000 — *00, где 1 -клетка занятая автомобилем, 0 — свободная клетка, * — предыдущее состояние рассматриваемой клетки. При рассмотрении центральной ячейки пра-

451

вило может быть записано следующим образом:

Текущий шаблон 111 110 101 100 011 010 001 000

Новое состояние 1 0 1 1 1 0 0 0

Если интерпретировать каждую ячейку, содержащую единицу как частицу, эти частицы ведут себя во многом сходно с находящимися на одной полосе автомобилями: они перемещаются слева направо с постоянной скоростью, если перед ними существует открытое пространство (ноль в клетке справа) и останавливаются на один, если справа от него пространство отсутствует (единица в клетке справа). Несмотря на свою примитивность, Правило 184 демонстрирует некоторые типичные свойства реального потока: кластеры свободно движущихся автомобилей, разделенные открытыми участками дороги, когда поток разреженный, и волны “стоп-старт”, когда поток перегружен.

ТКА Фукуи-Ишибаши (DFI-TCA) [17]. В 1996 году Фукуи и Иши-баши разработали свое правило на основе КА-184 ТКА. Хотя их модель является и стохастической, мы сначала обсудим ее с точки зрения детерминированной.

Идея Фукуи и Ишибаши была двоякой: с одной стороны, максимальная скорость движения была увеличена с 1 до Vmax клеток/шаг по времени, с другой стороны, транспортные средства могут мгновенно ускоряться, чтобы двигаться с максимально возможной скоростью.

В соответствии с определениями правила набора ТКА модели, КА-184 по правилу 1 (Пр.1), изменяется следующим образом:

Пр.1, ускорения и торможения

VI<\p>

Источник: https://cyberleninka.ru/article/n/klassifikatsiya-modeley-kletochnyh-avtomatov-osnovnye-pravila

Простейшие клеточные автоматы и их практическое применение

Этот мир просто охренеть какой сложный, каждый день поражаюсь.

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

И знаете, что удивительно? Этот подход замечательно работает. Ну, почти всегда. По крайней мере, ничего лучше мы до сих пор не придумали.

Но вообще-то я не об этом. Я хочу рассказать об одной чрезвычайно интересной как с эстетической, так и с математической точки зрения категории этих самых моделей.

Обратите внимание

Да, я о клеточных автоматах, а именно — об их подмножестве, простейших клеточных автоматах (Elementary cellular automaton). В этой статье я поведаю, что это такое, какие они бывают, какими свойствами обладают, а также отвечу на главный, на мой взгляд, и совершенно правильный вопрос, который часто несправедливо игнорируется в подобных статьях. Звучит он так: А это всё вообще зачем?

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

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

Унылая теория

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

Примеры: «Жизнь» Конуэя, Автомат Фон Неймана, Wireworld, Модель сегрегации Шеллинга.Какие они бывают?В зависимости от размерности решетки: одно-, дву-, трёхмерные, и т.д.

Например, Правило 110 и другие, освещенные в этой статье, — одномерные, «Жизнь» — двумерная.

В зависимости от количества возможных состояний:
бинарные, троичные, и т.д.

В разных клеточных автоматах может по-разному определяться окрестность клетки, то есть, множество клеток, от которых будет зависеть состояние в следующий момент времени. Это может быть, например, окрестность Фон Неймана различных рангов или окрестность Мура.

КА бывают синхронные и асинхронные. В синхронных все клетки системы обновляются одновременно, в асинхронных — каждая делает это независимо.

Одна из самых важных классификаций — по типам поведения. Об этом я расскажу отдельно чуть ниже.

А что же тогда такое простейший клеточный автомат?

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

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

Для начала определимся с терминологией. Так как вариантов таких автоматов всего 256, тот самый Вольфрам (я часто буду на него ссылаться) не стал сильно заморачиваться и предложил называть их числами от 0 до 255. Это именование по причине своей лаконичности и удобства отлично прижилось, и с тех пор оно называется, вы не поверите, «Код Вольфрама».

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

Что означают коды ВольфрамаРассмотрим сразу на примере. Возьмём номер правила, например, 110.

1. 11010 = 011011102.

2. Впишем цифры двоичного представления числа в таблицу:

111 110 101 100 011 010 001 000
1 1 1 1 1

В зависимости от состояний соседа слева, самой клетки и соседа справа (первая строка таблицы) на следующем шаге клетка примет одно из состояний, указанных во второй строке.

Еще более наглядно это можно представить так:

Также Вольфрам предложил разделить клеточные автоматы на четыре класса по типу поведения:

1 класс: все клетки быстро принимают одинаковое состояние, которое становится стабильным. Например, Правило 40:

2 класс: состояние всех клеток быстро стабилизируется, либо возникают периодические колебания. Например, Правила 3 и 33:

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

4 класс: автомат порождает сложные, взаимодействующие между собой структуры, способные выживать длительное время, однако не достигает стабильности. Например, правило 193:

Пка в жизни

Правило 30

Иногда элементарные клеточные автоматы обнаруживаются в совершенно неожиданных местах.
Вот, например, посмотрите, какой милашка.

Только не обольщайтесь. Он вас не любит. Это — Текстильный конус, самый опасный для человека моллюск из семейства Конусы. Противоядия от его яда пока нет.

Рисунок на его раковине — не что иное как узор, порожденный «Правилом 30». По крайней мере, именно так считают в Ноттингемском университете.

Так выглядит развитие «Правила 30» из одной точки.

Важно

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

Однако, существует огромное множество начальных условий, при которых правило порождает повторяющиеся паттерны. Например, если в начальных условиях «жива» каждая 14-я клетка, в результате получается вот такой скандинавский свитер.

Правило 110

Одно из самых интересных правил. Вольфрам относит его к классу 4, но в зависимости от начальных условий оно может вести себя как представитель класса 1, 2, 3 или 4. Для сравнения, эволюция из одной точки:

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

А вот — эволюция из случайного начального состояния, заполненного живыми клетками на 50%.Тут также видны и периодические (что интересно, с разными периодами), и хаотические.

Не буду долго тянуть, в 2000 году Мэтью Кук доказал, что этот клеточный автомат является Тьюринг-полным, то есть, на его основе можно реализовать любую вычислимую функцию.

Фракталы

Есть целый ряд клеточных автоматов (правила 18, 22, 126, 161, 182, 218, etc.), которые, развиваясь из одной точки, порождают фрактальные изображения.

Например, рисунок правила 22 — это треугольник Паскаля по модулю 2 (эдакий дискретный аналог «Салфетки Серпинского»).

Связь салфетки Серпинского и треугольника Паскаля уже достойно освещалась на Хабре три года назад. А выглядит всё это счастье так:

Правило 161 порождает инвертированный вариант того же самого фрактала.

Кстати, забыл упомянуть один важный момент, касающийся реализации автоматов.

Иначе вместо вполне ожидаемого полностью закрашенного прямоугольника (эволюция правила 161 с начальным состоянием, полностью состоящим из живых клеток) можно увидеть кое-то неожиданное:

Правило 184

Правило 184 обладает несколькими интересными особенностями, благодаря которым оно широко применяется в математическом моделировании:

  • После каждого шага количество «живых» клеток остается неизменным
  • Правило в зависимости от исходного состояния может вести себя как правило класса 2 или 4.
  • Чем меньше «живых» клеток в исходном состоянии, тем быстрее автомат стабилизируется

С его помощью довольно эффективно моделируются транспортные потоки.

Каждый отдельно взятый автомобиль передвигается вперед, в то время как волна траффика движется назад.
(картинка с Википедии)

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

Заключение

Математика, как ни крути, царица наук (хотя вряд ли её саму можно считать наукой), и работы в ней — непочатый край.

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

А бывает и наоборот — есть, казалось бы, никому не нужный математический аппарат, и тут возникает задача, для которой он внезапно оказывается пригодным (как, например, с правилом 184 и транспортными потоками).

Да и, в конце-то концов, красиво же.

Ссылки по теме:

Атлас простейших клеточных автоматов от Стивена Вольфрама;
Книга Вольфрама New Kind of Science;
Генератор простейших клеточных автоматов за авторством вашего непокорного слуги;
Еще один замечательный генератор от товарища по имени Nico Disseldorp.

Источник: https://www.pvsm.ru/javascript/110846

Ссылка на основную публикацию