не это [ограничения; функций ф (f), ф (р, j-g), • • • на множествах слов, записываемых в частичных алфавитах {а, . . ., (к < т.).

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

Теорема 1 (Тьюринг). Все частичные словарные функции, вычислимые по Тьюрингу, являются частично рекурсивными.

Так как функция, определенная в некотором алфавите и частично рекурсивная в расширенном алфавите, является частично рекурсивной и в первоначальном алфавите (п. 11.1), то для доказательства теоремы 1 достаточно но- казать, что функции ф (fi, . . ., f) (s = 1, 2, . . .) для любой машины Тьюринга £ являются частично рекурсивными.

Пусть {ао, «1, . . ., а}, {qo, qi, . ., qn) - внешний и внутренний алфавиты машины £ и пусть

bi -> Ci, ba Сг,. .., br

- программа подстановок для £, определенная в пред-шествуюш;ем разделе. Символы bi, означают подходящие слова в расширенном алфавите {ао, а, . . ., а, до, . . ., д„, и, V}.

Для произвольного слова а в указанном объединенном алфавите мы определяем слово с помощью следующего правила; в программе подстановок (2) ищем первую команду bi Ci, левое слово которой bi входит в а, и затем в в подставляем слово Cj вместо первого вхождения слова bj. Если ни одно из левых слов команд программы (2) в а не входит, то полагаем а = й.

Изложенное правило дословно совпадает с правилом построения слова ишу по заданному расширенному машинному слову umv, которое было сформулировано в конце предыдущего раздела. Отличие состоит лпшь в том, что теперь ьш применяем это правило к произвольным словам в расширенном алфавите, а не только к машинным словам. Полагая, как и в п. 12.1,

й(о):= й, вО+1)= ф)т (Я = О, 1, 2, . . .),

впдим, что выражеппе о теперь имеет определенное значение для любого слова а в расшпренном алфавите, причем, если й - машинное слово, то а* - машинное сло-

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

Вместо выражения f зависящего от словарного аргумента р и числового аргумента i, вводим функцию V (й, f), полагая

V (й, f) = f (Я"«а а)

для любых слов й, г в расширенном алфавите.

Функция ф (fl, . . ., fs) определена в редуцированном алфавите. Мы продолжим эту функцию до функции фо (?! • • ч ?з) в объединенном алфавите, полагая spo (fl! • • •. Is) совпадающей с ф (fi, . . ., fs)! для слов fl, . . м fs в редуцированном алфавите и неонределенной для остальных значений fi, . . ., fs- Так как графики функций 55 и f о совпадают, то частичная рекурсивность одной из этих функций влечет частичную рекурсивность другой. Но сравнивая определения функций sp и F, непосредственно заключаем, что для слов fi, . . ., fs, f в расширенном алфавите равенство

spo(fi, fs) = a:- (3)

истинно тогда и только тогда, когда существует слово а, удовлетворяющее требованиям:

fl, . . ., fs не содержат букв ао, до, . . ., д„, и, v,

qo содержится в слове V (а, идаос- . . . aofs), (4)

J = F (й, ugiaof 1... uosV)*,

где звездочка * означает операцию выбрасывания из данного слова всех вхождений символов ао, до, . . п, и, v. Согласно п. 11.2

ао f i Л = J5 (f i, Sbg (f i, Л)),

?i6fi-=JS(fi, Sbg.(fi, Л))

(7 = 0,..., re), ufiOA = :E;(fi, Sb„(fi,A)), (5)

i; fi <H> A = JS (f i, Sb (f i. A)), ?o6F(u, ugiuou - aof,y)=4A = JE;(go, V (a, ugi.aoti...aohv)), r = F(a,ugiaofi...aofsZ)*44A = JS;(f, F(...)*)J5(F(...)*, f),

где E, Sbo - примитивно рекурсивные словарные функции, определенные в конце и. 11.2.

Обозначая через G (fi, . . ., fs, f, й) произведение всех выpaжeниЙJ стоящих справа от (правых) знаков равенств

в формулах (5), приходил! к заключению, что совокупность условий (4) равносильна равенству

а) = Л. (6)

График функции spo состоит из систем (fi, . . ., fs, f), удовлетворяюш;их условию (3), т. е. из систем, для которых уравнение (6) имеет хотя бы одно решение л.

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

Из определения функции V следует, что

F(A,f) = f, (7)

V{az, f) =

Sb (F (a, f); bi, Ci), если bi 6 F (a, f), Sb (F (a, f); ba, Ca), если bi V (a, f), Ьг 6 F (й, j), (8)

если biCF(a, f),..., b F (a, f),

F (a, f),

где z б {яо, Й1, . . ., go, . . ., g„, u, y}, Sb - знак подстановки (и. 11.2), a bx, Cx, . . ., bf, C; - слова из программы подстановок (2) машины £.

Согласно п. 11.2 схемы (7), (8) равносильны схеме словарной индукции для V (й, f) с примитивно рекурсивными исходными функцией f и функциями

Яо (а, f, 9) = TF (Sb (t); bi, Ci),..., Sb (t); b,, q), 9;

.E(bi, 9), ...,(b„9)).

Следовательно, функция F (u, 5) примитивно рекурсивна и теорема доказана.

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

12.3. Синтез машин Тьюринга. Как уже говорилось, имеет место следующая важная

Теорема 1 (Тьюринг). Для каждой частично рекурсивной словарной функции F (fx, . . ., 5), определенной в некотором а.гфавите {«х, . . ., Ят}, существует машина Тьюринга с сшмволами ао, а, . . ., аи подходящим внутренними состояниями, которая вычисляет функцию F (fx, • • -, fs).

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

1) построить машины Тьюринга, вычисляющие простейшие функции;

2) имея машины Тьюринга, вычисляющие функции F, Fi, . . ., Fg, построить машины, вычисляющую функцию F (Fx, . . ., Fg);

3) имея машины Тьюринга, вычисляющие какие-то функции G, Hi, построить машину, вычисляющую функцию, возникающую из G, Hi примитивной рекурсией;

4) имея машину Тьюринга, вычисляющую всюду определенную функцию G (fx, . . ., fs, f, й), построить машину, вычисляющую функцию F, заданную соотношением

i(fi, f.) = f<H(3a)(G(fi, f„ f, a) = A).

Здесь (Эй) означает выражение «существует такое слово й, что ...».

Задачи 1)- 4) и будут решены ниже. Внутренние состояния искомой машины будут обозначаться символами до, Qi, . . ., д», а сама машина будет задаваться своей программой команд причем иногда будут выписываться не все команды а лишь те, которые будут нужны по ходу дела. Как и в предыдущем разделе, если m - машинное слово, то через т* будем обозначать машинное слово, описывающее то состояние машины, в которое она придет, исходя из состояния т, через i тактов работы.

Для машинных слов ш, п будем писать ш s> п, еслп т() = п для некоторого i и в процессе перехода от состояния m к состоянию п машина ни разу не пристраивала ячеек слева. Будем писать m 1 п, если т() = п для некоторого i и в процессе перехода от состояния m к состоянию п машина не пристраивала новых ячеек нп слева, ни справа.

Пусть машина £ пмеет а.лфавиты {ао, а, . . ., а}, {qo, qi, . . ., gn) п F (fx, . . ., fд) - частичная s-местная словарная функция, заданная в редуцированном алфавите {а, . . ., fl„j}. Будем говорить, что машина £ правильно вычисляет частичную функцию F (fx, . . ., fs), если

дхао?1йоЕ2 • • aofs Н • ")

для любой системы слов fj, . . ., в редуцированном ал- фавите, принадлежащей области определения функции Рл и еслп в случае, когда F (f, . . ., f) не определено, маши. на £, начав работать в состоянии дяоРхйоРг • • • oJs, никогда! не остановится, т. е. не придет во внутреннее состояние! до, и никогда в процессе работы не будет надстраивать ленту слева.

Сравнивая понятие правильной вычислимости функ-: ции с понятием (простой) вычислимости, введенным в: п. 12.2, непосредственно видим, что из правильной вычис-) лимости заведомо вытекает простая вычислимость. По-j этому мы лишь усилим теорему 1, если докажем, что спра-i ведлива

Теорема 2. Для каждой частично рекурсивной-словарной функции F (fl, . . ., fs), определенной на сово-. купности слов какого-нибудь алфавита {а, . . ., существует машина Тьюринга с символами «о, Яц . . ., а„. и подходящими внутренними состояниями, которая правильно вычисляет функцию F.

Мы докалем эту теорему лишь для случая, когда первоначальный алфавит {а, . . ., а,„} состоит из одного символа 1. Рассуждения в случае произвольного алфавита остаются теми }ке самыми и лишь записи становятся более громоздкими.

Вместо символа ао будем употреблять далее символ 0. Для положительного натурального х вводим обозначения

l-"" = И . . . 1, 0= = 00 . . . 0.

Дополнительно полагаем

О" = 1" = Л,

где Л - пустое слово. На слова

10 = л, 11 = 1, 1 = И, 13 = 111, . . .

будем смотреть как па «пзображенпя» натуральных чисел О, 1, 2, 3, . . . Соответственно этому будем говорить, что числовая частичная функция / {х-, . . ., х) правильно вычисляется машиной £, еслп этой машиной правильно вычисляется словарная ф5шкцпя F (fi, . . ., г), определенная равенством

F (ls is . . ., I-"") = l-"

§ 12. МАШЙНЬ! ТЬЮРИНГА

Итак, мы хотим доказать, что для каждой числовой частично рекурсивной функции f {х, . . ., х) существует машина Тьюринга с внешним алфавитом {О, 1} и подходящим внутренним алфавитом {до, gi, . . ., g„}, которая правильно вычисляет функцию f {х, . . Xs), т. е. для которой

giOl.Ol . . . 01"s> goOl""- ... О

при любых Xl, . . ., Xs из области определения функции /, 21 которая не останавливается и не надстраивает ячеек слева при запуске ее из состояния giOlOl* . . . Ol в случае, если значение j [х, х,, . ., х) не определено. -

Мы начнем с определения понятия композиции машин Тьюринга, играющего основную роль во всех вопросах, связанных с синтезом машин. Пусть заданы машины Тьюринга sp, имеющие какой-то общий внешний алфавит {ао, fli, . . ., йт} и внутренние алфавиты {до, gi, . . ., g„} и соответственно {до, ql, • qt}- Композитом (или произведением) машины sp на машину Й. будем называть машину Ш с тем же внешним алфавитом {йо, а},

внутренним алфавитом {до, gi, . . ., qn, qn+ъ • • qn+t} и программой, получающейся следующим образом. Во всех командах из sp, содержащих заключительный символ до, заменяем до символом qn+i- Все остальные символы в командах из sp оставляем неизменными. В командах из О,, напротив, символ qb оставляем неизменным, но зато ка}к-дый из остальных символов qj {] = i, • •, t) заменяем символом gt+j. Совокупность всех команд из sp и £i, измененных указанным способом (обозначим их соответственно ф* и Q*), и будет программой композита машин ф,й.

Композит машины ф на машину U обозначается через й. пли sp * Основное свойство его выражает

Лемма 1. Если для каких-то слов йо, Ьо, а, bi, «о, Ь, внешнего алфавита {uq, а, . . ., а)

sp : йодгЬо И uigobi, U : aigibi \=-> aqobi.

spu: uogibo Н> йздоЬо.

Действительно, преобразуя слово uogia с поющью команд пз sp*, ноллпм слово aig+ibi. Дальнейшие пре-образованпя его с помощью команд пз Ь* приведут к ЛодоЬз-