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

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

На хабре много статей по клеточным автоматам (http://habrahabr.ru/post/168291/, http://habrahabr.ru/post/227003/), особенно по игре “Жизнь” (http://habrahabr.ru/post/67790/, http://habrahabr.ru/post/154509/, http://habrahabr.ru/post/237629/). Я хочу рассказать что-то новенькое — про другие клеточные автоматы, привести неожиданные и интересные, по моему мнению, примеры. Мы посмотрим на структуру, которая постепенно копирует свою исходную конфигурацию; и на структуру, которая рисует круг.

Осторожно, большие gif-ки

Определение — штука важная, но не всем интересная

По книге Кудрявцева “Введение в теорию автоматов”, клеточынй автомат (или однородная структура) это набор:

где множество целочисленных k-мерных векторов — ячейки структуры. Будем использовать ;
— множество состояний;
— упорядоченный набор попарноразличных ненулевых векторов из мощности , для удобства положим . Это окрестность ячейки;
– функция n значной логики h аргументов (), — правило изменения состояний;

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

Это тоже относится к определениям, но это точно пригодится:
– состояние структуры.
– ячейка, то – ее состояние. Нечто вроде: «по координатам ячейки — ее состояние».
– новое состояние ячейки
– новое состояние структуры, где каждая ячека имеет свое новое состояние. (Применили ко всем ячейкам)

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

Конфигурация – состояние структуры с конечным количеством ненулевых ячеек.

Структура копирования

У нас есть некоторые направления — окресность. Захотим же, чтобы — XOR'ила все значения из окресности (в том числе и значение ячейки, результат которой вычисляем). Почему мы взяли именно так? Просто нам ясно, что если у нас на поле только одна единичная клеточка, то за один ход она «откопируется» во всю окрестность (инвертированную).

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

Пруф

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

Посмотрим, как конфигурация будет всести себя дальше (а она то будет вести себя классно!):

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

Что же, база доказательства копирования готова, попробуем сделать переход. Все так же, только вместо двойки — .
Если применение раз имеет вид:

то

Что и хотелось получить.
Теперь имеем
Классно, круто, наша структура действительно копируется вдоль векторов, задающих окрестность.

Покопируем солнышко:


На примере квадрата, как это распространяется дальше:

Окружность

Замечательный пример невероятного: дискретной структурой, с конечной памятью каждой ячейки (а значит она не может помнить даже свои координаты!) будем сколь угодно хорошо будем интерполировать непрерывный объект — окружность.

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

Начнем. Почти очевидно, что такое бегающий сигнал

Как устроен

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

И ясно, что он может «расталкивать» удерживающие его ячейки.

Как устроен

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

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

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

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

Красивая картинка, проясняющая ситуацию:



Спасибо Арсену за прототип солнышка!