Клеточные автоматы. Сложное в простом. Матрица.

Этот текст я взял у пользователя ЖЖ. Он удалил свой блог. Но чтоб текст не пропал я решил его сохранить тут.

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

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

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

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

Эти правила придумал математик Джон Конвей в 1970 году и назвал их игрой "жизнь". Это наиболее известный пример клеточного автомата. В сущности, я считаю, что это отрицательно сказалось на распространённости самой идеи клеточных автоматов. У нас в институте сказали, что это игра "жизнь" и математическая абстракция, а большего нам знать и не надо.
Но не всё так просто.
Дело в том, что несмотря на простейшие правила, лежащие в основе, игра жизнь неожиданно смогла воспроизвести и поддерживать очень сложные структуры. Всего 2-3 правила, а там есть чрезвычайно сложное поведение некоторых структур. Есть стабильные фигуры, есть динамические фигуры (глайдеры, которые повторяют форму через несколько итераций, но смещаются), есть фигуры, порождающие эти глайдеры, есть фигуры, принимающие глайдеры и порождающие столько же глайдеров, сколько приняли. Есть много чего. Настолько много, что в этой игре удалось реализовать "машину Тьюринга".
Поль Рендель 2 апреля 2000 года создал модель машины Тьюринга с помощью клеточного автомата Джона Хортона Конвея, а 10 февраля 2010 года повторил свой замечательный опыт. В первой модели использовалась решетка 1714 х 1647, с помощью конечных автоматов которой была создана машина Тьюринга. Она имела три возможных состояния и могла обрабатывать на ленте памяти три разных символа. В эксперименте 2010 года была создана модель универсальной машины Тьюринга. Существуют и другие успешные примеры создания машин Тьюринга с помощью игры «Жизнь», некоторые из них даже получили собственные названия: MRM (Minsky Register Machine) или ее универсальная версия URM, а также CoreWorld, LogiCell и другие.

То есть вычислительное устройство, способное к любым вычислениям.
А это означает, что на такой машине можно сделать что? Правильно, запустить игру "жизнь". Жители виртуальной Вселенной игры "Жизнь" могли бы создать собственную виртуальную реальность! В которой могли бы изменить правила и клетки бы не умирали))
Разве не здорово? Такие простые 3 правила, а позволили создать целый микромир со своими законами и даже виртуальной реальностью! Всего три простых правила!

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

Чуть хитрее поведение газов. Ещё хитрее - поведение жидкости в полном соответствии с системой дифференциальных уравнений Навье-Стокса, которые довольно трудно считаются в лоб, легко симулируются практически с абсолютной точностью простым (но довольно большим по размеру) клеточным автоматом.
Так что клеточные автоматы применяются в газо и гидродинамике. А также в оптике. По весьма схожим правилам. А также в физике при моделировании столкновений элементарных частиц, в квантовой физике, даже в теории световых полей. http://www.timeorigin21.narod.ru/rus_translation/1407_6928_Light_as_quant_automat.pdf

И ещё много где применяются.
При моделировании химических реакций (классика - реакция Белоусова-Жаботинского)

При моделировании социальных процессов (вообще схожих с гидродинамикой). Например, распространение инфы в соцсетях можно промоделировать.
https://moluch.ru/archive/142/39946/

При моделировании лесных пожаров.
http://genius.pstu.ru/file.php/1/pupils_works_2012/Vasenin_Igor.pdf

При моделировании транспортных потоков.
http://bek.sibadi.org/fulltext/epd624.pdf

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

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

Многие биологические процессы, популяции, генетики и тд тоже моделируются клеточными автоматами.
А также клеточные автоматы важны в разработке теории искусственного интеллекта, хотя сейчас и утратили былую популярность, уступив программным нейросетям.
Однако многие учёные считали, да и сейчас считают, что мозг близок к клеточному автомату. Ведь и правда, если представить каждую клетку, как нейрон...
Поэтому есть проекты, вроде Клеточных Нейронных Сетей, которые значительно проще в реализации. Но это в теории, а теперь немножко практики.
http://www.dissercat.com/content/nekotorye-modeli-kletochnykh-neironnykh-setei-i-ikh-issledovanie

На практике, где-то в 1999-2000 русский эмигрант Михаил Коркин и австралиец Hugo de Garis начали работу над игрушкой Robokoneko (игрушечный котэ) с мозгами. На разработку они получили поти поллимона баксов. До этого Хьюго работал с 1993 в японской лаборатории ATR Human Information Processing Research Laboratories над Cellular Automata Machine(CAM) на FPGA. В 2000 он ушёл, а лаборатория закрылась в 2001. Он перешёл в лабораторию Starlab(Нет, Барри Аллена в нашей Вселенной нет) в Брюсселе, за свой CAM он получил грант в 1 млн долларов от правительства Бельгии. Starlab обанкротилась в 2001 году. В общем, на разработку робокотэ они получили около 1,5 млн и не успели\ не смогли предоставить рабочий прототип "мозга" до банкротства Stalab. Хьюго пошёл по интитутам и стал профессором. Робоконеко остался бумажным проектом.

Тем не менее, клеточные автоматы всё ещё продолжают рассматриваться специалистами по ИИ. Вот, например, довольно интересное исследование по ИИ на Хабре, где, опять же, используются клеточные автоматы. Очень рекомендую осилить.
https://habrahabr.ru/users/alexeyr/posts/

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

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

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

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

А что если вся наша Вселенная на самом деле работает по простым правилам?

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

Что если вся наша Вселенная - громадный клеточный автомат? И кажется такой сложной (
ньютонова физика, противоречащие друг другу ОТО, СТО и квантовая физика), но на самом деле где-то глубоко внутри, подчиняется простейшим правилам. И вся эта мозголомность и противоречивость только из-за того, что мы не знаем этих абстрактных фундаментальных правил, которые их порождают? Ведь поведение клеточного автомата тоже может быть сложным и нелогичным(сначала рост колонии, потом смерть, хотя вроде клеток полно), но при этом подчиняться простым правилам в основе.
Эту теорию продолжает развивать расовый жид Стивен Вольфрам, выпустивший книгу "New kind of science". Не смотря на то, что книжка открыто доступна на его сайте, русского перевода нет, а читать 1300 страниц тяжёлого математического текста на английском мне не по зубам. Но можете посмотреть ролик с некоторыми идеями из этой книжки.

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

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

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

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