Презентация, доклад по теме Машина Тьюринга

понятия алгоритма.

Это математический объект, а не физическая машина.

Предложена Аланом Тьюрингом в 1936 году

Машина Тьюринга – это строгое математическое построение, математический аппарат, созданный для решения определённых задач.

бесконечной ленты, разделенной на ячейки;
каретки (читающей и записывающей головки);
программируемого автомата (программа в виде таблицы).

 Автомат каждый раз “видит” только одну ячейку. В зависимости от того, какую букву он видит, а также в зависимости от своего состояния q автомат может выполнять следующие действия:
записать новую букву в обозреваемую ячейку;
выполнить сдвиг по ленте на одну ячейку вправо/влево или остаться неподвижным;
перейти в новое состояние.

символ или пустая буква (признак того, что ячейка пуста).

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

Устройство машины Тьюринга

любой момент времени машина Тьюринга находится в одном из состояний q0, q1, …, qm

При этом: q1 - начальное состояние (машина начинает работу)
q0 - заключительное состояние (машина закончила работу)
Символы {П, Л, Н!} – символы сдвига (вправо, влево, на месте)

Устройство машины Тьюринга

ленте на одну ячейку вправо/влево или остаться на месте (П, Л, Н)
Перейти в новое состояние.

Указание о смене символа

Указание о сдвиге каретки

Указание о смене внутреннего состояния

из которых может быть записана только одна буква

Устройство машины Тьюринга

момент времени на ленте записано конечное число непустых букв

Лента является конечной, но дополняется в любой момент ячейками слева и справа для записи новых непустых символов.

Это соответствует принципу абстракции потенциальной осуществимости

воспринимает символ, записанный в ячейке

В одном такте работы каретка сдвигается на одну ячейку (вправо, влево) или остается на месте

Устройство машины Тьюринга

пары (qi, aj) программа машины должна содержать одну команду (детерминированная машина Тьюринга)

виде слова α

Описание работы машины Тьюринга

Будем говорить, что непустое слово α в алфавите А\{a0} воспринимается машиной в стандартном положении, если:
- оно задано в последовательных ячейках ленты,
- все другие ячейки пусты,
- машина обозревает крайнюю правую ячейку из тех, в которых записано слово α

слово в стандартном положении, находится в начальном состоянии q1 (стоп-состоянии q0)

состоянием qi и обозреваемым символом aj

Описание работы машины Тьюринга

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

1) Содержимое обозреваемой ячейки aj стирается и в нее записывается символ al (который может совпадать с aj)

2) Машина переходит в новое состояние qk (оно может совпадать с состоянием qi)

3) Каретка перемещается в соответствии с управляемым символом Х ∈ {П, Л, Н!}

записан результат работы алгоритма – слово β в алфавите А\{a0}

Описание работы машины Тьюринга

α1 и α2 - слова в алфавите А.

каретка обозревает на ленте символ al
- α1 и α2 – это содержимое ленты до и после символа al

слову, если в программе нет клеток останова или машина в процессе работы на них не попадает.
Например:

Машина Тьюринга применима к данному входному слову, если, начав работу над этим входным словом, она рано или поздно дойдёт до одной из клеток останова. Как изменилась программа в примере?

входном слове все буквы «а» заменить на буквы «б» и наоборот.

у

→

у

б

→

а

а

→

б

р

→

р

у

б

а

р

а

б

а

→

б

б

→

а

а

б

б

а

слово состоит из цифр целого десятичного числа, записанного в последовательные ячейки на ленте. В начальный момент машина находится против самой правой цифры числа.

Тьюринга каждый второй символ «+» заменяет на «–». Замена начинается с правого конца последовательности. Автомат в состоянии q1 обозревает один из символов указанной последовательности.

q1 – машина ищет правый конец числа;
q2 – пропускает знак «+», при достижении конца последовательности – останов;
q3 – знак «+» заменяет на «–».

}, алфавитом внутренних состояний Q = {q0, q1, q2, q3}, и следующей функциональной схемой:

Применить машину Тьюринга к слову α=11*1, начиная со стандартного начального положения

- 448 с.
Лихтарников Л.М., Сукачева Т.Г. Математическая логика. Курс лекций. Задачник-практикум и решения. – СПб.: Лань, 1999. - 288 с.
Ильиных А.П. Теория алгоритмов. Учебное пособие. – Екатеринбург, 2006. - 149 с.

принципиально отличаются от машин.