15-§. Структура примитино рекурсивных функций. Реализация алгоритма на машине Тьюринга

Реализация алгоритма на машине Тьюринга.

Машина Тьюринга включает в себя:

1. 
   Внешний алфавит - конечное множество символов . В этом алфавите в виде слова кодируется та информация, которая подается в машину. Машина перерабатывает информацию, поданную в виде слова, в новое слово. Обычно символ Внешний алфавит - конечное множество символов обозначает пробел.
   
2. 
   Внутренний алфавит - конечное множество символов . Для любой машины число состояний фиксировано. Два состояния имеют особое назначение - начальное состояние машины, - заключительное состояние (стоп-состояние).
   
3. 
   Операторы перемещения Т={Л(L), П(S), Н(R)}. Л, П, Н – это символы сдвига «влево», «вправо» и «на месте».
   
4. 
   Бесконечная лента Бесконечная лента характеризует память машины. Она разбита на клеточки. В каждую клеточку может быть записан только один символ из внешнего алфавита.
   
5. 
   Управляющая головка. Управляющая головка (УГ) передвигается вдоль ленты и может останавливаться напротив какой-либо клетки, т. е. считывать символ
   
6. 
   Управляющая головка. Управляющая головка (УГ) передвигается вдоль ленты и может останавливаться напротив какой-либо клетки, т. е. считывать символ.
   

Рис. 15.1. Функциональная схема машины Тьюринга.

Программа машины Тьюринга Р-совокупность всех команд или Таблица в виде.

Таким образом, машина Тьюринга может быть представлена в виде четверки:

(2)
Для описания работы МТ существует 3 способа:
1) система команд вида
2) функциональная таблица;
3) граф (диаграмма) переходов.