Клеточные автоматы и Игра Жизнь: Возникновение сложного из простого

Игра "Жизнь" (Conway's Game of Life) разворачивается на бесконечном двумерном поле (как тетрадный лист в клетку). Каждая клетка может находиться в одном из двух состояний: "жива" или "мертва". У каждой клетки есть 8 соседей. Эволюция всей системы происходит дискретными шагами (поколениями) по трем простейшим правилам:

1. Рождение: мертвая клетка, у которой ровно 3 живых соседа, оживает на следующем шаге (имитация размножения).
2. Выживание: живая клетка, у которой 2 или 3 живых соседа, остается живой (комфортная среда).
3. Смерть: если у живой клетки меньше 2 соседей, она умирает (от одиночества), а если больше 3 — тоже умирает (от перенаселения и нехватки ресурсов).

Несмотря на тривиальность правил, на поле начинают происходить математические чудеса. Возникают "осцилляторы" (фигуры, которые пульсируют, меняя форму и возвращаясь в исходную), "планеры" или глайдеры (структуры, которые самостоятельно ползут по бесконечному полю) и "ружья" (неподвижные фабрики, бесконечно стреляющие глайдерами).

С точки зрения информатики, Игра Жизнь обладает потрясающим свойством: доказано, что она является Полной по Тьюрингу (Turing-complete). Это означает, что из глайдеров и осцилляторов можно спроектировать полноценные логические вентили (И, ИЛИ, НЕ), регистры памяти и сумматоры. Следовательно, прямо на поле этой простой игры можно построить работающую модель процессора, которая сможет запустить любую программу, написанную человечеством (включая саму Игру Жизнь)!

Вне развлечений клеточные автоматы (изученные, в частности, Стивеном Вольфрамом) имеют колоссальное прикладное значение. Одномерные клеточные автоматы (такие как "Правило 30") генерируют последовательности, настолько близкие к истинному хаосу, что они используются в качестве генераторов псевдослучайных чисел в криптографии. Также на клеточных автоматах строятся быстрые компьютерные симуляции диффузии газов, роста кристаллов снежинок, распространения лесных пожаров и динамики автомобильных пробок, где каждый автомобиль представлен как автомат, реагирующий на впереди идущую машину.