Дискретная модель, состоящая из сетки ячеек, каждая из которых обновляет своё состояние на основе локальных правил и соседей.Клеточный автомат — это модель, в которой пространство разделено на регулярную сетку ячеек, время идёт дискретными шагами, а каждая ячейка находится в одном из небольшого числа состояний: включена или выключена, жива или мертва, один из нескольких цветов. На каждом такте все ячейки обновляются одновременно по правилу, которое учитывает только собственное состояние ячейки и состояния её ближайших соседей. Ничего больше не принимается в расчёт: ни глобального управляющего центра, ни дальнодействующих сигналов. Несмотря на такую аскетичность, клеточные автоматы могут порождать узоры поразительной сложности, поэтому их используют для изучения того, как простые локальные взаимодействия приводят к крупномасштабному порядку.
Они важны потому, что служат чистой испытательной площадкой для вопросов об эмерджентности, вычислениях и самоорганизации. Правило, умещающееся на открытке, может породить узор, который растёт бесконечно, входит в повторяющийся цикл или ведёт себя непредсказуемо. Некоторые правила оказываются способны к универсальным вычислениям — могут имитировать любой другой компьютер при достаточном запасе пространства и времени. Этот результат связывает теорию вычислений с физикой и биологией, намекая, что сложность не обязательно должна возникать из сложных ингредиентов.
Клеточные автоматы также служат игрушечными моделями в физике и биологии: транспортные потоки, рост кристаллов, лесные пожары, динамика хищник–жертва и распространение эпидемий — всё это моделировалось таким образом. Обычно они не предназначены для точного описания природы, а представляют собой минимальные системы, изолирующие механизм.
Джон фон Нейман задумал самовоспроизводящиеся автоматы в 1940-х годах, отчасти побуждаемый вопросами о биологическом размножении; Станислав Улам предложил формат сетки. Джон Конвей представил «Жизнь» в 1970 году, популяризовав эту область. Систематическое изучение одномерных правил Стивеном Вольфрамом в 1980-х годах привело к их классификации на четыре класса поведения.
Вы выбираете сетку (одномерную, квадратную, шестиугольную или более высокой размерности), набор состояний для каждой ячейки, окрестность (например, четыре ортогональных соседа или восемь окружающих ячеек) и правило, сопоставляющее каждой возможной конфигурации окрестности новое состояние центральной ячейки. Затем вы применяете правило сразу ко всем ячейкам, получая следующее поколение. Повторяйте.
Знаменитая «Жизнь» использует квадратную сетку, два состояния и окрестность Мура из восьми ячеек: живая клетка выживает при двух или трёх живых соседях и умирает в противном случае; мёртвая клетка оживает ровно при трёх. Из этих нескольких строк возникают глайдеры, осцилляторы и самовоспроизводящиеся структуры. Ключевой момент в том, что правило локально и единообразно — одно и то же везде, на каждом шаге, — поэтому любая структура, которую вы видите, есть следствие правила, а не особых начальных условий.
Используются в моделях транспортных и людских потоков, в решёточно-газовых методах моделирования жидкостей, в криптографии и генерации случайных чисел, а также как учебный инструмент для изучения эмерджентности и вычислений.
«Жизнь» тьюринг-полна: достаточно большой узор можно организовать так, чтобы он вычислял всё, что способен вычислить обычный компьютер, используя глайдеры в качестве сигналов.
