Разделы презентаций
- Разное
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Машина Тьюринга
Содержание
- 1. Машина Тьюринга
- 2. Машина Тьюринга – абстрактный исполнитель, осуществляющий алгоритмический
- 3. Устройство машины Тьюринга Машина Тьюринга включает в себя:Внешний алфавит;Внутренний алфавит;Внешняя память (лента);Каретка (управляющая головка);Функциональная схема (программа);
- 4. 1) Внешний алфавит А = {a0, a1, …,
- 5. 2) Внутренний алфавит Q = {q0, q1, …,
- 6. 3) Внешняя память (лента)Машина имеет ленту, разбитую
- 7. 4) Каретка (управляющая головка)Каретка машины располагается над
- 8. 5) Функциональная схема (программа)Программа машины состоит из
- 9. Описание работы машины ТьюрингаСтандартное положение называется начальным
- 10. Описание работы машины ТьюрингаВ соответствии с командой
- 11. При переходе машины в заключительное состояние q0
- 12. Машинным словом (конфигурацией) машины Тьюринга называется слово
- 13. Конфигурация α1qkal α2 интерпретируется следующим образом:- машина
- 14. ПримерДана машина Тьюринга с внешним алфавитом А
- 15. Решение
- 16. Решение1) Заменяем содержимое обозреваемой ячейки 1 на а0
- 17. Решение2) Машина переходит в новое состояние q2
- 18. Решение3) Каретка перемещается влево
- 19. РешениеПолное подробное решение
- 20. РешениеПолное подробное решение
- 21. РешениеПолное подробное решение
- 22. РешениеРешение, записанное с помощью конфигураций (в строчку)
- 23. α = 1*11Ответ: β = 111
- 24. Скачать презентанцию
Машина Тьюринга – абстрактный исполнитель, осуществляющий алгоритмический процессЭто математический объект, а не физическая машинаПредложена Аланом Тьюрингом в 1936 году
Слайды и текст этой презентации
Слайд 2Машина Тьюринга – абстрактный исполнитель, осуществляющий алгоритмический процесс
Это математический объект,
а не физическая машина
Слайд 3Устройство машины Тьюринга
Машина Тьюринга включает в себя:
Внешний алфавит;
Внутренний алфавит;
Внешняя память
(лента);
Каретка (управляющая головка);
Функциональная схема (программа);
Слайд 4
1) Внешний алфавит
А = {a0, a1, …, an}
Элемент a0 называется
пустой символ
В этом алфавите в виде слова кодируется исходный набор
данных и результат работы алгоритмаУстройство машины Тьюринга
Слайд 5
2) Внутренний алфавит
Q = {q0, q1, …, qm}, {П, Л,
С}
В любой момент времени машина М находится в одном из
состояний q0, q1, …, qmПри этом: q1 - начальное состояние
q0 - заключительное состояние
Символы {П, Л, С} – символы сдвига (вправо, влево, на месте)
Устройство машины Тьюринга
Слайд 6
3) Внешняя память (лента)
Машина имеет ленту, разбитую на ячейки, в
каждую из которых может быть записана только одна буква
Устройство машины
ТьюрингаПустая клетка содержит a0.
В каждый момент времени на ленте записано конечное число непустых букв
Слайд 7
4) Каретка (управляющая головка)
Каретка машины располагается над некоторой ячейкой ленты
– воспринимает символ, записанный в ячейке
Устройство машины Тьюринга
Слайд 8
5) Функциональная схема (программа)
Программа машины состоит из команд:
Устройство машины Тьюринга
Для
каждой пары (qi, aj) программа машины должна содержать одну команду.
Слайд 9
Описание работы машины Тьюринга
Стандартное положение называется начальным (заключительным), если машина,
воспринимающая слово в стандартном положении, находится в начальном состоянии q1
(стоп-состоянии q0)
Слайд 10
Описание работы машины Тьюринга
В соответствии с командой qiaj → qkal
Х выполняются следующие действия:
1) Содержимое обозреваемой ячейки aj стирается и
в нее записывается символ al (который может совпадать с aj)2) Машина переходит в новое состояние qk (оно может совпадать с состоянием qi)
3) Каретка перемещается в соответствии с управляемым символом Х ∈ {П, Л, С}
Слайд 11При переходе машины в заключительное состояние q0 ее работа прекращается
На
ленте записан результат работы алгоритма – слово β в алфавите
А\{a0}Описание работы машины Тьюринга
Слайд 12
Машинным словом (конфигурацией) машины Тьюринга называется слово вида α1qkal α2,
где α1 и α2 - слова в алфавите А.
Слайд 13Конфигурация α1qkal α2 интерпретируется следующим образом:
- машина находится в состоянии
qk
- каретка обозревает на ленте символ al
- α1 и
α2 – это содержимое ленты до и после символа al
Слайд 14Пример
Дана машина Тьюринга с внешним алфавитом А = {a0, 1,
* }, алфавитом внутренних состояний Q = {q0, q1, q2,
q3}, и следующей функциональной схемой:Применить машину Тьюринга к слову α=11*1, начиная со стандартного начального положения
