Машина Тьюринга

При написании этого раздела использовались материалы курсы лекций [1].

Неформально, машина Тьюринга (далее МТ) представляет собой автомат с конечным числом состояний и неограниченной памятью, представленной бесконечной лентой (в общем случае набором лент). Лента поделена на бесконечное число ячеек, и на ней выделена стартовая ячейка.

В каждой ячейке ленты может быть записан только один символ из некоторого конечного алфавита , где предусмотрен символ для обозначения пустой ячейки.

На ленте имеется головка чтения-записи, и она подсоединены к «управляющему модулю» МТ — автомату с конечным множеством состояний .

Имеется выделенное стартовое состояние и состояние завершения .

Перед запуском МТ находится в состоянии , а головка позиционируется на нулевой ячейке ленты.

На каждом шаге головка считывает информацию из текущей ячейки и посылают ее управляющему модулю МТ. В зависимости от этих символов и собственного состояния, управляющий модуль производит следующие операции:

1) посылает головке символ для записи в текущую ячейку каждой ленты;

2) посылает головке одну из команд «LEFT», «RIGHT», «STAY»;

3) выполняет переход в новое состояние (которое, впрочем, может совпадать с предыдущим).

На рисунке 1 представлена схема машины Тьюринга.

Определение 4. Машина Тьюринга — это набор

· - алфавит, - пустой символ;

· - конечное множество состояний, , - выделенные состояния : запуск машины и завершения работы;

· - произвольные отображения:

- задает новое состояние,

-символ для записи на ленте,

- определяет перемещение головки.

Таким образом, машина Тьюринга задается таблицей команд размером , задающей правила работы машины в соответствии с функциями . Если к словарю А добавить пустой символ , то получим расширенный словарь .

Под входом для МТ подразумевается слово состоящее из символов словаря , записанного справа от стартовой позиции на ленте МТ. Договоримся, что входное слово не содержит пустых символов - иначе возникнут технические сложности, как определить, где кончается входное слово и т.п.

Результатом работы МТ над некотором входном слове X считается слово, записанное на ленте после остановки МТ.

Таким образом память МТ – конечное множество состояний (внутренняя память) и лента (внешняя память).

Данные МТ – слова в алфавите машины. Через обозначим исходное слово.

Элементарные шаги машины – считывание и запись символов, сдвиг головки на ячейку вправо, влево, на месте, а также переход управляющего устройства в следующее состояние.

«Программа управления» МТ это задание записанное системой правил (команд) вида:

(- направление сдвига головки )

«Программу управления» можно задать таблицей, строки которой соответствуют состояниям МТ, столбцам – входные символы, а на пересечении строки и столбца записана тройка символов .

Альтернативным способом описания «программы управления» является диаграмма переходов, представленная в виде ориентированного графа, вершинами которого являются состояния , дуги помечены переходами вида .

Полное состояние МТ, по которому однозначно можно определить ее дальнейшее поведение, определяется ее внутренним состоянием, состоянием ленты и положением головки.

Пример 1. Сложение. Рассмотрим задачу сложения 2 натуральных чисел. Договоримся представлять натуральные числа в единичном (унарном) коде , например, для числа х справедливо: . Положим, что для всех числовых функций либо .

Тогда числовая функция правильно вычислима по Тьюрингу, если существует машина Т такая, что , когда и Т работает бесконечно, начиная с , когда не вычислима.

Рассмотрим сложение 2 чисел a и b () это слово необходимо переработать в , т.е. удалить разделитель и сдвинуть одно из слагаемых, скажем первое, к другому.