Лекция № 3. Машины Тьюринга

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

2. Не распознаваемость самоприменимости машины Тьюринга

Формализация понятия «алгоритм» на основе так называемых машин Тьюринга была предложена английским математиком Аланом Тьюрингом в 1936 году. С тех пор эта абстрактная математическая модель широко применяется в теории алгоритмов для исследования вербальных алгоритмов. Переходя к неформальному описанию машин Тьюринга, отметим следующее.

А.Тьюринг

В состав любой машины Тьюринга входит бесконечная в обе стороны лента, разделенная на ячейки, и головка, способная передвигаться вдоль ленты вправо и влево (см. рис. 4).

Ý – головка

Рис. 4. Представление машины Тьюринга.

В ячейку ленты может быть записана буква из алфавита A={a₀, a₁, a₂, … a_n}. Для каждой машины Тьюринга этот алфавит, называемый внешним, вообще говоря, свой. Но принято резервировать символ a₀ для обозначения пустой ячейки при определении внешнего алфавита любой машины. Будем также считать, что непустое слово в алфавите A–{a₀} воспринимается любой машиной в стандартном положении, если головка находится напротив крайней справа ячейки ленты из тех, в которых записано слово[5] (см. рис. 5).

Ý – головка

Рис. 3. Стандартное положение в машине Тьюринга

(внешний алфавит A={a₀, 0,1})

Работа любой машины Тьюринга осуществляется дискретным образом – шагами (тактами). В каждом такте головка располагается напротив какой-либо ячейки, «обозревая» ее. При этом она может «читать», имеющуюся в ячейке букву; записать в ячейку букву (из алфавита A), предварительно стерев старую; сдвигаться на одну ячейку влево или вправо.

Полагается, что при каждом такте работы машина находится в каком-то состоянии, обозначаемом буквой q_i из алфавита внутренних состояний – Q={q₀, q₁, q₂, ….q_m}. Каждая машина Тьюринга имеет свой собственный алфавит внутренних состояний, но принято считать, что символом q₀ в таком алфавите обозначается состояние остановки, а символом q₁ – начальное состояние. Из состояния q₁ машина начинает работать, а попав в состояние q₀, прекращает работу.

Работа любой машины Тьюринга осуществляется по своей собственной программе или в соответствии с функциональной схемой, представляющей собой совокупность выражений T(i, j) (1£i£m, 0£j£n, i,jÎZ), именуемыми командами, каждая из которых может иметь следующий вид (см. таблицу 1).

Функциональная схема машины Тьюринга (программа) может быть записана в виде последовательности команд или в виде таблицы (см. пример 3.1.1).

Таким образом, та или иная машина Тьюринга полностью определяется:

а) внешним алфавитом A={a₀, a₁, a₂, … a_n};

б) алфавитом внутренних состояний Q={q₀, q₁, q₂, ….q_m};

в) программой (функциональной схемой).

Таблица 1

Говорят, что слово a перерабатывается машиной Тьюринга в слово b, если от слова a, воспринимаемого в начальном состоянии q₁, машина после выполнения конечного числа команд программы приходит к слову b, воспринимаемому в положении остановки.

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

Слово, воспринимаемое в начальном состоянии q₁ имеет вид:

Ý

Определим, в какое слово переработает это слово машина.

Так машина находится в состоянии q_1, обозревая ячейку в которой находится 1, то первой должна быть выполнена команда, стоящая на пересечении столбца q₁ и строки 1 функциональной схемы. Это команда q₂a₀Л. После ее выполнения машина перейдет в следующее состояние:

Ý

После выполнения следующей команды q₂*Л (записанной на пересечении столбца q₂ и строки 1)машина перейдет в следующее состояние:

Ý

На пересечении столбца q₂ и строки 1в функциональной схеме машины Тьюринга записана команда q₂1Л, выполнение которой приведет к состоянию:

Ý

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

q₂1→q₂1Л

Ý

q₂a₀→q₃1П

Ý

q₃1→q₃1П

Ý

q₃1→q₃1П

Ý

q₃*→q₃*П

Ý

q₃a₀→q₁a₀Л

Ý

q₁*→q₀a₀

Ý

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

Определение 3.1.1. Пусть на некотором множестве слов алфавита {a₁, a₂, … a_l} задана функция k переменных, значениями которой являются слова в том же алфавите. Предположим, что имеется машина Тьюринга с алфавитом A={a₀, a₁, a₂, … a_l} (n³l), которая любой набор из k слов, входящий в область определения функции, записанный последовательно с промежутком в одну ячейку между словами, перерабатывает в слово, являющееся значением функции на этом наборе. А на любом наборе из k слов, не входящих в область определения функции, машина работает бесконечно. Тогда про такую машину Тьюринга говорят, что она вычисляет данную функцию, а сама функция называется вычислимой по Тьюрингу.