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

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

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

1. Внешний алфавит - конечное множество символов . В этом алфавите в виде слова кодируется та информация, которая подается в машину. Машина перерабатывает информацию, поданную в виде слова, в новое слово. Обычно символ обозначает пробел.

2. Внутренний алфавит - конечное множество символов . Для любой машины число состояний фиксировано. Два состояния имеют особое назначение - начальное состояние машины, - заключительное состояние (стоп-состояние).

3. Операторы перемещения Т={Л, П, Н}. Л, П, Н – это символы сдвига «влево», «вправо» и «на месте».

4. Бесконечная лента Бесконечная лента характеризует память машины. Она разбита на клеточки. В каждую клеточку может быть записан только один символ из внешнего алфавита.

5. Управляющая головка. Управляющая головка (УГ) передвигается вдоль ленты и может останавливаться напротив какой-либо клетки, т. е. считывать символ

6. Управляющая головка. Управляющая головка (УГ) передвигается вдоль ленты и может останавливаться напротив какой-либо клетки, т. е. считывать символ.

 

 


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

 

7. Программа машины Тьюринга (Р) - совокупность всех команд, Программа представляется в виде таблицы и называется Тьюринговой функциональной схемой.

a0 a1 a2
q1 а0Пq1 a1Пq1 a2Лq2
q2 а1Пq2 a2Нq0 a0Нq0

 

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

(4.9)