Глоссарий
Абстрактные вычислительные машины

Абстрактная вычислительная машина
Абстрактная вычислительная машина - теоретическое построение, с помощью которого вводится строгое, математическое определение алгоритма.

Автомат
Автомат - разновидность абстрактной вычислительной машины, которая определяется:
- множеством входных и выходных сигналов;
- множеством состояний;
- функцией, задающей переходы из одних состояний в другие; и
- функцией, определяющей выходные сигналы в зависимости от входного сигнала и текущего состояния.
Автомат предназначен для формальной переработки последовательностей символов.

Конечный автомат
англ.Finite-state machine
Конечный автомат - математическая модель устройства с конечной памятью. Конечный автомат перерабатывает множество входных дискретных сигналов в множество выходных сигналов. Различают синхронные и асинхронные конечные автоматы.

Машина Поста
Машина Поста - математическое построение, предназначенное для уточнения понятия алгоритма. Машина Поста состоит:
- из неограниченной в обе стороны ленты, разделенной на ячейки;
- из головка чтения/записи, которая может перемещаться вдоль ленты и управляется программой на специальном языке из шести команд.
Доказано, что классы алгоритмов, представленных в форме машины Поста, и класс алгоритмов, представленных в форме машины Тьюринга, совпадают.

Машина Тьюринга
Машина Тьюринга - математическое построение, предназначенное для уточнения понятия алгоритма.
Машина Тьюринга состоит:
- из неограниченной в обе стороны ленты, разделенной на ячейки;
- из головка чтения/записи, которая может перемещаться вдоль ленты.
Программа для машины Тьюринга, задается в виде таблицы, определяющей команды для головки.

Нормальный алгоритм Маркова
Нормальный алгоритм Маркова - математическое построение, предназначенное для уточнения понятия алгоритм. Нормальный алгоритм Маркова:
- задается алфавитом и нормальной схемой подстановок, выполняемых по заранее определенной схеме;
- определяет преобразование строк.
Доказано, что класс нормальных алгоритмов Маркова и класс алгоритмов, представленных в форме машины Тьюринга, совпадают.

Тезис Тьюринга
Тезис Тьюринга - принимаемое без доказательства фундаментальное положение теории алгоритмов, согласно которому всякий алгоритм представим в форме машины Тьюринга.

[ 05-05-2024 www.glossary.ru]