1). В частности, если машина S правильно вычисляет функцию / {х), то для каждого натурального х

Р {а, дШ) = gOVm ... 0. (3)

Чтобы избавиться в формуле (3) от стоящих в конце букв О, введем особую функцию G-i (5), полагая по определению: Gj (f) = первое д1аксимальное подслово вида

Ii в f, Gi (г) = Л, если f не содерншт подслое вида lt+i

Примитивная рекурсивность функций Gi (f) будет доказана ниже.

Из формулы (3) И определения функции Gi получаем Gi (Р (й, = IM. (4)

Функции М, Е* примитивно рекурсивны (п. 11.2). Формула (2) показывает, что функция Р (а, у) частично рекурсивна. Так как функция Gy примитивно рекурсивна, то функция

Н (й, f) = Gi (Р (а, р))

также частично рекурсивна. Вместе с нею будет частично рекурсивной и ее представляющая функция

h (а, х) = с {Н {са, сх)),

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

g{x) = e (gOl), к {х) = 1.1, (с (1") = х).

Очевидно, первая из этих функций примитивно рекурсивна, а вторая частично рекурсивна. Поэтому функция

Т (а, х) = к {h (а, g (х)))

является частично рекурсивной. Она и является искомой универсальной частично рекурсивной функцией. Действительно, пусть / (х) - какая-то частично рекурсивная одноместная функция. Согласно п. 12.3 / (х) правильно вычислима на подходящей машине Тьюринга S. Пусть а - шифр этой .машпны в алфавите An а = с {а) ~ номер этого шифра. Пз формулы (4) получаем

И (а, д-ОТ) = 1Я--)

и, следовате.льно,

h {а, g (х)) = с (IW), к {h (а, g (X))) = / (х).

то есть

Т {а, х) = / (х),

а это и означает, что Т {п, х) - частично рекурсивная универсальная функция.

Нам остается показать, что примитивно рекурсивная словарная функция М (л, у, J)), обладающая свойством а), существует. Но функи,ия М, определяемая словарной рекурсией

М(а, 5, Л) = у, М{а, h Г)и) = Ф{л, М {л, f, t))) (uA),

заведомо обладает свойством а), если вспомогательная функция ф (й, f) примитивно рекурсивна и удовлетворяет следующему требованию:

б) если й - шифр некоторой машины £ и j - произвольное машинное слово, то Ф (й, f) есть машинное слово, описывающее состояние машины £, в которое она переходит из состояния 5 после одного такта работы.

В свою очередь, функцию Ф мы будем искать в впде

ф(й, f) = Com;(F(u, г), ?),

где Com, Ч - подходящие примитивно рекурсивные функции. Ясно, что фзнкция Ф, определенная формулой (5), заведомо удовлетворяет требованию б), если функции ¥ 1 Com удовлетворяют соответстзенно условиям

в) если й - шифр машпны Тьюринга S п г - машинное слово, 5 = {и = О, 1), то

¥ (й, f) = g-iy (i; = О, 1, L, Л),

где g+if - правая часть приказа g+i-u g-+if, выполняемого машиной £;

г) если J - машинное слово f = Sg+uq, а Ь равно какому-нибудь слову вида (у = О, 1, L, R), то Com (b, f) равно машинному слову, получающемуся из г командой g+lu -> Ъ.

Строим сначала функцию ¥. Функция St (х), равная начальной букве х, удовлетворяет словарной рекурсии: St (Л) = Л п

f St (г), если фА, ,

St(m)= , =JJ\{u, Str; г)

- [ и, если г = Л,

п потому примитивно рекурсивна, функция Rest (й, г), равная части слова ?, лежащей за первым вхождением

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

й в р, если а (: 5, и равная Л, если а (f у, удовлетворяет словарной - рекурсии: Best (а, Л) = Л и

[ Rest (а, f) и, если а G ?, Rest (й, ри) = . =

I Л, если йр,

= TFi(Rest(a, у) а, Л; J7 (а, р)).

Поэтому функция Rest примитивно рекурсивна. Наконец, функции <?„ (iO (иА), определенные схемой: С,. (р) = = первое максимальное подслово вида u+i, входящее в р, если р содержит подслова этого вида, и Gy (р) = Л, если 5 ке содержит подслов указанного вида, удовлетворяют словарной рекурсии: G„ (Л) = А и

Gu{¥v) = Gu{t) {иеА,ифи),

•G„(p), если Best (G„(p), ,Gu{x)u, если Rest {Gu{x), 5) = А.

Gu{u) =

Поэтому функции Gu (?) примитивно рекурсивны.

Из функций G„(j) выше была использована функция Gi (j). Далее нам будет нулша лишь функция G (г) = = G (р). Исходя из этой функции и функций St, Sb (и. 11.2), легко уже построить и функцию ¥, обладающую свойством в). В самом деле, пусть р = Pg+iuq (и = О, 1) - машинное слово и

й = сдЮд-июедЧд-пихх. .. eg«iOg""Oy„oPg"ilg-"i;„i

- шифр некоторой машины S. Тогда

G (i-) = St (Rest (G (j), E)) = u.

Вводя примитивно рекурсивную функцию

Dir J = G (p) St (Rest (G (p), p)),

будем пметь

Dir 5 = g i(i.

Rest (e Dir j, a) = . . . eq+HqVni,

Dir (Rest (e Dir p, ()) = q""Щu

Поэтому примитивно рекурсивная функцпя

¥(а, г) = Dir (Rest (е Dir г, а))

заведомо удовлетворяет условию в).

Аналогичным образом строится и функцпя Com. За-метпдг сначала, что равенство St (Ь~) = и {Ь~ есть обра-

§ 12. МАШИ1Л>1 ТЬЮРИНГА

щение слова Ъ (см. и. 11.2)) означает, что и есть последняя буква слова Ъ- Условие г) мы теперь запишем на формульном языке в виде следующей схемы:

Com(i), р) =

fSb(p; Dirj, Ь), Bb(p; Dirp, uG{b)),

еслп St(b ): если St (b") -

= <

Sb(p; Dirp, uG(b)O), если St(b ) Sb(p; {Вк~),С{Ь)и), если St(b~)

Sb(?; G(p), G(b)O), A

0, 1,

R, Bic = u, С1фА, {uA), R, Bicu,

=

L, Bi = u,

В1СфА, если St (b~) = L, Dp = A,

в остальных случаях, где для краткости положено >

/?r = StRest(Gp, i), Ср = Rest (Dir f, j), Ду = Rest ((Dir ?)~, Г).

Эта схема определяет значение функции Com (b, р) для любых слов !), р в алфавите А. Она подобрана так, что Com, как легко видеть, заведомо удовлетворяет требованию г). Остается лишь убедиться, что функция Com примитивно рекурсивна. Для этого преобразуем схему, заменяя указанные в ней равенства и неравенства стандартными равенствамп пустому слову при помощи следующих соотношений:

а = Ь4ФБ(а, b)i5(b, й) = К, афА Wx{l, А; а) = Л, а = А и Ь = Л44-а!) = Л.

После этого определяющая функцпю Com схема примет вид

еслп ai = A,

Com(b, х) =

t)p, еслп ар = А,

Л в остальных случаях.

Схема (6) равносильна равенству

Gom(b, )=Wp{r)i, ..., рр, А; ai, ..., ар).

Так как . функции t)i

up примитивно

рекурсивны, то из этого равенства следует, что функция Com также примитивно рекурсивна.

Итак, примитивно рекурсивная словарная функция М (а, р, t)), обладаюш;ая свойством а), построена.

12.5. Универсальные машины. В п. 8.1 множество натуральных чисел и было названо ш-универсальным, если и рекурсивно перечислимо и для каждого рекурсивно перечислимого множества 8 существует такая общерекурсивная функция g (х), что

x8,g{x)U.

Мнояество Ъ слов в произвольном алфавите В называется т-универсальпым, если совокупность номеров слов из Ъ ж-универсальна.

Если вместо алфавита В мы будем рассматривать более широкий алфавит А, то номера слов из Ш в алфавите А будут UHHiMH. Однако легко убедиться (см. п. 11.2), что если совокупность номеров слов из вычисленная в алфавите В, является }>г-универсальной, то совокупность номеров слов иа S, вычисленных в алфавите А, будет также 7гг.-универсальной. В частности, если алфавит состоит лишь из одного символа а, то словарный номер слова а" совпадает с х. Поэтому совокупность слов {а?, . . .} (в произвольном алфавите, содержащем а) тогда и только тогда «г-универсальна, когда ??г-универсальна совокупность чисел {хо, Xi, . . . }.

После этпх предварительных замечаний рассмотрим снова какую-нибудь машину Тьюринга Z с символами «0=0, dy = i, аз, . . ., Ят и внутренними состояниями до, . • -, дп- Пусть в начальный мо-мент эта машпна имеет конфигурацию, описывающуюся машинным словом (igib- Начав работать в этой конфигурации, машина либо через некоторое число тактов работы остановится, придя во внутреннее состояние д, либо будет работать вечно. Символом Ziin словимся обозначать совокупность машинных слов, описывающих те конфигурации, начиная с которых: машина через конечное чпсло тактов работы останавливается, а через Zmt обозначим совокупность всех остальных машинных слов.

Определение. Машина Тьюринга £ называется универсальной, если множество tfin т-универсально.

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

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

Теорема 1. Если частично рекурсивная функция f (х) имеет своей областью определения т-универсаль-ное множество, то вычисляющая ату функцию машина £ универсальна.

В самом деле, пусть {О, 1, а, . . ., a„j} - внешний алфавит машины £ и д„, д, . . - ее внутреиние состояния. Обозначим через Z7 область определения функции / и пусть Му - совокупность всех машинных слов вида giOl*, а 31и - совокупность тех машинных слов gOl-, для которых X f U. Ясно, что Ми есть пересечение рекурсивно перечислимой совокупности £fin и рекурсивного множества 31 у. Но если пересечение рекурсивно перечислимой совокупности и рекурсивного множества 1>г-уни-версально, то (см. п. 8.1) совокупность также ?»г-универ-сальна, что и. требовалось.

Хотя теорема 1 сформулирована для одноместных функций, ясно, что аналогичная теорема верна и для многоместных функций. Известно что область определения функции Клини К {х, у) ш-универсальна (п. 8.1). Поэтому машина Тьюринга, вычисляющая К (х, у), универсальна.

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

Пусть S5 - какое-нибудь множество слов в произвольном алфавите В. Проблемой вхождения для ?8 называют проблему отыскания алгоритма, с помощью которого для любого слова р в алфавите В можно узнать, входит р в S или нет. Говорят, что проблема вхождения для лшоже-ства аз разрешима на машинах Тьюринга, еслп существует машина Тьюринга £, обладающая следующими свойствами:

а) Алфавит В входит во внешний алфавит А машпны £, А содержит символ О, не входящий в .В, 1 - символ пз В.

б) Для каждого слова р в алфавите В, если р б S, то машпна £, начав работать в конфигурации дОр, после конечного числа тактов работы переходит в заключительное состояние goOlO ... 0. Еслп же р (: S5, то дтшина £ из состояния дОр переходит в зак.лючптельное состояние доО . . . 0.