Рассмотрим теперь какие-нибудь частичные словарные функции G и Ну, . . ., Йр соответственно от /г и от /г -Ь 2 иеремешых, заданны в алфавите А. Результатом операции словарной примитивной рекурсии над функциядш G, Ну, . . Hp условимся называть (п + 1)-местную частичную словарную функцию F, которая для любых слов fi, • ! In, \> в алфавите А. удовлетворяет равенствам

Fin, • ; Vn, m) = Hi{£i, • • •, Рп. t), F{n, • • Ртг. О))»

(Il. • . . In, »)ар) = Яр(х1,.. ., fn, t), .. ., 5„, t))).

Легко убедиться, что для каждых G, Ну, . . ., Hp функция F суш;ествует и единственна.

Теорема 1. Пусть словарная функция F получается посредством словарной рекурсии (2) из всюду определенных словарных функций G, Ну, . . ., Пр. Тогда числовая функция /, представляющая функцию F, может быть получена из функций g, hy, . . ., hp, представляющих G, Ну, . . ., Hp, и простейших числовых функций конечным числом операций подстановки и примитивной рекурсии.

В частности, если заданные словарные функции G, Ну, . . ., Hp примитивно рекурсивны, то получающаяся из них с помощью словарной рекурсии функция F также примитивно рекурсивна.

В самом деле, из (2) для любых натуральных Ху, . .. . . ., Хп, у получаем

/ {Ху, . . ., Хп, 0) = g (Ху, . . ., Хп),

/ [ху, . . ., Хп, py + i)= hi {ху, . . .,Xn,y,f (ху, . . ., Хп, у))-

Равенство (4) можно представить в виде

1{ху,. . .,Xn,z) =

hi {ху, . .., Хп, [z/p], f{xy, . ..,Хп, [zip])),

если Z - p[zlp] = l = i, 2,.. ., р - i,

hp (ху.....х„, [z/p] 1, / {.Ту, Хп, [zip] 1)),

еслп z p[z!p] = 0.

откуда

j{Xy,...,Xn,z) =

Р-1

= hx{xy,.. ., Хп, [z]p], f{xy,. . ., Хп, [z/p]))sg\% ~

- {z-p[zip])\ + hp{xy,..., Xn, [zlp]~ 1,

/ {Xy, ...,Xn, [zip] 1)) 1 Z p [zip] I .

Равенство (3) и последнее соотношение составляют Б совокупности схему возвратной рекурсии для функции/, рассмотренную в п. 3.2. Поэтому согласно доказанной в п. 3.2 теореме функция / может быть ползптена из заданных функций g, hy, . . ., hp и простейших функций опера-цпями подстановки и примитивной рекурсии.

Рассмотрим, наконец, операцию минимизации для словарных функций. Пусть F (5, t)) - некоторая частичная словарная функция, заданная в алфавите А = {ау, . . . . . ., ар}. Если бы мы захотели определить значение выражения

WiFih) = A) (5)

так же, как для числовых функций, то пришлось бы говорить о наименьшем слове t), удовлетворяюп1;ем условию F {х, V)) = А, т. е. пришлось бы пользоваться нумерацией всех слов в алфавите 4, что не всегда желательно. Поэтому вместо одной операции минимизации (5) мы введем операцию минимизации по каждой букве алфавита а, и будем через

lial (F (f, а?) = Л)

обозначать такое слово я" = аа; . . . Ui {п букв), что

(?, я?) = А л F (j, (й) определено и отлично от А для S<п.

Т е о р е ма 2. Пусть / {х, у) - представляющая час-пичная7функция для частичной словарной функции F (г, 11), определенной в алфавите А= {ау, . . ., ар}. Тогда представляющая функция g {х) для частичной словарной Функции G {х), возникающей из F словарной минимизацией

G (?) = val {F (J, а?) = Л),1

•Южет быть получена из f и примитивно рекурсивных Функций операциями подстановки и минимизации. В част-

ности, если словарная функция F (f, t)) частично рекурсивна, то и функция G (р) также частично рекурсивна. Действительно, по условию имеем

g (х) = ciml (af {х, cal) = А) =h (щ (/ {х, h (t)) = 0))), где

/I (i) = са = г + ф + . . . +

- числовая примитивно рекурсивная функция.

Теперь с помощью теоремы 1 докажем примитивную рекурсивность некоторых часто встречающихся словарных функций. Начнем с функции F (f, t)) = ft). Так как

pA==f=r}(f), p.t)ai = ft)-ai-=j(?t)) Ц = 1,...,р)

и функции ll. Si примитивно рекурсивны, то функция jt) в силу теоремы 1 также примитивно рекурсивна.

Пусть 5" - обращение слова р, т. е. есть слово, полученное из р записью всех его букв в обратном иорядке, например, {aia2a-i)~ = ааа. Из соотношений

Л~ = Л, (га(Г = = (?)

видим, что р" есть примитивно рекурсивная функция от f.

Следствие. Если словарные функции G, Н, . . . . . ., Hp примитивно рекурсивны и

Fi(ri,. .., A) = G(fi, ig, Fi(ri, . . ., 5„, а;{)) = Я,(Г1, .. ., f„, t), Fi{xi, . . ., t,„ \))) {i==i, . . . , p),

mo словарная функция F также примитивно рекурсивна. В самом деле, из этих соотношений следует, что функция

F{Xu--; fn. t))=l(?b---. ?n. t)~)

удовлетворяет соотношениям (2) обычной словарной рекурспп п пото.му F примитивно рекурсивна, а вместе с нею будет примптпвно рекурсивной и функцпя

Fl . • ., fn, 0) = • • in,

По аналогии с числовой функцией sg х введем словарную фзнкцию Sgyt), полагая

ГА, t) = A,

f t) =

A(f) =

f - t), есл::, x - t) существует, I, если f - t) «e существует также примитивно рекурсивна. Для этого введем функции А, если f - flj существует, а,, если X - а-, не существует. Соотношения

а(Л) = а;, 1>,-(гаО = Л, а(1-а,-) = а, (/#0

показывают, что функции 2); (г) примитивно рекурсивны. Введем еще функцию D [х, t)), полагая по определению

D{x, А) = А, D{x, a,-t)) = i>(f, V))D,{x -t)). Пз этих равенств непосредственно видно, что

D (г, t)) = А г - t) существует. Но в таком сл5П1ае

f А, если г - t) существует,

Sgrl>(r, t)) =

[г, если X - 1) не существует.

Следовательно,

А{тс, t)) = (rt))Sgf-D(r, t)) и потому функцпя Д примитивно рекурсивна,

Из соотношений

SgfА = А, Sgft)a; = г

следует, что функция Sg примитивно рекурсивна.

Обозначим через f - t) решение 5 уравнения f = 5t). Если указанное уравнение решения не имеет, то значение выражения f - t) будем считать неопределенным. По аналогии с числовой разностью х - у полагаем

f - t), если f - t) определено,

Л, если f - t) не определено.

Одноместная функция f - заведомо примитивно рекурсивна, так как удовлетворяет соотношениям А аг == А, fa,- = f, Ui = А (j ф i).

Из тождеств

fA = f, fa-t) = (г t))

видно, что функция f -- t) примитивно рекурсивна. Мы хотим теперь показать, что функция

р„, если t)i А, t).2 7A,. .., t)„ = A, р„и, если !)17А, t)3A,. . ., 9„7А..

Так как

TFi (pi, Pa; Л) = Pi, Wx (pi, Pa; t)ai) = ?2,

TO функция TFi примитивно рекурсивна. Предполагая теперь известным, что для некоторого п функция JF„ примитивно рекурсивна, из соотношений

Wn+i (Pi. • • , Pn+a; Л, t)2., •.., t)7i+i) = Pi.

Wn+i(Pi, • •) Pn+a; t)iai,t)3, • • •) 1)71+1)==

= (Pa, . . Pnta; t)2.....l)»m)

видим, что функция TFn+1 также примитивно рекурсивна. Рассмотрим функцию F, определенную схемой

ГА, если рGt>,

Р, если pt),

где р б t) означает, что слово 1С есть подслово в t). Согласно определению имеем

(р,А) = р, (6)

А, если р б t),

Е{тс,щ)= Л, если p$t), P6t)ai, (7)

. р, если p(Jt), p$t)ai.

Но условие г б t) равносильно равенству (р, t)) = А, а условия ? t), ? 6 t)! равносильны соотношениям -Е (г, Х))Ф К, D (t)a;, р) = Л. Поэтому из (7) вытекает

Е{$, Yia,) = W2iA, А, р; J5(r,t)), В{г)а„ г)). (8)

Равенства (6), (8) показывают, что функция JS (г, t)) при1штивно рекурсивна.

Обозначим через Sb (р; t), j) результат подстановки слова J в слово р вместо первого вхождения t>. В частности

полагаем

Sb (А; t), J) = Л

Sb (р; t), J) = Р, если t) не входит в р. Ясно, что Sb (р; t), 5) «i,

Sb(pai;t),5)

если t) б р,

если t)p, ОбРЯг, (10) если J) р, t) ра;.

А(Р«г, t))5, pfli,

Соотношения (10) можно переписать в виде тождества

ЗЬ(раь J). 5) =

= W2 (Sb (р; J), 5) ai, А (paj, t)) i, ра; .Е (t), р), (t), ра)).

Это тождество вместе с равенством (9) составляют схему словарной рекурсии для функции Sb. Так как исходные функции примитивно рекурсивны, то и функция Sb примитивно рекурсивна.

Наконец, обозначим через Sb,, (р, t)) результат подстановки в слово р слова t) вместо каждого вхождения в р буквы а. Например, Sb (р. А) есть результат вычеркивания из р всех вхождений буквы а. Далее, Sb,, (р. Л) = = р равносильно условию, что р вообш;е не содержит буквы а и т. д. Очевидные тождества

Sba. (А, t)) = л,

Sba. (рая t)) = Sb„. (р, t)) aj (у ф t),

Sba. (pa;, t)) = Sba. (p, t)) t)

показывают, что все функции Sba (р, t)) являются при-штивно рекурсивными.

11.3. Прямое определение класса частично рекурснвных словарных функций. Как уже отмечалось, основной недостаток введенных в п. 11.1 определений прпмптпвнсп п частичной рекурсивностп словарных функцип состоит в том, что эти определения зависят от нумерации слов. Рассмотренные в п. 11.2 операцип подстановки, словарной рекурсии и словарной мннпмпзацпп свободны от этого недостатка п hotomj могут быть использованы для того, чтобы нолчить новые, пнварпантные определенпя jTsaaaHEHX понятий. Искомые определенпя содержатся в следующих теоремах.

Теорема 1. Для того чтобы определенная в алфавите А Словарная функция F (Ji, . . ., у„) была примитивно рекурсивной, Необходимо и достаточно, чтобы она могла быть получена иа про-<тейших словарных функций О, S, Х, конечные!, числом словарных рекурсий и подстановок.

Полагаем по определению

ТГ„(Г1, • Рпм; t)i, • •., t)n) =

pi, если t)i = A,

5-2, если t)i7bA, 1)з = Л,