Алгоритмы

Алгоритмические машины

1. Машина Тьюринга

-это модель универсального исполнителя алгоритмов обработки символьных последовательностей.

Создана в 30-х годах XX века в связи с появлением такой науки, как теория алгоритмов, английским ученым Аланом Тьюрингом.

Машина Тьюринга обрабатывает символьные последовательности - слова. Всё множество символов образует внешний алфавит машины. Символы записываются в позиции (ячейки) на бесконечной ленте - памяти машины. Использован алфавит десятичной системы счисления.

Автомат - программно управляемое считывающее/записывающее устройство. Головка автомата установлена на определенной ячейке и под управлением программы может перемещаться, считывать и записывать символы.

Внутренний алфавит машины - конечное множество состояний автомата.

Входное слово - слово на ленте, ограниченное пустыми ячейками, на одном из символов которого расположена головка головка автомата, находящегося в начальном состоянии.

Выходное слово - слово, остающееся на ленте после остановки работы автомата, головка которого установилась на одном из символов.

Функциональная схема машины Тьюринга - таблица с занесенными в ячейки командами управления.

Алгоритмическая разрешимость по Тьюрингу:

"Алгоритмически разрешима та задача, для решения которой можно построить машину Тьюринга".


2.Машина Поста

-это ещё одна модель универсального исполнителя алгоритмов обработки символьных последовательностей.

Создана в 30-х годах XX века, практически одновременно с машиной Тьюринга. Создатель - американский ученый Эмиль Пост. Работает с двоичным алфавитом, является частным случаем машины Тьюринга, но представляет больший интерес.

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

Автомат выполняет следующие действия:

-распознать, ячейка пустая или содержит метку;

-стереть метку в текущей ячейке;

-поставить метку в пустую текущую ячейку.

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

Теория об эквивалентности: "Любая алгоритмически разрешимая задача может быть разрешена путем программирования как для машины Тьюринга, так и для машины Поста.