Клеточный автомат — это сетка клеток, где каждая на каждом шаге смотрит на соседей и по одному и тому же правилу решает, какой ей стать. Только и всего, а из этого вырастают треугольники Серпинского, спиральные волны, лабиринты и «существа», которые ползают по сетке.
Как это устроено
«Элементарный 1D» — строка клеток 0 и 1. Новое значение клетки зависит от неё самой и двух соседей: вариантов восемь, а восемь ответов записываются восемью битами — это и есть номер правила от 0 до 255. Каждое поколение рисуется строкой ниже предыдущего, и получается диаграмма «пространство — время».
В «циклическом» автомате N цветов стоят по кругу, и клетка переходит в следующий цвет, если его набралось достаточно среди соседей. Следующий цвет «съедает» клетку, но и сам станет добычей своего соседа по кругу — и случайный шум сам собой собирается в спиральные волны, как в реакции Белоусова — Жаботинского.
В «Жизни» запись B/S перечисляет, при скольких живых соседях из восьми мёртвая клетка рождается (B) и живая выживает (S). Правила поколений добавляют угасающие состояния: клетка несколько шагов «остывает» и не может родиться заново.
Немного истории
В конце 1940-х Джон фон Нейман по совету Станислава Улама построил на клеточной сетке самовоспроизводящийся автомат с 29 состояниями. В октябре 1970 года Мартин Гарднер рассказал в Scientific American о «Жизни» Джона Конуэя, и в том же году Билл Госпер нашёл «ружьё», бесконечно стреляющее планерами, — из них потом собрали даже универсальный компьютер. В 1983 году Стивен Вольфрам взялся перебрать все 256 элементарных правил. Правило 30 оказалось настолько хаотичным, что служило генератором случайных чисел в Mathematica, а его узор украшает фасад вокзала Кембридж-Норт. Мэттью Кук доказал, что правило 110 универсально: оно может вычислить всё, что вычислимо. Итог Вольфрам подвёл в книге «A New Kind of Science» (2002). Циклический автомат в конце 1980-х изучал Дэвид Гриффит, а «Мозг Брайана» придумал Брайан Сильверман.
Что покрутить
- «Автомат» «элементарный 1D», «Старт» «центр» и «Правило 1D» 90 — треугольник Серпинского из одной клетки; 30 — хаос, 110 — бегущие структуры на периодическом фоне.
- В циклическом режиме поставьте «Состояний» 14, «Радиус соседства» 1, «Порог» 1 и «Соседство» фон Неймана — и дождитесь спиралей.
- «Правило „Жизни“» «Лабиринт» из шума прорастает коридорами, а «Коралл» лучше растить из центра.
- «Раскраска» «история» оставляет за угасшими клетками тающие следы; «Форма клетки» «круги» с «Зазором» превращает поле в светодиодное табло.
- Включите анимацию: одномерный автомат поползёт вверх, как лента самописца, а «Мозг Брайана» под эффектом «Калейдоскоп» станет живым орнаментом.
Реакция–диффузия
Физарум
Жилкование