Лемма 5. Функция /, возникающая примитивной рекурсией из правильно вычислимых функций g, k, сама правильно вычислима.

Для нашпх целей достаточно будет рассмотреть частный случай, когда функция / связана с функциями g, h зависимостью

/ {X, 0) = g {X), f{x,i + i)=h{f {X, i), X).

Как и выше, через (g), {h) обозначим программы машин, правильно вычисляюш;их функции g ж h. Пусть х, у - произвольные натуральные числа. Имеем:

giOlOPO

(Б+ВГВБ+)1

0101"gp01/(«. 0)

q&o gp+iL

(A)p+2 01=01!/ ig01/(»=. 0) (Б-ББ+ВГ),, 01!/-Ю1/(-. OgaOlOl- (ВБ-ВБ+)б OlOly-igeOlrt". "Ю!"

omv-qyOm 1)

Команды, идуш;ие после первого появления состояния gp, преобразуют машинное слово

OlOly-gpOl/t-. )

в слово

010l5-<i+ig..01(-

при условии, что г/ г. Команда дО дрО зацикливает программу и носледуюш;имп преобразованиями параметр y - i будет понижаться до тех пор, пока не получится слово

01-0др01/(. У\

которое в силу команды дрО gp+i перейдет в слово 01др«001«---.-). Дополнительными командами

gpiO-g.+iO, (A).,..i, (В(0)В)ь (Б-)д, (A)v ползшим требуемое состояние qoOily\

Отметим несколько следствий, неносредственно вытекающих иш доказанных лемм. Прежде всего, соотношения

х: + 0 = X, X + {i + i) = {х + i) + i

показываю)т, что функция х -\- у получается из функций g (х) = X и h (х, у) = X I посредством примитивной рекурсии рассмотренного в лемме 5 вида. Функции х и .S (/?) согласно леммам 2, 3 правильно вычислимы. Поэтому и функция X у правильно вычислима.

Аналогичным образом убеждаемся, что функции х - у и ху возникают примитивной рекурсией указанного в лемме 5 вида из функций х, h {х, у) = х - i ж соответственно о {х), у .х. Так как последние функции правильно вычислимы, то функции X - у ж ху также правильно вычисли-лш. В силу леммы 4 вместе с функциями ж, х-х, правильно вычислимой будет и функция х.

Лемма 6. Если частичная функция g (х, у) правильно вычислима, то функция

f (X) = [Ху {g [х, у) = 0)

также пршильно вычислима.

Действительно, для любого заданного натурального х

(Гг)1 OlOgaOl-O {g)aOim%Ois<».

Теперь как и выше, подбираем команды, которые при условии g (х, i) О преобразовывали бы слово OP01gp01®() в слово 01"01»+igp01g(-

дрО -> gp-i? gi5+il дрхзО дв+гО др+зЬ др+зО gp+il

др+Д-др,зД Ol--OlVOl--"- (0)р+5 01Ш%0 (Б-Б-)у geOlOli

(Гг)б 01-""01V0101i (g)e 01-"01ig.01="(«. 1) gJ) gpO 01-01igp01g(--.

Последняя команда зацикливает программу и машина от состояния OlOlgpOl! преобразуется в состояние

ГЛ. V. АЛГОРИТМЫ Н МАШИНЫ ТЫОРИИГА

OlOlfipOlst), затем в состояние Ol-OlgpOl-SJ и т. д. Допустим, что по истечении некоторого времени машина перешла в состояние 01-0Гдр01г<->> и g (х, i) = 0. Написанная выше команда дО gp+ii? переведет машину в состояние OlOlDgpniO. Так как в рассматриваемом случае / (х) = i, то нам остается дописать лишь команды, под воздействием которых машина из указанного состояния перейдет в состояние goOV. Полагаем

gp+iO д-л+ю (В (0) Б-),

01-01Оди-иО 01%01

Если в процессе вычисления значений g (х, i) (i = = О, 1, 2, . . .) встретится либо неопределенное значение, либо все значения будут определены, но отличны от О, то машина будет работать вечно, не приходя никогда во внутреннее состояние до- Но в этих случаях функция / (х) имеет неопределенное значение и потому во всех случаях указанная программа будет вычислять / (х). Лемма доказана.

Выше была установлена правильная вычислимость

функций о (х), X -Ь 1, Х\ ХУ, Х-\- у, 1т,Щ. В СИЛу

леммы 4 вместе с этими функциями правильно вычислимыми будут и все функции, иолуча10ш,иеся из заданных операциями подстановки. В частности, правильно вычислимыми будут функции Yg{{y+ if -х) и sg (2 (г/ -Ь 1) х). Но

[х/2] = \1у({2 (1/-Ы)--х) = 0), []Гх] = ((г/-ЫГ-х) = 0),

поэтому в силу леммы 6 функции [х/2], [Yх] также правильно вычислили)!.

в п. 3.3 бы.ли введены нумерационные функции Кантора с (х, у), I (х), г (х). Из явных выражений для этих функцип видно, что они выражаются через х, у при помощи -f, х, [х], [./2]. Поэтому функции с, I, г ира-впльно вычислимы.

Теперь для завершения доказательства теорелп>1 о синтезе машин Тьюринга нам остается .лишь сослаться на следствие теорелш 2 пз п. 3.4, согласно которому любая

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

частично рекурсивная функция может быть получена пз функций о, x-f 1, /™> с, I, г конечным числом операций подстановки, рекурсий из леммы 5 и минимизаций из леммы 6.

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

Теорема 1. Область определения произвольной частично рекурсивной числовой функции / (xj, . . ., х„) является рекурсивно перечислимым множеством.

Пусть до, gi, . • ., gm - внутренний алфавит машины Тьюринга £, правильно вычисляющей функцию /. Это означает, что

%: giOr"... ОГ" s> goOl"""«О ... О

для тех Ху, . . ., Хп, для которых / определена, и что £ работает вечно для остальных х, . . ., х„. В соответствии с и. 12.2 обозначим через (дхй) машинное слово, получающееся из слова дй после t тактов работы£. Согласно п.12.2 словарная функция

Р {г, . . ., fn, J)) = (giOl"™" Q-(длина уудлшач)

примитивно рекурсивна. Нам надо найти такой момент t, при котором буква до войдет в слово Р, т. е. при котором

Е {д„ Р(1==. , . . ., 1--«, 10) = Л,

где 7 - словарная функция, определенная в п. 11.2. Так как словарные функции Е п Р пртштивно рекурсивны, то примитивно рекурсивной будет и числовая функция

g (хх, . . ., Хп, t) = сЕ (до, Р (I---, . . ., Т", 1)).

По условию / (хх, . . ., х„) определено для тех и только тех Хх, . . ., Хп, для которых существует решение t уравнения (1), т. е. для которых разрешимо уравнение

g(xx, . . .,Хп, t) = О,

а это означает согласно п. 4.4, что область определения функции / рекурсивно перечислима.

Следствие. График произвольной частично рекурсивной функции / {ху, . . ., Xji) рекурсивно перечислим.

Рассмотрим частичную функцию

(у - f (хи п)) + (/ (xi, . - у).

Она частично рекурсивна и ее область определения совпадает с графиком функции /. Поэтому график / рекурсивно перечислим.

Теорема 2. Существует частично рекурсивная функция двух переменных T{xq,X]), обладающая следующим свойством: последовательность одноместных частично рекурсивных функций

Т (О, X), Т (1, X), ...,Т (тг, X), . . .

содержит каждую одноместную частично рекурсивную функцию.

Функции Т {п, х), обладающие указанным свойством, обычно называют универсальными частично рекурсивными функциями двух переменных. Переменные Xq, х в теореме 2 играют разные роли. Поэтому первую из них часто называют параметром. Конечно, можно сформулировать аналогичную теорему и относительно существования универсальных частично рекурсивных функций многих неременных. Однако все эти функции легко получаются (см. п. 6.2) пз универсальной функции двух переменных.

Идея построения функции Т («, х) следующая. Каждая одноместная частично рекурсивная функция / (х) правильно вычислима на подходящей машине Тьюринга £ с внешним алфавитом О, 1 и внутренним алфавитом q, q, . . . . . ., qn (п зависит от /). Машина £ вполне определяется своей таблицей переходов

qfi-qaioVio

ЧЛ Чщп {Vij = О, 1, L, R; i = 1, . . ., п).

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

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

Рассмотрим алфавит 4 = {1, О, д, L, R, е). Условимся в алфавите А внутреннее состояние qi изображать словом g+l (с = О, 1, . . ., п). В частности, машинное слово дгО!" в алфавите А будет изображаться словом gOl, машинное слово qQiQ ... О будет изображаться словом д01=0 ... О и т. д.

Шифром машины £ в алфавите А условимся называть слово

а = eq{)q"-Wxf>eq4q-"Vn . . . (?д»+10д""0уед»+11д«п1у

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

Допустим теперь, что нам удалось построить определенную в алфавите А трехместную примитивную рекурсивную словарную функцию М {а, г, t)), удовлетворяющую требованию

а) если а - шифр некоторой машины Тьюринга £, то

М (а, g01 1") = (да 01) (х, г/ = О, 1, . . .).

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

Р{а,х) = М{а, р, ixiy{E-{q\ М{а, $, 1)) = Л)), (2)

( 1, если аЬ, Е*{(1, Ь) = И1(1, Л; Е{л, Ь))=(д

есчи аЬ.

Иными словами, если а - шпфр машины £ и

1 = 1х1\{Е* {fM (a,"g01 1)) = Л),

то машина £, начав работать в конфигурации g01•, через 2 тактов работы придет в заключительное состояние, так как машинное слово (g01•)W не будет содержать подслов вида q\ i > 2, характеризующих активное внутреннее состояние £. Сама заключительная конфигурация будет согласно а) характеризоваться словом М (а, g-Ol",