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

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

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

Машина Тьюринга преобразует какие-либо объекты (например, строку символов, принадлежащих некоторому алфавиту) в некоторый искомый результат. При этом, хотя слова алгоритма машины Тьюринга могут иметь некоторый смысл, для теории алгоритмов это несущественно.

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

А – внешний алфавит машины Тьюринга.

Некоторый алфавит Р=р₁, р₂, …р_n, характеризующий состояние машины в конкретный момент времени, называют внутренним алфавитом.

Состояние движения ленты описывается множеством возможных состояний -¥, …, d_j, …, d₀, d₁, …, +¥.

Опишем принцип работы машины Тьюринга.

1) Чтение a_i из ячейки d₀, на которой позиционируется головка чтения/записи (R/W Head). Состояние машины в этот момент определяется p_j.

Начальный кортеж: {a_i, d₀, p₀}

2) В зависимости от значений a_i и p_j изменяется поведение машины:

{a_x, d_y, p_z}

Данный кортеж означает: записать вместо a_i символ a_х, переместить головку чтения/записи в позицию d_y, блоку управления перейти в состояние p_z.

3) Если после второго шага состояние машины Тьюринга описывается исходным кортежем, то машина останавливается. Иначе – повтор пункта 2.

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

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