Машина Тьюринга как формальная модель алгоритма

Июль 25, 2022

Главная
Информатика
Машина Тьюринга как формальная модель алгоритма

Содержание

2. Неформальное определение машины Тьюринга Машина Тьюринга (МТ) — это автомат, который имеет потенциально бесконечную в обе
3. Формальное определение машины Тьюринга
4. Формальное определение машины Тьюринга
5. В определении машины Тьюринга можно выделить следующие характерные черты
6. Конфигурация МТ
9. Способы представления машины Тьюринга: перечисление множества команд задание машины Тьюринга в виде графа формирование таблицы переходов
10. Правила формирования команд
11. Пример
12. Пример Машина, работающая бесконечно на цепочке из 1 1 -> 1R ε -> ε R
13. Задачи
14. Функции, вычислимые по Тьюрингу
15. Можно на любом алфавите рассматривать машины Тьюринга, которые: никогда не прекращают работу на любых исходных данных
21. Машина Тьюринга с полулентой Рассмотренные нами определения машины Тьюринга использовали бесконечную ленту в обе стороны. Это
24. Скачать презентацию

Слайд 2

Неформальное определение машины Тьюринга
Машина Тьюринга (МТ) — это автомат, который имеет

потенциально бесконечную в обе стороны ленту, считывающую головку и управляющее устройство.
Конечное множество состояний УУ: Q={q1,…, qn}.
Алфавит: Σ= {a1,…,am}.

Слайд 3

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

Слайд 4

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

Слайд 5

В определении машины Тьюринга можно выделить следующие характерные черты

Слайд 6

Конфигурация МТ

Слайд 7

Слайд 8

Слайд 9

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

графа
формирование таблицы переходов

Слайд 10

Правила формирования команд

Слайд 11

Пример

Слайд 12

Пример
Машина, работающая бесконечно на цепочке из 1
1 -> 1R
ε -> ε

Слайд 13

Задачи

Слайд 14

Функции, вычислимые по Тьюрингу

Слайд 15

Можно на любом алфавите рассматривать машины Тьюринга, которые:
никогда не прекращают работу
на любых

исходных данных машина Тьюринга всегда закончит свою работу через конечное число шагов
на некоторых исходных данных машина Тьюринга работает бесконечно, а на некоторых завершает работу

Слайд 16

Слайд 17

Слайд 18

Слайд 19

Слайд 20

Слайд 21

Машина Тьюринга с полулентой
Рассмотренные нами определения машины Тьюринга использовали бесконечную ленту

в обе стороны. Это значит, что на ленте нельзя оставить какие-нибудь данные, которые машина Тьюринга не будет использовать при движении влево или вправо. Ограничим ленту с одной стороны и покажем, что машина Тьюринга с полулентой ( левой или правой ) эквивалентна машина Тьюринга с бесконечной в обе стороны лентой.
Теорема 4.3. Функция, правильно вычислимая на машине Тьюринга с обычной лентой, правильно вычислима на машине Тьюринга с правой полулентой.
Теорема 4.4. Функция, правильно вычислимая на машине Тьюринга с обычной лентой, правильно вычислима на машине Тьюринга с левой полулентой.

Слайд 22