Машина Тьюринга. Теория алгоритмов, формальных языков, грамматик и автоматов презентация
Содержание
- 3. Типы алгоритмов. История создания Интенсивный поиск универсального уточнения алгоритма предложил примерно
- 4. Алгоритмические машины (АМ) имеют единственный процессор, выполняющий небольшой набор очень примитивных
- 5. Основные АМ Машина Тьюринга (МТ) предложена Тьюрингом в 1937 г. Машина
- 7. Автор
- 10. Структура алгоритма (составляющие алгоритма) Процессорная структура. (Исполнитель алгоритма).
- 11. Составляющие структуры Информационная структура алгоритма (ИСА). Структура функций есть описание конструирования
- 12. Интерпретация МТ. Процессор – в МТ называется управляющей головкой (УГ).
- 13. МТ Тьюринг назвал свое абстрактное механическое устройство "универсальной машиной", поскольку она
- 15. Абстрактная модель машины Тьюринга МТ = <Q, D, P, q0,
- 16. МТ = <Q, D, P, q0, qкон>
- 19. Машина Тьюринга состоит из трех частей: ленты, считывающе-записывающей головки и логического
- 20. Головка неподвижна, а лента передвигается относительно нее вправо или влево.
- 21. В каждую ячейку ленты может быть записан лишь один символ.
- 22. Система исполняемых головкой команд предельно проста: Система исполняемых головкой команд
- 23. Команды перемещений ленты L («Left») на ячейку влево, R («Right»)
- 24. Элементарный шаг (такт) работы машины Тьюринга головка считывает символ из обозреваемой
- 25. Определение Конфигурация машины- совокупность состояний всех ячеек ленты, состояния УУ и
- 26. Пример Пусть начальной является конфигурация 1q11111. Такт 1 Обозревается 1,
- 27. Отличия читающего автомата с выходом и МТ
- 28. Тезис Тьюринга Всякий алгоритм может быть задан посредством тьюринговой функциональной
- 29. Отличия ЭВМ и машины Тьюринга Главное отличие машины Тьюринга от ЭВМ
- 30. Этапы решения задачи
- 31. Представление машины Тьюринга совокупностью команд Совокупность всех команд, которые может
- 33. Представление машины Тьюринга графом При представлении машины Тьюринга посредством графа
- 34. Представление машины Тьюринга таблицей соответствия
- 36. Пример 1. Построить машину Тьюринга, которая правильно вычисляет функцию f(x) =x+1
- 39. Построение МТ Для того чтобы доказать вычислимость функции, а в дальнейшем
- 40. Операции над машинами Тьюринга 1. Композиция машин Тьюринга. Пусть машины Т1
- 41. Операции над МТ
- 42. Операции над МТ
- 43. Алгоритмическая машина Поста (МП) — абстрактная вычислительная машина, предложенная Эмилем
- 44. За один такт (его называют шагом) головка может сдвинуться на одну
- 45. Структура команды Каждая команда имеет следующую структуру xKy, x –
- 46. Система команд машины
- 47. Система команд машины
- 48. Пример
- 49. Комментарий к примеру Последовательное исполнение команд 1 и 2 приводит к
- 50. Если данные условия не выполняются, происходит безрезультатная остановка машины, т.е. остановка
- 51. Функции, вычислимые алгоритмом алгоритм не определяется формально, а существует как
- 52. Вычислимые функции
- 56. Рекурсивные функции Рекурсивные функции на множестве натуральных чисел были предложены Клини
- 57. Рекурсия Пример: определение факториала. n!=1*2*3*...*n. Н.Вирт отмечает, что "...мощность рекурсии
- 58. Рекурсивные функции Рекурси́вная фу́нкция (от лат. recursio — возвращение) — это числовая функция числового аргумента, которая
- 59. Свойства рекурсивных алгоритмов: Правильный рекурсивный алгоритм не должен создавать бесконечную последовательность
- 60. Примитивная рекурсия Оператор примитивной рекурсии Rn позволяет определить (n+1) - местную
- 63. Исчисления. Исчисление функций, вычисляемых на множестве натуральных чисел предложено Эрбраном
- 65. Метапрограммирование Метапрограммирование предусматривает написание программ, которые работают с другими программами в
- 66. Ассоциативное исчисление
- 70. Скачать презентацию
Слайды и текст этой презентации
Скачать презентацию на тему Машина Тьюринга. Теория алгоритмов, формальных языков, грамматик и автоматов можно ниже: