Машина Тьюринга (презентация)
презентация к уроку на тему

Слайд 1

Слайд 2

Машина Тьюринга – абстрактный исполнитель, осуществляющий алгоритмический процесс, созданный для уточнения понятия алгоритма. Это математический объект , а не физическая машина. Предложена Аланом Тьюрингом в 1936 году Машина Тьюринга – это строгое математическое построение, математический аппарат, созданный для решения определённых задач.

Слайд 3

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

Слайд 4

1) Внешний алфавит А = { a 0 , a 1 , …, a n } Элемент a 0 называется пустой символ или пустая буква (признак того, что ячейка пуста). В этом алфавите в виде слова кодируется исходный набор данных и результат работы алгоритма. Устройство машины Тьюринга

Слайд 5

2) Внутренний алфавит Q = { q 0 , q 1 , …, q m }, { П, Л, Н! } В любой момент времени машина Тьюринга находится в одном из состояний q 0 , q 1 , …, q m При этом: q 1 - начальное состояние (машина начинает работу) q 0 - заключительное состояние (машина закончила работу) Символы { П, Л, Н! } – символы сдвига (вправо, влево, на месте) Устройство машины Тьюринга

Слайд 6

Виды команд машины Тьюринга Написать новую букву в обозреваемую ячейку Выполнить сдвиг по ленте на одну ячейку вправо/влево или остаться на месте (П, Л, Н) Перейти в новое состояние. а 0 а 1 … а i … а j q 0 q 1 … a k { ЛПН } q m q i … q j 1 1 1 * 1 1 Указание о смене символа Указание о сдвиге каретки Указание о смене внутреннего состояния

Слайд 7

3) Внешняя память (лента) Машина имеет ленту, разбитую на ячейки, в каждую из которых может быть записана только одна буква Устройство машины Тьюринга

Слайд 8

3) Внешняя память (лента) Устройство машины Тьюринга Пустая клетка содержит a 0 . В каждый момент времени на ленте записано конечное число непустых букв Лента является конечной, но дополняется в любой момент ячейками слева и справа для записи новых непустых символов. Это соответствует принципу абстракции потенциальной осуществимости

Слайд 9

4) Каретка (управляющая головка) Каретка машины располагается над некоторой ячейкой ленты – воспринимает символ, записанный в ячейке В одном такте работы каретка сдвигается на одну ячейку (вправо, влево) или остается на месте Устройство машины Тьюринга

Слайд 10

5) Функциональная схема (программа) Программа машины состоит из команд: Устройство машины Тьюринга Для каждой пары ( q i , a j ) программа машины должна содержать одну команду (детерминированная машина Тьюринга)

Слайд 11

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

Слайд 12

Описание работы машины Тьюринга Стандартное положение называется начальным ( заключительным ), если машина, воспринимающая слово в стандартном положении, находится в начальном состоянии q 1 (стоп-состоянии q 0 )

Слайд 13

Находясь в не заключительном состоянии, машина совершает шаг, который определяется текущим состоянием q i и обозреваемым символом a j Описание работы машины Тьюринга

Слайд 14

Описание работы машины Тьюринга В соответствии с командой q i a j  q k a l Х выполняются следующие действия: 1) Содержимое обозреваемой ячейки a j стирается и в нее записывается символ a l (который может совпадать с a j ) 2) Машина переходит в новое состояние q k (оно может совпадать с состоянием q i ) 3) Каретка перемещается в соответствии с управляемым символом Х  { П, Л, Н! }

Слайд 15

При переходе машины в заключительное состояние q 0 ее работа прекращается На ленте записан результат работы алгоритма – слово  в алфавите А\ {a 0 } Описание работы машины Тьюринга

Слайд 16

Машинным словом ( конфигурацией ) машины Тьюринга называется слово вида  1 q k a l  2 , где  1 и  2 - слова в алфавите А.

Слайд 17

Конфигурация  1 q k a l  2 интерпретируется следующим образом: - машина находится в состоянии q k - каретка обозревает на ленте символ a l -  1 и  2 – это содержимое ленты до и после символа a l

Слайд 18

Ситуации неприменимости машины Тьюринга Считается, что машина Тьюринга неприменима к данному входному слову, если в программе нет клеток останова или машина в процессе работы на них не попадает. Например: Машина Тьюринга применима к данному входному слову, если, начав работу над этим входным словом, она рано или поздно дойдёт до одной из клеток останова. Как изменилась программа в примере? а 0 0 1 q 1 1П q 1 0П q 1 1П q 1 а 0 0 1 q 1 1Н q 0 0П q 1 1П q 1

Слайд 19

Пример машин Тьюринга Требуется построить машину Тьюринга для решения следующей задачи: во входном слове все буквы «а» заменить на буквы «б» и наоборот. а 0 а б в … я q 1 а 0 Н ! б Л q 1 а Л q 1 в Л q 1 … я Л q 1 у  у б  а а  б р  р у б а р а б а  б б  а а б б а

Слайд 20

Реализуйте предложенный алгоритм Машина Тьюринга прибавляет единицу к числу на ленте. Входное слово состоит из цифр целого десятичного числа, записанного в последовательные ячейки на ленте. В начальный момент машина находится против самой правой цифры числа. а 0 0 1 2 3 4 … 7 8 9 q 1 1Н q 0 1Н q 0 2Н q 0 3Н q 0 4Н q 0 5Н q 0 … 8Н q 0 9Н q 0 0Л q 1

Слайд 21

Реализуйте предложенный алгоритм На ленте машины Тьюринга содержится последовательность символов «+». Машина Тьюринга каждый второй символ «+» заменяет на «–». Замена начинается с правого конца последовательности. Автомат в состоянии q 1 обозревает один из символов указанной последовательности. а 0 + – q 1 а 0 Л q 2 + П q 1 q 2 а 0 Н ! + Л q 3 q 3 а 0 Н ! – Л q 2 q 1 – машина ищет правый конец числа; q 2 – пропускает знак «+», при достижении конца последовательности – останов; q 3 – знак «+» заменяет на « – ».

Слайд 22

Пример Дана машина Тьюринга с внешним алфавитом А = { a 0 , 1, * } , алфавитом внутренних состояний Q = { q 0 , q 1 , q 2 , q 3 }, и следующей функциональной схемой: Применить машину Тьюринга к слову  =11*1, начиная со стандартного начального положения

Слайд 23

Решение

Слайд 24

Решение 1) Заменяем содержимое обозреваемой ячейки 1 на а 0

Слайд 25

Решение 2) Машина переходит в новое состояние q 2

Слайд 26

Решение 3) Каретка перемещается влево

Слайд 27

Решение Полное подробное решение

Слайд 28

Решение Полное подробное решение

Слайд 29

Решение Полное подробное решение

Слайд 30

Решение Решение, записанное с помощью конфигураций (в строчку)

Слайд 31

 = 1*11 Ответ:  = 111

Слайд 32

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

Слайд 33

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