Детерминированная машина Тьюринга (ДМТ)Рассмотрим "школьное" определение алгоритма.
1. Алгоритм – любой алгоритм задается последовательностью инструкций.
2. Алгоритм выполняется детерминировано, то есть для одинаковых данных выполняются одинаковые действия.
3. Должен существовать вычислитель, способный выполнить указания в алгоритм инструкции.
4. Вычислитель должен иметь средства для хранения и отображения информации
Детерминированная машина Тьюринга есть ни что иное, как модель абстрактного вычислителя, способного выполнить указанные в алгоритме инструкции.
Опр. 5. ДМТ имеет бесконечную ленту, управляющее устройство и считывающее/пишущую головку. Лента разделена на ячейки, в каждой ячейке записан или пустой символ
, или символ некоторого конечного алфавита. В каждый момент на ленте может быть только конечное число непустых символов.
Управляющее устройство находится в одном из конечного множества состояний, среди которых выделяются начальное
и заключительное
. Перед началом работы ДМТ находится в начальном состоянии
, попав в заключительное
, останавливается.
На одном такте работы ДМТ производит следующие действия:
1. Считывает символ из текущей ячейки.
2. Записывает вместо него новый.
3. Остаётся на месте или сдвигается в соседнюю ячейку.
4. В зависимости от текущего состояния и прочитанного символа переходит в новое состояние.
$$Îáîçíà÷èì \ A =\{a_1, \ldots, a_n\} \ - \ ìíîæåñòâî \ ñèìâîëîâ; \\
Q =\{q_1, \ldots, q_n\}\ - \ ìíîæåñòâî \ ñîñòîÿíèé;\ d_k \ \ êîìàíäà \ ñäâèãà \ \{L, R, E\}$$.
Тогда один такт работы ДМТ записывается одной командой
Конечная система команд называется ДМТ-программой. Таким образом, алгоритм, детерминированная машина Тьюринга и ДМТ-программа разные названия, обозначающие алгоритм.
Тезис ТьюрингаВсякий алгоритм может быть реализован машиной Тьюринга.Тезис - не аксиома и не теорема, просто другое определение алгоритма. Пример 1. На ленте записано слово из 0 и 1. Составить систему команд для машины Тьюринга, которая заменяет 0 на 1, а 1 на 0.
Решение. Изобразим систему команд с помощью графа (диаграммы) переходов.
ДМТ идёт по слову слева направо, переписывая нули и единицы, доходит до пустого символа
и двигается налево, как кот учоный, пока не вернётся на первый непустой символ.
(Заметим, что стандартное заключительное состояние любой ДМТ - останов на первом непустом символе. Это нужно для композиций машин Тьюринга.)