Теорема 2. Для того чтобы заданная в алфавите А частичная словарная функция F {Xi, . . ., Хп) была частично рекурсивной, необходимо и достаточно, чтобы она могла быть получена из простейших словарных функцийО, S, 1 конечным числом операций подстановки, словарной рекурсии и словарной минимизации.

Для полноты приведем доказательства этих теорем. В п. 11.2 установлено, что операции подстановки и словарной рекурсии, примененные к примитивно рекурсивным функциям, дают функции примитивно рекурсивные и что простепнше словарные функции примптпвно рекурсивны. Тем самым установлена достаточность в теореме 1. В п. 11.2 также доказано, что операция словарной минимизации, примененная к словарной частично рекурсивной функции, дает частично рекурсивную функцию. Поэтому достаточность в теореме 2 также установлена. Для доказательства необходимости в теоремах 1, 2 предварительно выведем несколько лемм. Уело- • вимся словарную функцию называть словарно примитивно рекурсивной, если она может быть получена из простейших словарных функций операциялш подстановки и словарной рекурсии.

Введем еще обозначения v (п) = а" = аа . . . v (0) =

= а = Л, гдео -какая-либо буква заданного алфавита.

Лемма!. Для каждой числовой примитивно рекурсивной функции f {xi, . . ., Хп) существует словарно примитивно рекурсивная-функция F (Vi, . . ., удовлетворяющая тождеству

F [vxx, . . ., ухп) = V/ [xi, . . .,хп). (1)

Доказательство проведем по числу к операций подстановки и примитивной рекурсии, которые следует выполнить, чтобы получить / пз простейших числовых функций о, s, 1\. Если = О и, значит, / совпадает с одной пз функций о, s, 1\, то словарная функция F, удовлетворяющая (1), строится очевидным образом.

Пусть > О, / = ""+1 (Л, /ti, . . ., hm) и пусть Н, Н, . . . . . ., Н,п - словарные функцпп, связанные с функциялш h, hi, . . . . . ., hm соотношениями впда (1). Тогда словарная функция F = (Я, Hi, . . ., Ыт) будет связана с / соотношенпеи (1).

Наконец, пусть f = R {g, h) и пусть G, Н - словарные функцпп, связанные с g, к соотношениямп тппа (1). Таким образом,

п, У, f (xi, . . ., Хп, у))

v.r,i, vj/, v/(a;i, . . ., х„, у)).

f (ai, • Q) = g [xi,

f (xi, . . ., Xn, !/ -b 1) = Л (xi, .

n В силу (1)

V/ [Xl, . . ., Xn, 0) = G{vxi, . V/ {xi, . . ., Xn, !/ -b 1) = Я {vxi. Ho тогда F {Xl, . . ., Xn, i)), определенная рекурсией F{Xu...,Xn A) = G(Oi, ...,r)J,

F (Xl, . . ., r„, pai) = Я (Гь . . ., ,r„, Г), F (Xl, . . ., .r,, r))) F(Xi, . . . ,Xn, mi) =A (г=2, . . . , p), будет, как легко видеть, связана с / условием (1).

Лемма 2. Существует словарно примитивно рекурсивная /функция Т (г), удовлетворяющая соотношению

Т (V (л)) = an*).

Действительно, обозначая через G [х) слово, номер которого на 1 больше номера х, пз формулы (1) п. 11.1 видим, что

G(.\)=ai, G{xa)=X4i (J = 1, . . ., р - 1), G (ха) = G {х) ai

II потому функция G словарно прилштивно рекурсивна.

Отсюда следует, что функция Т [х), определенная рекурсией

Г(А) = Л, Т{ха-;) = Т(х) (i = 2.....р), T(xai) = G{x),

также примитивно рекурсивна. Эта функция, очевидно, и удовлет-ипряет требованию (2).

Лемма 3. Одноместная словарная функция у (с (х)) словарно примитивно рекурсивна.

Согласно лемме 1 существуют словарно примитивно рекурсивные функции Fi [х), для которых

Fi (vx) = vc (axui) = V {px -\- i) {x E Щ.

)ункция V (e (x)) удовлетворяет схеме рекурсии

vc(A)=/\, vc(rtaj)=ve(ac(a)a.) = Fj(vc(a)) (t=l,

ir потому сама является примитивно рекурсивной.

Чтобы закончить доказательство теореьш 1, нам надо было показать, что каждая, примитивно рекурсивная функция G (Xi, . . . . Хп) словарно прилииивно рекурсивна. Пусть / {xi, . . ., Хп) - представляющая функция для G. По условию/ примитивно рекурсивна и, значит, в силу леммы 1 существует словарно примитивно рекурсивная функция F, связанная с / соотношением (1). Из соотношений П), (2) последовательно получаем (й,..., Хп) = «/ (с (Хх),. . с ixj) = Txf (с (Xl), . .., с (yj) =

= TF(vc (Xi),...,vc (Xn)).

Так как функции Т, F, vc (х) словарно примитивно рекурсивны, то G также словарно примитивно рекурсивна, что и требовалось.

Доказательство теоремы 2 проводится аналогично, только нместо лелшы 1 надо опираться на аналогичную лемму:

Лемма 4. Для каждой числовой частично рекурсивной функции f (xi, . . ., x,i) существует словарная частичнся функция Р (Xi, . . ., Xn)i удовлетворяющая соотношению (1) и по.гучающаяся 1-1 простейших с.говарных функций операция.чи подстановки, словар-•ой рекурсии и с.юварной мини.мизпции.

Справедливость этой леммы устанавливается тем же способом, ITO и справедливость лем.\ш 1. А именно, обозначаем через к чпсло "пераций подстановки, примитивной рекурспп и минимизации, чрп по5Ющп которых ф5кцпя / ползчается пз простейших числовых Функций о, S, 1, и веде.м индукцию по к. Для к = О утвержденпе

*) Как н ранее, an означает слово, имеющее в алфавитной нумерации (п. 11.1) номер п.

очевидно. Пусть для функции / число к имеет заданное значение а для всех функций / с меньпшм к мы умеем строить функцию р] Если / получается из функций с меньшим к нодстановкой или в-рш-митивной рекурсией, то построение F было указано при доказате-стве леммы 1. Остается рассмотреть случай, когда

Ш = И-у (g у) = 0)

и для функции g соответствующая функция G известна. Но из (1) и (3) непосредственно получаем

v/(a;) = na(G(vx, а;) = Л). Следовательно, функция

FW = pa(G(X, а/) = .А) и будет искомой функцией для /. Дополнения и примеры

1. Доказать примитивную рекурсивность следующих словарных функций

а) F [X) = начальной букве х,

б) F (х, о) = начальному отрезку слова х, длина которого равна длине р; если длина о больше длины у, то F {х, ) = X,

в) F ():)= максимальному решению уравнения р = r)jP~.

2. Пусть алфавит А состоит из предметных переменных ху, . . .

• > Хп, функциональных переменных /, . . ., /" скобок (,) и запятой. Показать, что совокупность всех термов, записываемых в алфавите .4, примитивно рекурсивна.

3. Пусть алфавит А содержит не менее двух букв. Рассматри- . вается совокупность всех бинарных отношений между словами в А. Для каждой буквы ai из А определяем отношения pi, Oj посредством формул

Xp-lf-Г , riP Х = 01). Щ

Композиция 9x02 произвольных бинарных отношений Э, опреде- ляется обычным образом:

j:9i92t)4(3})(yGi3-&-392!)).

Исходя пз отношенпп рх, стх, • • •. Рр, <Тр, строим новые отношения с помощью операцип объединения, пересечения, композиций и рефлексивно-транзитивного залшкания отношения. Показать, что класс всех полученных отношений совпадает с классом всех бинар- ныхрекурсивно перечпслтшх отношений (Ц еп т п н [2]). м

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

Первый важный и достаточно широкий класс алгоритмов был описан Т ь ю р и н г о"м [Ц иП остом [1] в 1936-1937 гг. Алгоритдпл: этого класса осуш;ествляются особылш машинами, называемыми в настоящее время ма-

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

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

12.1. Машины Тьюринга-Поста. Машина Тьюринга - Поста содержит следуюпще части (рис. 1).

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

может находиться в одном из конечного множества состояний. Эти состояния мы будем обозначать символазии До, а-у, . . ., йт или другими символами. Совокупность их называется внешним алфавитом машины, а сама лента часто называется внешней памятью машины. Клетки в одном фиксированном состоянии иногда называются пустыми. Пустые состояния мы обычно будем обозначать символами flo или 0. В процессе работы машины ячейки ленты могут изменять свои состояния, но могут и не изменять их. Все вновь пристраиваелпле ячейки пристраиваются пустыми. Лента считается направленной и ее ячейки мы будем просматривать слева направо. Таким образом, если в какой-то момент времени лента имеет г ячеек и внешний алфавит машины состоит из символов aoii, . . ., состояние ленты полностью описывается словом

ajflj, . . . aj. . . aj,

где aj, - состояние первой (слева) ячейки aj - состояние второй и т. д.

Рис. 1

б) Внутренняя намять. Внутренняя память машины - это некоторое устройство, которое в каждый рассматриваемый момент находится в некотором «состоянии». Предполагается, что число возможных состояний внутренней памяти конечно и для каждой машины фиксировано. Состояния внутренней памяти мы будем обозначать символами ?1, • • •> (7я или любыми другими символами, не входящими во внешний алфавит машины. Совокупность символов, обозначающих состояния внутренней иалгяти, называется внутренним алфавитом машины.

Состояния внутренней памяти часто называются внутренними состояниями машины. Одно из этих состояний называется заключительным и в работе машины играет особую роль. Символ, обозначающий заключительное состояние, будет называться стоп-символом.. Как правило, роль стон-символа далее будет играть символ q.

в) Управляющая головка. Это некоторое устройство, которое может перемещаться вдоль ленты так, что в каждый рассматриваемый момент времени оно находится в определенной. ячейке ленты. Иногда, наоборот, считают управляющую головку неподвии<но связанной с машиной, а движущейся частью считают ленту. В таком случае предполагается, что в управляющую головку вводится то одна, то другая ячейка ленты. Если какая-нибудь ячейка находится в управляющей головке, то говорят также, что машина в данный момент «воспринимает» или «обозревает» эту ячейку.

г) Механическое устройство. Предполагается, что машина снабжена особым механизмом, который в зависимости от состояния восприни1маемой ячейки и состояния внутренней памяти может изменить состояние внутренней памяти и одновременно либо изменить состояние воспринимаемой ячейки, либо сдвинуть управляющую головку в соседнюю слева ячейку, либо сдвинуть управляющую головку в соседнюю справа ячейку. Если управляющая головка находится в самой правой ячейке и по ходу работы машина должна сдвинуть унравляющзчо головку в соседшою справа (отсутствующую) ячейку, то предполагается, что, сдвпгая головку, машина одновременно пристроит недостающ5то ячейку в пустом состоянии. Аналогично работает машина п в случдз, когда головка воспринимает са.мую левую ячейку п по ходу дела машине надо сдвинуть головку еще левее.

-St,

Наконец, если в какой-то момент времени внутренняя память машины приходит в заключительное состояние q, то дальнейших изменений в дгашине не шроисходит и машина называется остановившейся. Мож(ет случиться, что Ji машине не будет происходить никаких изменений и при каком-то другом внутреннем состоянии д,. Однако в том случае мы не будем говорить, что лгашина остановилась, а будем считать, что машина продоллоет работать «вечно».

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

Совокупность всех.этих данных можяо записать одним словом

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

Предполагается, что существуют машины Тьюринга с любылп! заданными внешним и внутренним алфавитами при условии, что эти алфавиты не имею1Т общих символов. Предполагается также, что коль скорю заданы внешний {яо. dv . ., flm} И внутренний {до, q, . . ., qn} алфавиты лашпны, то машину можно привести в «состояние», описываемое любым произвольно заданный)! словом вида (1) (при условии, что СИЛ1В0Л qi в нем ие самый правый), и затем пустить маиьину работать.

Работа машины состопт в том, что она из данного "Состояния» по пстеченпп одного такта, работы механического устройства переходит в следующее «состояние», затем от нового состояния по истечении такта работы пере->;одпт к ново-му состоянию и так далее.

Если данное состояние описывается машпнным словом

то машинное слово, описывающее следующее состоя-нпе машпны, будет обозначаться через Полагаем,

далее,

m(+i) = (mf))-i) (J = 0, 1,2,...),