Игра «Жизнь» — клеточный автомат, придуманный английским математиком Джоном Конвеем в 1970 году. Это игра без игроков, в которой человек создаёт начальное состояние, а потом лишь наблюдает за её развитием. В игре можно создать процессы с полнотой по Тьюрингу, что позволяет реализовать любую машину Тьюринга.
Кле́точный автома́т — дискретная модель, изучаемая в математике, теории вычислимости, физике, теоретической биологии и микромеханике. Основой является пространство из прилегающих друг к другу клеток (ячеек), образующих решётку. Каждая клетка может находиться в одном из конечного множества состояний. Решётка может быть любой размерности, бесконечной или конечной, для решётки с конечными размерами часто предусматривается закольцованность при достижении предела (границы). Для каждой клетки определено множество клеток, называемых окрестностью. Например, окрестность фон Неймана ранга 2 включает все клетки на расстоянии не более 2 от текущей. Устанавливаются правила перехода клеток из одного состояния в другое. Обычно правила перехода одинаковы для всех клеток. Один шаг автомата подразумевает обход всех клеток и на основе данных о текущем состоянии клетки и её окрестности определение нового состояния клетки, которое будет у неё при следующем шаге. Перед стартом автомата оговаривается начальное состояние клеток, которое может устанавливаться целенаправленно или случайным образом.
Циклический клеточный автомат — класс клеточных автоматов. Система правил, определяющая волнообразное порождение клеток в циклическом клеточном автомате , может определять генерацию паттернов, имитирующих самоорганизующиеся автокаталитические химические реакции типа реакции Белоусова-Жаботинского. Правила циклического клеточного автомата — одни из самых простых среди клеточных автоматов:
- клетка меняет цвет только при наличии рядом заданного критического числа клеток-соседей того же цвета
- цвета могут меняться только в определённом порядке.
Правило 184 — элементарный клеточный автомат, то есть одномерный клеточный автомат с двумя состояниями.
Окре́стность фон Не́ймана клетки — совокупность четырёх клеток на квадратном паркете, имеющих общую сторону с данной клеткой. Окрестность получила своё название в честь Джона фон Неймана, использовавшего её в своих клеточных автоматах, включая универсальный конструктор. Окрестность фон Неймана и окрестность Мура являются наиболее часто используемыми окрестностями в двумерных моделях клеточных автоматов.
Пра́вило 30 — элементарный клеточный автомат, то есть одномерный клеточный автомат с двумя состояниями, впервые описанный Стивеном Вольфрамом в 1983 году. Стивен Вольфрам говорит, что «это его самое любимое правило», и подробно описывает его в своей книге «A New Kind of Science». Из четырёх типов поведения, описанных в этой книге, Правило 30 обладает классом поведения III, показывая апериодическое, хаотическое поведение.
Косми́ческий кора́бль — класс конфигураций в «Жизни» — созданной Конвеем модели клеточного автомата.
Натюрмо́рт — класс конфигураций в «Жизни» — созданной Конвеем модели клеточного автомата.
Сад Эде́ма — конфигурация в игре «Жизни» Конвея или другом клеточном автомате, которая не может появиться в результате эволюции, потому что не имеет предшественников. Термин «сад Эдема» был введён Джоном Тьюки ещё в 1950-х годах, задолго до появления «Жизни».
Правило 110 — один из вариантов элементарного клеточного автомата, в котором последовательность результатов преобразования образуют бинарную последовательность 01101110, что является двоичным представлением десятичного числа 110. Все элементарные клеточные автоматы представляют собой бесконечную ленту из последовательно размещённых клеток, которые могут иметь только два состояния и при этом будущее состояние клетки зависит от текущих значений трёх клеток — её самой и двух её ближайших соседей.
Правило 90 — это элементарный клеточный автомат, то есть одномерный клеточный автомат с двумя состояниями, основанный на функции сложения по модулю 2 . Наименование «Правило 90» определяется кодом Вольфрама.
Элементарный клеточный автомат — это клеточный автомат с одномерным массивом ячеек в форме бесконечной в обе стороны ленты, который имеет два возможных состояния ячеек и правило для определения состояния ячейки на следующем шаге, использующее только состояние ячейки и её двух соседей на текущем шаге. В целом такие автоматы являются одними из наиболее простых возможных клеточных автоматов, однако при некоторых правилах они показывают сложное поведение; так, использование правила 110 приводит к полному по Тьюрингу автомату.
Долгожи́тель — класс конфигураций клеточного автомата, в частности — игры «Жизнь» Конвея, которые состоят из небольшого числа живых ячеек в начальном состоянии, но стабилизируются только спустя много поколений. Под стабилизацией подразумевается распадение конфигурации на циклические и стабильные подконфигурации и удаляющиеся от точки старта космические корабли. Стабилизация для долгожителя обязательна, и это сужает круг применимости данного термина — во многих клеточных автоматах любая конфигурация либо быстро вымирает, либо растёт неограниченно.
Обратимый клеточный автомат — клеточный автомат, в котором каждое состояние имеет единственного предшественника. Таким образом, это регулярная решётка из ячеек, состояние каждой из которых берётся из конечного множества состояний, и правило для одновременного обновления состояний ячеек, исходя из состояний её соседей. Условие обратимости заключается в том, что предыдущее состояние любой ячейки может быть определено, зная обновлённые состояния всех ячеек решётки. После обращения времени получается другой обратимый клеточный автомат, возможно — с намного большими окрестностями, но также с правилом для определения будущего состояния ячейки, исходя из текущих состояний ей соседей.
«Криттеры» — блочный клеточный автомат, проявляющий поведение, схожее с игрой «Жизнь» Конвея; в частности, полон по Тьюрингу. Впервые описан Томмазо Тоффоли и Норманом Марголусом в 1987 году, как и некоторые другие обратимые клеточные автоматы.
«День и ночь» — клеточный автомат, модификация игры «Жизнь». Придуман и назван в 1997 году Нейтаном Томпсоном ; подробно исследован Дэвидом Беллом, который нашёл многие любопытные конфигурации и дал им имена.
Парово́з — класс конфигураций в игре «Жизнь» и других родственных ей клеточных автоматах: объект, который движется по полю подобно космическому кораблю, но при этом ещё и оставляет за собой «выхлопы» — след из других объектов.
HighLife — клеточный автомат, модификация игры «Жизнь». Придуман в 1994 году Нейтаном Томпсоном, назван Джоном Конвеем.
Грабли - разновидность паровоза - конфигурации, оставляющей за собой след из мусора. Грабли же оставляют мусор в виде потока из космических кораблей.
«Семена́» — клеточный автомат, модификация игры «Жизнь». Придуман Брайаном Сильверманом, назван Миреком Вуйтовичем (Mirek Wójtowicz).
Три лестницы. Верхняя и нижняя останавливаются, натолкнувшись на простейший натюрморт из одной живой клетки; средняя лестница, встретив устойчивый объект из четырёх живых клеток, поворачивает — и останавливается, столкнувшись с нижней.
Быстрый паразитический росток на более медленной лестнице. Когда росток обгоняет лестницу, происходит хаотичный «взрыв», выбрасывающий два паразитических ростка в обратном направлении.