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

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

    На хабре много статей по клеточным автоматам (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-ки

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


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

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


    Это тоже относится к определениям, но это точно пригодится:
    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_formula inline_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

    Спасибо Арсену за прототип солнышка!
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 3

      0
      Про окружность очень понравилось. Не поделитесь ссылкой на источник? А то когда говорят а вычислении на КА подразумевают часто только разновидности автомата фон Неймана, а тут версия естественная и красивая.
        +2
        www.intsys.msu.ru/science/books
        В.Б. Кудрявцев, С.В. Алёшин, А.С. Подколзин. Введение в теорию автоматов. Изд-во «Наука», М., 1985, 320 с. (7-я в списке)
        Про окружность написано на стр. 264, пункт 7.
          0
          Спасибо, (и похоже она есть в подсобном фонде в Ленинке). Хотя вряд ли там есть какая-то методология, а не отдельные диковинки. Ещё кстати, вспомнился способ вычленения односвязной области методом «разливания краски». Вообще, неясно как в общем виде описывать задачи для решения на клеточном автомате. Алгоритмы общего вида натягивать на КА можно (автомат фон Неймана), но вряд ли стоит, хотя бы из-за присущих КА топологических ограничений. (Правда эти ограничения можно отчасти преодолеть, я вот использовал для комбинаторного компьютера автомат с древовидной топологией.) В моделировании КА используются, но это немного не то. Хотелось бы видеть больше изящных решений специального вида задач вроде приведённых в статье, может быть когда-нибудь метод разовьётся.

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

      Самое читаемое