Итак, клеточные автоматы — это математические объекты с дискретными пространством и временем. Каждое положение в пространстве представлено отдельной клеткой, а каждый момент времени — дискретным временным шагом или поколением. Состояние каждой пространственной клетки определяется очень простыми правилами взаимодействия. Эти правила предписывают изменения состояния каждой клетки в следующем такте времени в ответ на текущее состояние соседних клеток.

Преобразование системы по правилу «сумма по модулю два»

Например, если пустой клетке присвоено значение 0, а занятой клетке — 1, то правила можно представить, скажем, так: на каждом шаге каждой клетке присваивается значение 0, если две ближайшие к ней клетки либо обе пусты, либо обе заняты. В арифметическом смысле это соответствует правилу, согласно которому новое значение каждой клетки равно сумме значений ближайших к ней клеток по модулю два. Далее такое построение можно автоматически повторять на каждом следующем шаге — отсюда название «клеточный автомат».

Впервые идея таких автоматов появляется в 1940-х годах в работах Джона фон Неймана и Станислава Улама. Улам и фон Нейман были близкими друзьями, эмигрантами из Восточной Европы, выходцами из верхушки среднего класса с еврейскими корнями. Оба очутились в одинаковой политической ситуации и оба обладали выдающимся интеллектом. В 1935 году фон Нейман пригласил Улама в США, а четыре года спустя сделал Уламу, работавшему тогда в Висконсинском университете, более интригующее предложение: перебраться в Нью-Мексико и присоединиться к нему в работе над неизвестным проектом. Улам взял в университетской библиотеке путеводитель по штату Нью-Мексико и увидел, что до него путеводитель брали его коллеги, которые исчезли куда-то без всяких объяснений. Выяснив, в каких областях они работали, он понял, что именно его просят сделать. Так Улам присоединился к Манхэттенскому проекту в Лос-Аламосе.

В ходе разработки термоядерного оружия Улам понял, что если поведение физической системы является слишком сложным, то для того, чтобы его прогнозировать, нужно предоставить компьютеру возможность сделать множество случайных оценок, а затем получить более точные показатели с помощью статистических методов. Во время одной из поездок на автомобиле Улам объяснил этот метод фон Нейману; тогда и было придумано для него название — «метод Монте-Карло». Например, для того чтобы определить вероятность того, что шарик рулетки остановится на черном, игроку не нужно решать уравнение — он может просто подсчитать, сколько раз шарик выпадает на черное после сотен случайных бросков.

Так Улам увлекся теорией игр. Все свое свободное время в Лос-Аламосе он тратил на изобретение игр с одним участником. Эти игры сводились к созданию шаблонов из ячеек решетки. Изменение правил создания таких шаблонов позволяло строить фигуры, которые могли разрастаться и меняться весьма необычными способами. Эти игры вдруг пересеклись с исследованиями, в которых фон Нейман пытался выяснить, что понадобится машине, чтобы воспроизвести себя.

Ему понадобилось посвятить 200 страниц своей книги «Теория самовоспроизводящихся автоматов» доказательству того, что «универсальный строитель» принципиально возможен. Однако он обнаружил, что самовоспроизводиться способна только машина, преодолевшая определенный порог сложности. Это очень важный вывод: качественно новые свойства появляются у системы только тогда, когда она обладает достаточным уровнем сложности.

Улам выдвинул предположение, что для того, чтобы сосредоточиться исключительно на логических аспектах самовоспроизведения, вместо работы с реальной машиной фон Нейману следует проанализировать фигуры, образующиеся на решетке ячеек. В процессе обсуждения этой задачи двое ученых изобрели новую математическую концепцию — «клеточный автомат».

Фон Нейман разработал клеточный автомат, в котором каждая клетка находилась в одном из 29 состояний, и придумал правила, призванные обеспечить самовоспроизведение исходного шаблона, состоящего из 200 000 клеток. Клеточные автоматы не привлекали к себе особого академического интереса до тех пор, пока на них не обратил внимание британский математик с еще более «игривым разумом, чем у Улама».

В 1960-х годах в комнате отдыха математического факультета Кембриджского университета преподаватели и студенты постоянно играли в настольные игры и придумывали новые. Идей было так много, что один преподаватель даже вел файл под названием Games Without Names («Игры без названий») и сопутствующий файл — Names Without Games («Названия без игр»). Здесь Джон Конвей, ливерпульский фанатик игры в нарды и талантливый математик, изобрел свой клеточный автомат на квадратной сетке, которому он дал имя Game of Life («Игра "Жизнь"»).

В этой игре клетка является либо живой, либо мертвой и подчиняется следующим правилам.

• Рождение: мертвая клетка, имеющая три живые соседние клетки, становится живой.

• Выживание: живая клетка, имеющая две или три живые соседние клетки, продолжает жить.

• Смерть от одиночества: живая клетка, у которой нет по соседству живых клеток или есть только одна такая клетка, умирает.

• Смерть от перенаселенности: живая клетка с четырьмя или более соседними клетками умирает.