LOGO Определение машины Тьюринга. Машина Тьюринга – абстрактный исполнитель, осуществляющий алгоритмический процесс Это математический объект, а не физическая. - презентация

1 LOGO Определение машины Тьюринга

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

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

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

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

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

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

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

9 Замечание 1) В недетерминированной машине может появиться несколько параллельных вычислительных процессов 2) Разные машины Тьюринга отличаются своими программами Для каждого алгоритма создается своя машина Тьюринга, точнее ее программа

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

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

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

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

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

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

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

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

18 Решение

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

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

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

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

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

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

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

26 = 1*11 Ответ: = 111

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

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