...

воскресенье, 20 сентября 2015 г.

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

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

На хабре много статей по клеточным автоматам (http://ift.tt/12EU9Db, http://ift.tt/1oNXGW3), особенно по игре “Жизнь” (http://ift.tt/1WaAiVL, http://ift.tt/W8mbSC, http://ift.tt/1C2XOtw). Я хочу рассказать что-то новенькое — про другие клеточные автоматы, привести неожиданные и интересные, по моему мнению, примеры. Мы посмотрим на структуру, которая постепенно копирует свою исходную конфигурацию; и на структуру, которая рисует круг.

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

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

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

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

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


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

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

Пруф


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

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

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

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


то

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

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

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


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

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

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

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

signal

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

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

signal2

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

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

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

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

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

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.

Комментариев нет:

Отправить комментарий