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

Герасимова Светлана Александровна

Для дисциплины "Теория алгоритмов"

Скачать:

ВложениеРазмер
Office presentation icon mashina_tyuringa.ppt2.03 МБ

Предварительный просмотр:


Подписи к слайдам:

Слайд 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

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


По теме: методические разработки, презентации и конспекты

Тест "Машина Тьюринга"

Тест  по УД "Теория алгоритмов" "Машина ТЬюринга"...

презентация "Машинные швы"

Материал можно использовать для проведения учебных занятий по швейным профессиям...

Презентация Детали машин

Для организаторов поп...

Презентация Детали машин

Для организаторов поп...

Машина Тьюринга (презенация)

Машина Тьюринга (презенация)...

Презентация на тему: В чем смысл эквивалентности машин Тьюринга и Поста и нормальных алгоритмов Маркова?

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