Маши́на Тью́ринга (Шаблон:Сокр) — абстрактный исполнитель. Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма.
Игра «Жизнь» — клеточный автомат, придуманный английским математиком Джоном Конвеем в 1970 году. Это игра без игроков, в которой человек создаёт начальное состояние, а потом лишь наблюдает за её развитием. В игре можно создать процессы с полнотой по Тьюрингу, что позволяет реализовать любую машину Тьюринга.
Кле́точный автома́т — дискретная модель, изучаемая в математике, теории вычислимости, физике, теоретической биологии и микромеханике. Основой является пространство из прилегающих друг к другу клеток (ячеек), образующих решётку. Каждая клетка может находиться в одном из конечного множества состояний. Решётка может быть любой размерности, бесконечной или конечной, для решётки с конечными размерами часто предусматривается закольцованность при достижении предела (границы). Для каждой клетки определено множество клеток, называемых окрестностью. Например, окрестность фон Неймана ранга 2 включает все клетки на расстоянии не более 2 от текущей. Устанавливаются правила перехода клеток из одного состояния в другое. Обычно правила перехода одинаковы для всех клеток. Один шаг автомата подразумевает обход всех клеток и на основе данных о текущем состоянии клетки и её окрестности определение нового состояния клетки, которое будет у неё при следующем шаге. Перед стартом автомата оговаривается начальное состояние клеток, которое может устанавливаться целенаправленно или случайным образом.
Клеточный автомат фон Неймана — клеточный автомат, разработанный Джоном фон Нейманом при содействии Станислава Улама для исследования возможности создания самовоспроизводящихся машин.
Фронтальный клеточный автомат - специальный тип вычислительных алгоритмов, основанных на моделях клеточных автоматов.
Правило 184 — элементарный клеточный автомат, то есть одномерный клеточный автомат с двумя состояниями.
Wireworld — клеточный автомат, предложенный Брайаном Сильверманом в 1987 году, смоделированный в его программе Phantom Fish Tank. Автомат стал более известен после опубликования статьи в колонке «Computer Recreations» журнала Scientific American. Wireworld в особенности пригоден для симуляции электронных логических элементов, или «гейтов». Несмотря на простоту правил, Wireworld является полным по Тьюрингу.
Окре́стность фон Не́ймана клетки — совокупность четырёх клеток на квадратном паркете, имеющих общую сторону с данной клеткой. Окрестность получила своё название в честь Джона фон Неймана, использовавшего её в своих клеточных автоматах, включая универсальный конструктор. Окрестность фон Неймана и окрестность Мура являются наиболее часто используемыми окрестностями в двумерных моделях клеточных автоматов.
Пра́вило 30 — элементарный клеточный автомат, то есть одномерный клеточный автомат с двумя состояниями, впервые описанный Стивеном Вольфрамом в 1983 году. Стивен Вольфрам говорит, что «это его самое любимое правило», и подробно описывает его в своей книге «A New Kind of Science». Из четырёх типов поведения, описанных в этой книге, Правило 30 обладает классом поведения III, показывая апериодическое, хаотическое поведение.
Окре́стность Му́ра клетки — в двумерном случае — совокупность восьми клеток на квадратном паркете, имеющих общую вершину с данной клеткой. Окрестность получила своё название в честь одного из пионеров теории клеточных автоматов Эдварда Мура.
Правило 110 — один из вариантов элементарного клеточного автомата, в котором последовательность результатов преобразования образуют бинарную последовательность 01101110, что является двоичным представлением десятичного числа 110. Все элементарные клеточные автоматы представляют собой бесконечную ленту из последовательно размещённых клеток, которые могут иметь только два состояния и при этом будущее состояние клетки зависит от текущих значений трёх клеток — её самой и двух её ближайших соседей.
Правило 90 — это элементарный клеточный автомат, то есть одномерный клеточный автомат с двумя состояниями, основанный на функции сложения по модулю 2 . Наименование «Правило 90» определяется кодом Вольфрама.
Элементарный клеточный автомат — это клеточный автомат с одномерным массивом ячеек в форме бесконечной в обе стороны ленты, который имеет два возможных состояния ячеек и правило для определения состояния ячейки на следующем шаге, использующее только состояние ячейки и её двух соседей на текущем шаге. В целом такие автоматы являются одними из наиболее простых возможных клеточных автоматов, однако при некоторых правилах они показывают сложное поведение; так, использование правила 110 приводит к полному по Тьюрингу автомату.
Обратимый клеточный автомат — клеточный автомат, в котором каждое состояние имеет единственного предшественника. Таким образом, это регулярная решётка из ячеек, состояние каждой из которых берётся из конечного множества состояний, и правило для одновременного обновления состояний ячеек, исходя из состояний её соседей. Условие обратимости заключается в том, что предыдущее состояние любой ячейки может быть определено, зная обновлённые состояния всех ячеек решётки. После обращения времени получается другой обратимый клеточный автомат, возможно — с намного большими окрестностями, но также с правилом для определения будущего состояния ячейки, исходя из текущих состояний ей соседей.
«Криттеры» — блочный клеточный автомат, проявляющий поведение, схожее с игрой «Жизнь» Конвея; в частности, полон по Тьюрингу. Впервые описан Томмазо Тоффоли и Норманом Марголусом в 1987 году, как и некоторые другие обратимые клеточные автоматы.
Бильярдный компьютер — логическая модель для проведения обратимых вычислений, механический компьютер, основанный на законах движения Ньютона и предложенный в 1982 году Эдвардом Фредкиным и Томмазо Тоффоли.
«День и ночь» — клеточный автомат, модификация игры «Жизнь». Придуман и назван в 1997 году Нейтаном Томпсоном ; подробно исследован Дэвидом Беллом, который нашёл многие любопытные конфигурации и дал им имена.
«Жизнь без смерти» — клеточный автомат, модификация игры «Жизнь». Впервые описан в 1987 году Томмазо Тоффоли и Норманом Марголусом, которые дали ему название «Кляксы» — поскольку многие конфигураций автомата ведут себя подобно растекающемуся чернильному пятну. Известен также под названием «Хлопья».
Pomaranch — поточный шифр, использующий каскадное включение РСЛОС с неравномерным шагом. Шифр участвовал в конкурсе eSTREAM и дошёл до 3 этапа, но, тем не менее, не был выбран для финального портфолио. Шифр был разработан для защиты от атак по сторонним каналам и может быть эффективно реализован в оборудовании для широкого спектра задач.
Хеш-функции на основе клеточных автоматов — разновидность хеш-функций, использующая для вычисления клеточные автоматы. Использование клеточных автоматов обеспечивает высокий уровень параллелизма и, следовательно, позволяет достичь высоких скоростей, что необходимо в условиях ограниченных вычислительных мощностей и жестких требований к энергопотреблению. Хеш-функции на основе клеточных автоматов обладают хорошим лавинным эффектом. Использование клеточных автоматов позволяет добиться устойчивости к атакам временного анализа.
