Алгоритмы
Алгоритмические машины
-это модель универсального исполнителя алгоритмов обработки символьных последовательностей.
Создана в 30-х годах XX века в связи с появлением такой науки, как теория алгоритмов, английским ученым Аланом Тьюрингом.
Машина Тьюринга обрабатывает символьные последовательности - слова. Всё множество символов образует внешний алфавит машины. Символы записываются в позиции (ячейки) на бесконечной ленте - памяти машины. Использован алфавит десятичной системы счисления.
Автомат - программно управляемое считывающее/записывающее устройство. Головка автомата установлена на определенной ячейке и под управлением программы может перемещаться, считывать и записывать символы.
Внутренний алфавит машины - конечное множество состояний автомата.
Входное слово - слово на ленте, ограниченное пустыми ячейками, на одном из символов которого расположена головка головка автомата, находящегося в начальном состоянии.
Выходное слово - слово, остающееся на ленте после остановки работы автомата, головка которого установилась на одном из символов.
Функциональная схема машины Тьюринга - таблица с занесенными в ячейки командами управления.
Алгоритмическая разрешимость по Тьюрингу:
"Алгоритмически разрешима та задача, для решения которой можно построить машину Тьюринга".
2.Машина Поста
-это ещё одна модель универсального исполнителя алгоритмов обработки символьных последовательностей.
Создана в 30-х годах XX века, практически одновременно с машиной Тьюринга. Создатель - американский ученый Эмиль Пост. Работает с двоичным алфавитом, является частным случаем машины Тьюринга, но представляет больший интерес.
Как и в Машине Тьюринга, имеется бесконечная информационная лента, разделенная на позиции - ячейки. В каждой из них может либо стоять метка, либо отсутствовать. Вдоль ленты двигается головка автомата, которая может перемещаться шагами.
Автомат выполняет следующие действия:
-распознать, ячейка пустая или содержит метку;
-стереть метку в текущей ячейке;
-поставить метку в пустую текущую ячейку.
Назначение машины - производить любые преобразования на информационной ленте. Исходное её состояние можно рассматривать как исходные данные задачи, а конечное - как результат решения. Кроме того, в исходные данные входит положение головки автомата.
Теория об эквивалентности: "Любая алгоритмически разрешимая задача может быть разрешена путем программирования как для машины Тьюринга, так и для машины Поста.