Машина Тьюринга (презентация) презентация к уроку на тему
Машина Тьюринга – абстрактный исполнитель, осуществляющий алгоритмический процесс, созданный для уточнения понятия алгоритма. Это математический объект , а не физическая машина. Предложена Аланом Тьюрингом в 1936 году Машина Тьюринга – это строгое математическое построение, математический аппарат, созданный для решения определённых задач.
Структура и описание машины Тьюринга Машина Тьюринга состоит из: бесконечной ленты, разделенной на ячейки; каретки (читающей и записывающей головки); программируемого автомата (программа в виде таблицы). Автомат каждый раз “видит” только одну ячейку. В зависимости от того, какую букву он видит, а также в зависимости от своего состояния q автомат может выполнять следующие действия: записать новую букву в обозреваемую ячейку; выполнить сдвиг по ленте на одну ячейку вправо/влево или остаться неподвижным; перейти в новое состояние.
1) Внешний алфавит А = < a 0 , a 1 , …, a n >Элемент a 0 называется пустой символ или пустая буква (признак того, что ячейка пуста). В этом алфавите в виде слова кодируется исходный набор данных и результат работы алгоритма. Устройство машины Тьюринга
2) Внутренний алфавит Q = < q 0 , q 1 , …, q m >, < П, Л, Н! >В любой момент времени машина Тьюринга находится в одном из состояний q 0 , q 1 , …, q m При этом: q 1 - начальное состояние (машина начинает работу) q 0 - заключительное состояние (машина закончила работу) Символы < П, Л, Н! >– символы сдвига (вправо, влево, на месте) Устройство машины Тьюринга
Виды команд машины Тьюринга Написать новую букву в обозреваемую ячейку Выполнить сдвиг по ленте на одну ячейку вправо/влево или остаться на месте (П, Л, Н) Перейти в новое состояние. а 0 а 1 … а i … а j q 0 q 1 … a k < ЛПН >q m q i … q j 1 1 1 * 1 1 Указание о смене символа Указание о сдвиге каретки Указание о смене внутреннего состояния
3) Внешняя память (лента) Машина имеет ленту, разбитую на ячейки, в каждую из которых может быть записана только одна буква Устройство машины Тьюринга
3) Внешняя память (лента) Устройство машины Тьюринга Пустая клетка содержит a 0 . В каждый момент времени на ленте записано конечное число непустых букв Лента является конечной, но дополняется в любой момент ячейками слева и справа для записи новых непустых символов. Это соответствует принципу абстракции потенциальной осуществимости
4) Каретка (управляющая головка) Каретка машины располагается над некоторой ячейкой ленты – воспринимает символ, записанный в ячейке В одном такте работы каретка сдвигается на одну ячейку (вправо, влево) или остается на месте Устройство машины Тьюринга
5) Функциональная схема (программа) Программа машины состоит из команд: Устройство машины Тьюринга Для каждой пары ( q i , a j ) программа машины должна содержать одну команду (детерминированная машина Тьюринга)
К началу работы машины на ленту подается исходный набор данных в виде слова Описание работы машины Тьюринга Будем говорить, что непустое слово в алфавите А\ воспринимается машиной в стандартном положении , если: - оно задано в последовательных ячейках ленты, - все другие ячейки пусты, - машина обозревает крайнюю правую ячейку из тех, в которых записано слово
Описание работы машины Тьюринга Стандартное положение называется начальным ( заключительным ), если машина, воспринимающая слово в стандартном положении, находится в начальном состоянии q 1 (стоп-состоянии q 0 )
Находясь в не заключительном состоянии, машина совершает шаг, который определяется текущим состоянием q i и обозреваемым символом a j Описание работы машины Тьюринга
Описание работы машины Тьюринга В соответствии с командой q i a j q k a l Х выполняются следующие действия: 1) Содержимое обозреваемой ячейки a j стирается и в нее записывается символ a l (который может совпадать с a j ) 2) Машина переходит в новое состояние q k (оно может совпадать с состоянием q i ) 3) Каретка перемещается в соответствии с управляемым символом Х
При переходе машины в заключительное состояние q 0 ее работа прекращается На ленте записан результат работы алгоритма – слово в алфавите А\ Описание работы машины Тьюринга
Машинным словом ( конфигурацией ) машины Тьюринга называется слово вида 1 q k a l 2 , где 1 и 2 - слова в алфавите А.
Конфигурация 1 q k a l 2 интерпретируется следующим образом: - машина находится в состоянии q k - каретка обозревает на ленте символ a l - 1 и 2 – это содержимое ленты до и после символа a l
Ситуации неприменимости машины Тьюринга Считается, что машина Тьюринга неприменима к данному входному слову, если в программе нет клеток останова или машина в процессе работы на них не попадает. Например: Машина Тьюринга применима к данному входному слову, если, начав работу над этим входным словом, она рано или поздно дойдёт до одной из клеток останова. Как изменилась программа в примере? а 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
Пример машин Тьюринга Требуется построить машину Тьюринга для решения следующей задачи: во входном слове все буквы «а» заменить на буквы «б» и наоборот. а 0 а б в … я q 1 а 0 Н ! б Л q 1 а Л q 1 в Л q 1 … я Л q 1 у у б а а б р р у б а р а б а б б а а б б а
Реализуйте предложенный алгоритм Машина Тьюринга прибавляет единицу к числу на ленте. Входное слово состоит из цифр целого десятичного числа, записанного в последовательные ячейки на ленте. В начальный момент машина находится против самой правой цифры числа. а 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
Реализуйте предложенный алгоритм На ленте машины Тьюринга содержится последовательность символов «+». Машина Тьюринга каждый второй символ «+» заменяет на «–». Замена начинается с правого конца последовательности. Автомат в состоянии 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 – знак «+» заменяет на « – ».
Пример Дана машина Тьюринга с внешним алфавитом А = < a 0 , 1, * >, алфавитом внутренних состояний Q = < q 0 , q 1 , q 2 , q 3 >, и следующей функциональной схемой: Применить машину Тьюринга к слову =11*1, начиная со стандартного начального положения
Решение 1) Заменяем содержимое обозреваемой ячейки 1 на а 0
Решение 2) Машина переходит в новое состояние q 2
Решение 3) Каретка перемещается влево
Решение Полное подробное решение
Решение Полное подробное решение
Решение Полное подробное решение
Решение Решение, записанное с помощью конфигураций (в строчку)
= 1*11 Ответ: = 111
Литература Игошин В.И. Математическая логика и теория алгоритмов. – М.: Академия, 2008. - 448 с. Лихтарников Л.М., Сукачева Т.Г. Математическая логика. Курс лекций. Задачник-практикум и решения. – СПб.: Лань, 1999. - 288 с. Ильиных А.П. Теория алгоритмов. Учебное пособие. – Екатеринбург, 2006. - 149 с.
Люди могут вести себя по-разному в одинаковых ситуациях, и этим они принципиально отличаются от машин.
По теме: методические разработки, презентации и конспекты
Тест "Машина Тьюринга"Тест по УД "Теория алгоритмов" "Машина ТЬюринга".
презентация "Машинные швы"Материал можно использовать для проведения учебных занятий по швейным профессиям.