Игра «Жизнь»

В игре «Жизнь» Конвея каждая клетка x бесконечной решётки либо жива, $s(x) = 1$, либо мертва, $s(x) = 0$. Если N(x) — число живых клеток среди 8 соседей x, включая диагональных, то следующее поколение задаётся так:

Это правило B3/S23. Здесь можно рисовать узоры, наблюдать их развитие, возвращаться к прошлым поколениям, заглядывать на поколение вперёд и узнавать, когда стабилизация узора доказана.

Все клетки обновляются одновременно по одному и тому же предыдущему поколению. На паузе Следующее поколение показывает шаг до его выполнения: клетки, которым предстоит родиться, обведены рамкой, а те, которым предстоит умереть, перечёркнуты. Наведение на клетку показывает её 8 соседей и число живых среди них. У поля нет края, и оно не замыкается само на себя. Угловая стрелка у края изображения показывает число живых клеток за его пределами в этом направлении. Кривая на панели считает живые клетки в каждом поколении после последнего изменения поля.

Некоторые типы объектов возникают снова и снова. Натюрморт никогда не меняется, как блок или улей. Осциллятор возвращается в исходное состояние, как мигалка каждые 2 поколения. Космический корабль возвращается к прежней форме в другом месте: глайдер через 4 поколения сдвигается на клетку в сторону и на клетку вниз. Ружьё возвращается к своему состоянию и каждый раз что-то оставляет позади; ружьё Госпера выпускает глайдер каждые 30 поколений. Маленькие узоры, которым нужно много времени для стабилизации, например R-пентамино, называются мафусаилами. Поскольку следующее состояние клетки зависит только от блока 3 × 3 вокруг неё, никакое влияние не распространяется быстрее одной клетки за поколение; диагональный шаг тоже считается за одну клетку. Это скорость света c, а глайдер движется со скоростью c/4.

Страница объявляет узор стабилизировавшимся, только если может это доказать. Доказательство опирается на один факт. Обозначим через F переход на одно поколение. Если две группы живых клеток X и Y находятся на расстоянии не менее 3 клеток друг от друга, по-прежнему считая диагональный шаг за одну клетку, то

поскольку никакой блок 3 × 3 не захватывает обе группы. Поэтому, как только оставшиеся на месте остатки узора начинают повторяться сами по себе, а каждый улетающий корабль всегда остаётся не менее чем в 3 клетках от них и от других кораблей, ничто больше не может их потревожить. Пунктирная линия на кривой отмечает первое поколение, с которого поле состоит из этих остатков и этих кораблей. Если страница не может это доказать, например при приближающемся столкновении кораблей или продолжающем стрелять ружье, она не делает вывода о стабилизации. Она также никогда не утверждает, что узор не стабилизируется в будущем.

Джон Хортон Конвей придумал игру в 1970 году, а Мартин Гарднер сделал её известной в октябре того же года, рассказав о ней в Scientific American.