Прообразом современных клеточных автоматов можно считать треугольник Паскаля, известный с десятого века. Вот что пишет Википедия:
Если очертить треугольник Паскаля, то получится равнобедренный треугольник. В этом треугольнике на вершине и по бокам стоят единицы. Каждое число равно сумме двух расположенных над ним чисел. Продолжать треугольник можно бесконечно. Строки треугольника симметричны относительно вертикальной оси. Имеет применение втеории вероятностей и обладает занимательными свойствами.
Если заменить нечётные числа точками, а чётные сделать прозрачными, то получаем треугольник Серпинского:
Рекомендую обзор треугольников Паскаля и Серпинского, опубликованный на Арбузе.
Клеточный автомат
Опять обратимся к Википедии:
«Станислав Улам, работая в Лос-аламосской национальной лаборатории в 1940-е годы, изучал рост кристаллов, используя простую решёточную модель. В это же время Джон фон Нейман, коллега Улама, работал над проблемой самовоспроизводящихся систем. Первоначальная концепция фон Неймана основывалась на идее робота, собирающего другого робота. Такая модель известна как кинематическая. Разработав эту модель, фон Нейман осознал сложность создания самовоспроизводящегося робота и, в частности, обеспечения необходимого «запаса частей», из которого должен строиться робот. Улам предложил фон Нейману использовать более абстрактную математическую модель, подобную той, что Улам использовал для изучения роста кристаллов. Таким образом возникла первая клеточно-автоматная система. Подобно решётке Улама, клеточный автомат фон Неймана двухмерный, а самовоспроизводящийся робот описан алгоритмически. Результатом явился универсальный конструктор, работающий «внутри» клеточного автомата с окрестностью, включающей непосредственно прилегающие ячейки, и имеющего 29 состояний. Фон Нейман доказал, что для такой модели существует паттерн, который будет бесконечно копировать самого себя.»
Алгоритм Живые Пиксели на бесконечном поле бесконечно копирует любой начальное расположение активных пикселей, то есть решает задачу фон Неймана.
Определение клеточного автомата из Википедии:
«Кле́точный автома́т — дискретная модель, изучаемая в математике, теории вычислимости, физике, теоретической биологии и микромеханике. Включает регулярную решётку ячеек, каждая из которых может находиться в одном из конечного множества состояний, таких как 1 и 0. Решетка может быть любой размерности. Для каждой ячейки определено множество ячеек, называемых соседством. К примеру, соседство может быть определено как все ячейки на расстоянии не более 2 от текущей. Для работы клеточного автомата требуется задание начального состояния всех ячеек, и правил перехода ячеек из одного состояния в другое. На каждой итерации, используя правила перехода и состояния соседних ячеек, определяется новое состояние каждой ячейки. Обычно правила перехода одинаковы для всех ячеек и применяются сразу ко всей решётке.»
Достаточно обширный анализ клеточных автоматов сделан в программе Cellular Automata Laboratory http://www.fourmilab.ch/cellab/cellab.zip В программе реализованы 37 видов автоматов, которые описаны по-английски на странице:http://www.fourmilab.ch/cellab/manual/rules.html Примеры к программе не используют алгоритм, повторяющий Живые Пиксели, изучение описаний алгоритмов показывает, что Живые Пиксели являются частным случаем алгоритма Эдварда Фредкина Fredmem. Близким к Живым Пикселям является алгоритм Fractal, который также является частным случаем алгоритма Fredmem. Эдвард Фредкин указывает на то, что его алгоритм является примером «самовоспроизводства», то есть «размножения» — начальная фигура через определённое число итераций превращается в несколько таких же фигур. Такую картину мы наблюдаем в Живых Пикселях на бесконечном поле.
Ещё более полная подборка клеточных автоматов приводится на сайте:http://www.mirekw.com/ca/rullex_wlif.html
Алгоритмы «Эволюция», и затем «Живые Пиксели» были разработаны и программно реализованы в 2012м году. На сегодняшний день многие аспекты алгоритмов остаются неизученными. Читатель может принять участие в анализе «Живых Пикселей» и «Эволюции» и поиске интересных конструкций, используя программу NeoNeuro Live Pixels – Живые Пиксели.