Я давно хотел реализовать клеточный автомат «в железе» — то есть без программ, процессоров, микроконтроллеров, — на жёсткой логике. Например, широко известную игру «Жизнь». Однако каждый раз, когда я пытался представить себе реализацию, получалось нечто ужасное: сотни и сотни логических элементов ради того, чтобы собрать крошечное поле, на которое не влезет ничего, кроме одного глайдера. Поэтому я решил начать с чего-то более простого, — например, взять не двумерный клеточный автомат, а одномерный. Скажем, «Правило 110». В этой серии статей я расскажу, как мне удалось решить эту задачу.
-
Часть 1 — Изобретаем велосипед (Вы здесь)
-
Часть 2 — «Заработало!» (ссылка появится позже)
-
Часть 3 — Щупаем «Правило 110» (ссылка появится позже)
Что такое клеточные автоматы?
Клеточный автомат — это математическая конструкция, представляющая собой поле в клеточку, где каждая клетка может находиться в одном из нескольких состояний. Клеточный автомат развивается во времени, и делает это дискретно — по шагам. На каждом шаге все клетки одновременно определяют своё новое состояние по заранее заданным правилам, основываясь на собственном текущем состоянии и состоянии своих соседей. Обычно правила одинаковы для всех клеток.
Совсем простые правила могут порождать удивительно сложное поведение клеточного автомата в целом. В частности, игра «Жизнь» [1] — наиболее известный клеточный автомат — является полным по Тьюрингу: на достаточно большом (в пределе бесконечном) поле из специально организованных клеточных структур можно реализовать выполнение любого алгоритма. Есть, например, проекты калькуляторов, машины Тьюринга и даже реализация «Жизни» в «Жизни».
Источник: habr.com