Удивительные клеточные автоматы: блочные КА, окрестность Марголуса

👾, Хабр!

Сегодня мы снова немного отойдём от классической модели, и будем строить конфигурацию с самого начала, благо, никаких сложностей в этом нет. Сегодняшняя конфигурация – блочные КА – предполагает, что наша сетка разбивается на некоторые участки, собственно, блоки, для которых заранее определены инструкции перехода. Никаких вариаций – один шаблон перехода для одного шаблона расположения. Звучит так, будто мы получим набор бессвязных осцилляторов, верно? Но у конфигурации есть второе условие: каждый шаг происходит смещение сетки разбиения, за счёт чего клетки при каждой следующей итерации относятся к новому блоку. Лучше, конечно, на примере.

Самой популярной моделью построения блочных КА является разбиение на блоки 2×2 со смещением на 1 клетку по диагонали за итерацию. Данная модель носит имя своего первого и основного исследователя, пионера изучения КА – Нормана Марголуса. Хоть сам вид и называют окрестностью Марголуса, он несколько отличается логически от тех окрестностей, что мы с вами обозревали ранее. А именно: данная окрестность отображает сразу оба возможных состояния, и она не привязана ни к какой конкретной клетке. Читать дальше →

Источник