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