Интересные примеры клеточных автоматов.
На хабре много статей по клеточным автоматам (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/). Я хочу рассказать что-то новенькое — про другие клеточные автоматы, привести неожиданные и интересные, по моему мнению, примеры. Мы посмотрим на структуру, которая постепенно копирует свою исходную конфигурацию; и на стркутру, которая рисует круг.
где множество целочисленных k-мерных векторов — ячейки структуры. Будем использовать ;
— множество состояний;
— упорядоченный набор попарноразличных ненулевых векторов из мощности , для удобства положим . Это окресность ячейки;
– функция n зачной логики h аргументов (), — правило изменения состояний;
Вообще говороя, вместо можно брать и дргуие носители, просто так делают невероятно редко. Почему бы не сдлеать клеточный автомат на торе?
Это тоже относится к определениям, но это точно пригодится:
– состояние структуры.
– ячейка, то – ее состояние. Нечто вроде: «по координатам ячейки — ее состояние».
– новое состояние ячейки
– новое состояние структуры, где каждая ячека имеет свое новое состояние. (Применили ко всем ячейкам)
Заметим, что новое состояние структуры не зависит от «порядка применения» , как это может показаться с первого взгяляда: на самом деле мы не изменяем состояние, мы делаем новое поле и его заполняем новыми состояниями.
Конфигурация – состояние структуры с конечным количеством ненулевых ячеек.
Структура копирования
У нас есть некоторые направления — окресность. Захотим же, чтобы — XOR’ила все значения из окресности (в том числе и значение ячейки, результат которой вычисляем). Почему мы взяли именно так? Просто нам ясно, что если у нас на поле только одна единичная клеточка, то за один ход она «откопируется» во всю окрестность (инвертированную).
Очевидно, что операция линейна (в смысле XOR), то есть мы можем вычилить новые конфигурации для каждой ячейки по отдельности, а потом поэлементно проксорить результат, а не честно считать новую конфигурацию. Другими словами: если , то . Ну и соответсвенно .
Обозначим — конфигурация с одной единичкой в ячейке элементом.
Ну так рассмотрим их по отдельности. Несложно заметить, что следующая конфигурация будет иметь в ячейках (в том числе, 1 останется на месте), то есть:
Посмотрим, как конфигурация будет всести себя дальше (а она то будет всети себя классно!):
Выходит, что все члены при сокращаются, ибо входят четное число раз в сумму (а мы используем поле характеристики два).
Что же, база доказательсятва копирования готова, запилим переход. Все так же, только вместо двойки — .
Если применение раз имеет вид:
то
Ну и успех. За базу можно было взять одну итерацию, но было бы не ясно откуда всё пошло.
Теперь имеем
Классно, круто, наша структура действительно копируется по направлениям векторов окрестности.
Покпируем солнышко:
На примере квадрата, как это распространяется дальше:
Окружность
Замечательный пример невероятного: дискретной структурой, с конечной памятью каждой ячейки (а значит она не может помнить даже свои координаты!) будем сколь угодно хорошо будем интерполировать непрервыный объект — окружность.
Я не буду формально описывать эту систему, так как от ее формального описания яснее не станет: там у ячейки дюжина состояний и столько же элементов в окресности.
Начнем. Почти очевидно, что такое бегающий сигнал
И ясно, что он может «расталкивать» удерживающие его ячейки.
Это почти всё, что нам нужно: запустим горизонтиальный сигнал, который будет расталкивать несущие ячейки, а при каждом расталкивании будем создавать два вертикальных фиксатора и вертикальный сигнал. Ясно, что сигналы можно устроить так, чтобы горизонтальный не кофликтовал с вертикальными: если они уж наложились, нужно делать новое состояние, которое будет «помнить» в какие стороны нужно запустить сигналы на следующем шаге.
Почему же фиксирующие точки будут стремиться к окружности?
Обозначим:
, — расстояние «до начала» от точек, фиксирующих горизонтальный сигнал;
, — рассточние от горизонтальной оси до точек, фиксирующих вертикальный сигнал в столбце с индексом ;
Тогда время запуска вертикального сигнала: (для каждого из суммы нам нужно от центра отойти на вправо, вернуться, влево, вернуться), что ассимптотически . Аналогично, время от запуска вертикального сигнала до достижения им высоты : . Определим радиус окружности, как , то есть имеем . Как мы уже поняли, время образования точки на столбце на расстоянии : . Эта точка лежит на окружности радиуса (теорема Пифагора), то есть , но , то есть мы получили, что . А это значит, что все такие (вертикальные фиксирующие) точки будут находится примерно на том же расстоянии от центра, что и горизонтальные фиксирующие. Следовательно, они буду образовывать фигуру, близкую к окружности.
Красивая картинка, проясняющая ситуацию.
Спасибо Арсену за прототип солнышка!
ссылка на оригинал статьи http://habrahabr.ru/post/267219/
Добавить комментарий