PPt4Web Хостинг презентаций

Главная / Математика / Определение машины Тьюринга
X Код для использования на сайте:

Скопируйте этот код и вставьте его на свой сайт

X

Чтобы скачать данную презентацию, порекомендуйте, пожалуйста, её своим друзьям в любой соц. сети.

После чего скачивание начнётся автоматически!

Кнопки:

Презентация на тему: Определение машины Тьюринга


Скачать эту презентацию

Презентация на тему: Определение машины Тьюринга


Скачать эту презентацию



№ слайда 1 Определение машины Тьюринга
Описание слайда:

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

№ слайда 2 Машина Тьюринга – абстрактный исполнитель, осуществляющий алгоритмический процес
Описание слайда:

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

№ слайда 3 1) Внешний алфавит А = {a0, a1, …, an} Элемент a0 называется пустой символ В это
Описание слайда:

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

№ слайда 4 2) Внутренний алфавит Q = {q0, q1, …, qm}, {П, Л, С} В любой момент времени маши
Описание слайда:

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

№ слайда 5 3) Внешняя память (лента) Машина имеет ленту, разбитую на ячейки, в каждую из ко
Описание слайда:

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

№ слайда 6 3) Внешняя память (лента) Устройство машины Тьюринга Пустая клетка содержит a0.
Описание слайда:

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

№ слайда 7 4) Каретка (управляющая головка) Каретка машины располагается над некоторой ячей
Описание слайда:

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

№ слайда 8 5) Функциональная схема (программа) Программа машины состоит из команд: Устройст
Описание слайда:

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

№ слайда 9 Замечание 1) В недетерминированной машине может появиться несколько параллельных
Описание слайда:

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

№ слайда 10 К началу работы машины на ленту подается исходный набор данных в виде слова Опис
Описание слайда:

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

№ слайда 11 Описание работы машины Тьюринга Стандартное положение называется начальным (закл
Описание слайда:

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

№ слайда 12 Находясь в не заключительном состоянии, машина совершает шаг, который определяет
Описание слайда:

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

№ слайда 13 Описание работы машины Тьюринга В соответствии с командой qiaj qkal Х выполняютс
Описание слайда:

Описание работы машины Тьюринга В соответствии с командой qiaj qkal Х выполняются следующие действия: 1) Содержимое обозреваемой ячейки aj стирается и в нее записывается символ al (который может совпадать с aj) 2) Машина переходит в новое состояние qk (оно может совпадать с состоянием qi) 3) Каретка перемещается в соответствии с управляемым символом Х {П, Л, С}

№ слайда 14 При переходе машины в заключительное состояние q0 ее работа прекращается На лент
Описание слайда:

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

№ слайда 15 Машинным словом (конфигурацией) машины Тьюринга называется слово вида 1qkal 2, г
Описание слайда:

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

№ слайда 16 Конфигурация 1qkal 2 интерпретируется следующим образом: - машина находится в со
Описание слайда:

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

№ слайда 17 Пример Дана машина Тьюринга с внешним алфавитом А = {a0, 1, * }, алфавитом внутр
Описание слайда:

Пример Дана машина Тьюринга с внешним алфавитом А = {a0, 1, * }, алфавитом внутренних состояний Q = {q0, q1, q2, q3}, и следующей функциональной схемой: Применить машину Тьюринга к слову =11*1, начиная со стандартного начального положения

№ слайда 18 Решение
Описание слайда:

Решение

№ слайда 19 Решение 1) Заменяем содержимое обозреваемой ячейки 1 на а0
Описание слайда:

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

№ слайда 20 Решение 2) Машина переходит в новое состояние q2
Описание слайда:

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

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

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

№ слайда 22 Решение Полное подробное решение
Описание слайда:

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

№ слайда 23 Решение Полное подробное решение
Описание слайда:

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

№ слайда 24 Решение Полное подробное решение
Описание слайда:

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

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

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

№ слайда 26 = 1*11 Ответ: = 111
Описание слайда:

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

№ слайда 27 Литература Игошин В.И. Математическая логика и теория алгоритмов. – М.: Академия
Описание слайда:

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

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

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

Скачать эту презентацию


Презентации по предмету
Презентации из категории
Лучшее на fresher.ru