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