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

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

Определение 4.1.Машиной Тьюринга Zназывается конечный автоматА,снабженный потен­циально бесконечной лентой, разбитой по длине на одинаковые квадраты (ячейки), и устройствомDдля считывания содержимого ячейки ленты в каждый мо­мент времени, печатания нового символа в этой (обо­зреваемой) ячейке и передвижения ленты на одну ячейку влево или вправо. Символы ленты принадле­жат конечному алфавитуХ(для удобства считаем, что вХсодержится пустой символ, т. е. пустая ячейка). Каждая ячейка ленты либо пуста, либо в ней содержится только один символ. В каждый момент времени лента содержит только конечное число непу­стых символов.

Рис. 4.1. Машина Тьюринга.

Входом для А(рис. 4.1) в каждый момент времени является символ изX,считываемый устройствомD. ВыходомА,который однозначно определяется по счи­тываемому символу изХи внутреннему состояниюА, является элемент из(ХМ)(стоп),гдеМ={Л, П, Н}.Если выходом является «стоп», то машинаZпрекращает вычисления. Если выходом яв­ляется пара(х, т),то автоматА спомощью устрой­стваDпечатает в обозреваемую ячейку символх и перемещается на одну ячейку влево (еслит=Л), вправо (еслит=П)или остается на месте (еслит=Н).

Определение 4.2.Каждой машине Тьюрин­гаZсопоставим функциюF_z(n₁,n₂,…,n_r) такую, что еслиZв начальном состоянииq₀обозревает са­мый левый символ слова

1…1  1…1  …  1…1,

{

{

{

n₁+1 n₂+1 n_r+1

по обе стороны которого находятся только пустые символы, то F_z(n₁,n₂,…,n_r)равно числу единиц, произвольным образом размещенных на ленте ма­шиныZв момент ее остановки; еслиZне останавли­вается, то считается, что функцияF_zне опреде­лена (на данном наборе).

Предполагается, что машина Zобра­щается с пустой ячейкой ленты так, как будто бы в ней напечатан специальный символ «».

Введем специальное название для функции F_z одного аргумента.

Определение 4.3.Функцияfнатурального аргумента называетсячастично рекурсивной,если

f(n)=F_z(n)

для некоторой машины Тьюринга Zи всех натураль­ных чисел (считается, что если одна часть равенства неопределена, то такой же является и вторая часть этого равенства).

Частично рекурсивная функция называется рекур­сивной,если она определена при всехп.

Из определения 4.1 следует, что вся интересующая нас информация о ее струк­туре уже содержится в структуре входящего в ее со­став конечного автомата

А = {X, (XМ)U (стоп), Q, ,  ).

Поскольку ХиQ– конечные множества, мы можем легко перенумеровать их элементы

Х={x₁, x₂, …, x_m}, Q={ q₁, q₂, …, q_n }.

Теперь автомат Аможно представить следующим списком пятерок

q_kx_ix_nmq_p, (4.1)

где для каждой пары (q_k, x_i)такой, что (q_k, x_i)стоп, имеется в точности одна пятерка такая, что(х_n, m)= (q_k, x_i), q_p=(q_k, x_i).

Ясно, что имеется взаимно однозначное соответствие между такими списками и конечными автоматами рассматриваемого типа. Так как множество значений каждой из величин k, i, nирнумеруемо, а вели­чинатпринимает три значения, то совокупность всех пятерок вида (4.1) может быть также перену­мерована. Таким образом, перечислимо множество всех конечных списков таких пятерок и, следовательно, множество всех интересующих нас конечных автоматов.

Далее, эти автоматы можно перечислить, т. е. так, что по любому задан­ному числу rможно восстановитьr-й автомат. Опре­делимвеспятерки вида (4.1) как натуральное числоk+i+n+m+p(полагаяЛ=1, П=2, Н=3).Ясно, что имеется только конечное число автоматов, задаваемых списками из не более чемrпятерок таких, что вес каждой пятерки не превосходитr.Все такие списки можно расположить в лексикографическом порядке. Автоматы, задаваемые такими списками, назовемавтоматами степени r.Таким образом, все интересую­щие нас автоматы можно эффективно перечислить (возможно с повторениями, что не имеет значения) следующим образом: перечисление начинается с ав­томатов степени 1, затем автоматов степени 2 и т. д., а автоматы одной степени перечисляются в лексико­графическом порядке. Таким образом, имеет место следующая теорема.

Теорема 4.1.Множество всех машин Тьюринга эффективно перечислимо:

Z₁, Z₂, Z₃, …

Отсюда непосредственно имеем

Следствие 4.1.Множество всех рекурсивно перечислимых множеств эффективно перечислимо:

S₁, S₂, S₃, ….

При этом

Определение 4.4.МножествоSназываетсярекурсивно перечислимым,еслиS={f(n) |n N}для некоторой частично рекурсивной функцииf.

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