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

Одно из уточнений понятий алгоритма было дано Постом и А.Тьюрингом независимо друг от друга в 1936-1937гг. Основная мысль их заключалась в том, что алгоритмические процессы – это процессы, которые может свершить подходящим образом устроенная ”машина”. Ими были описаны гипотетические (условные) устройства, которые получили название «Машина Поста»(МП) и «Машина Тьюринга»(МТ). Так как в них много общего, то впоследствии их стали называть машинами Тьюринга.

Машина Тьюринга состоит из следующих частей:

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

2. Считывающей головки – чувствительного специального элемента, способного обозревать содержимое ячеек. Лента может перемещаться вдоль головки так, что в каждый момент времени головка обозревает одну ячейку.

3. Управляющего устройства (УУ), которое в каждый момент времени находится в некотором состоянии. Число состояний конечно. Одно из состояний называется заключительным.

Множество символов, которые записываются в информационной ленте {S₁,S₂,….,S_m}, составляют внешний алфавит МТ.

При этом S₁ соответствует пустому символу.

Множество состояний, в которых может находиться УУ, обозначим {q₁,q₂,…,q_n}. Среди состояний одно будет соответствовать значительному, при котором МТ останавливается.

Кроме того, УУ вырабатывает три команды на перемещение ленты: П, Л, Н, где

П – обозревать соседнюю справа ячейку;

Л – обозревать соседнюю слева ячейку;

Н – продолжать обозревать ту же ячейку.

Совокупность символов {q₁,q₂,…,q_n} и {П,Л,Н} образуют внутренний алфавитМТ.

Работа машины происходит в дискретном времени. В каждый момент времени МТ, находясь в состоянии q_i, обозревает на ленте символ S_k, затем переходит в состояние q_j, заменяет S_k на символ S_l и передвигает ленту (либо нет) на одну ячейку.

Считывающая головка и управляющее устройство образуют логический блок, который представляет из собой (2,3) - полюсник.

q_iS_k q_jS_l П(Л,Н)

Таким образом, команда МТ задается пятеркой символов: q_i, S_k, q_j,S_l, П, а сам ЛБ является по своей сути конечным автоматом.

Структура МТ имеет следующий вид:

Q - ячейка хранит символ состояния, а Р - ячейка - символ сдвига. В них происходит задержка данных символов до начала следующего такта.

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

Если остановка и сигнал об остановке никогда не поступают, то говорят, что МТне применима к последовательности U.

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

Внешний алфавит будет состоять из символов: {1, +, Ù}, где Ù - пустой символ.

Внутренний алфавит будет состоять из четырех символов {q₁, q₂, q₃, !}, где символ q₁ означает начальное состояние, а ! - заключительное состояние.

Пусть на ленте записана начальная информация:

1 2 3 4 5 6 7

+

МТ должна ее переработать в результирующую информацию:

1 2 3 4 5 6 7

Состояние ленты МТ в данный момент времени назовем ее конфигурацией.

Последовательность команд, реализующих операцию сложения, будет иметь вид:

1q₁ Ùq₃П

1q₃ 1q₃П

+q₃ +q₃П

1q₃ 1q₃П

Ùq₃ 1q₂H 1 2 3 4 5 6 7

1q₂ 1q₂Л

1q₂ 1q₂Л

+q₂ +q₂Л

1q₂ 1q₂Л 1 2 3 4 5 6 7

1q₁ Ùq₃П

+q₃ +q₃П

1q₃ 1q₃П

1q₃ 1q₃П

Ùq₃ 1q₂H

1 2 3 4 5 6 7

+

1q₂ 1q₂Л

1q₂ 1q₂Л

1q₂ 1q₂Л

+q₂ +q₂Л

Ùq₂ Ùq₁П 1 2 3 4 5 6 7

+

+q₁ Ù!Н 1 2 3 4 5 6 7

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

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

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

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