1611678200-36438fb4f1ee6f855c93dc4a315ea8eb (826633), страница 52
Текст из файла (страница 52)
,iп-l)=ik, i1, ... in-l Ew.по1)Отметим, что еслиfоднозначно в случае, когдаf -частичная функция, то ее местность определенаfне является нигде не определенной. Нигдене определенные функции местностиkиmдля любыхk, mЕ w равны.Гл.2547.ВычислимостьКак легко видеть,Го= (х1 ~ О/1 [хо, х1],Гч:= (хп ~ Xk) 11 [xo, ... , Xn-1, Хп]•(2) Пусть D ~ wn и бi ~ wk, где i ~ п. Если Н: D --. w и gi: бi --. w,гдеi<п, являются частичными Е-функциями,б ~{zIz= (io, ...
,ik-1) Еnдj, (go(z), ... ,gп-1(z)) ЕD },j<nто следующая функцияh:б--. wявляется Е-функцией:zЕ б.h(z) = H(go(z), ... , gn-t (z)),Действительно, если ГнIPi, i < п, то= Ф 11 [х]и Г9;= rpf[y], i < п,для Е-формулФ иДля дальнейшего изучения Е-предикатов и Е-функцией на П важнойявляетсявозможность<<кодирования>>пар,троек,... ,всехконечныхпоследовательностей натуральных чисел натуральными числами с помощью Е-функций на П. Начнем с <<кодирования» пар.(3) Функция с: w2--.(с х,уw, определенная по формуле) ~ (x+y)(x+y+l)2+х,взаимно однозначно отображает w 2 на w (см. рис. 1).Формальное доказательство оставляем читателю в качестве упражнения. Заметим только лишь, что с соответствует <<пересчету» (т. е.нумерации) всех упорядоченных пар натуральных чисел в соответствии с рис.(х,у) является суммачисла парl. Именно: номером с(х,у) пары(и, v) таких, что и + v < х + у; это(х + у)(х +у+ 1)/2 и первой координаты х.число равно величинеСледствие7.2.l.Существуют функцииl: w--.
wтакие, что для любых х, у Е w выполняетсяl(c(x, у))=х,r(c(x, у))= у,c(l(x), r(x)) =х.и r:w--. wЕ-предикаты и Е-функции на§ 7.2.(0,0) -(0,1)(0,2)(1,1)(1,2)(2,0)(2, 1)(2,2)(3,0)(4,0)~255(0,3)~1/~/1/(1,0)n(0,4)(1,3)/(3,1)/Рис.1Замечание7.2.2.Для любых х, у Е w справедливос(х, у) ~ х, у,с(х, у)с(х,у)=х=улишь в случае х =у= О,лишь в случаях х=l(x) ~ х,l(x) = х лишь в случае х = О,r(x) ~ х,r(x) = х лишь в случаях х = О(4)Функции с,lиrО и (у= О или у=или х1),= 1.являются Е-функциями на П.Действительно, легко проверить, что еслиФ(х, у,z) ~ :3и(и +и~ (х+ у)(х + s(y)) /\ z ~и+ х),Гс~ Ф 11 [х,у,z], Г1 ~ (:3уФ) 11 [z,х], Гr ~ (:3хФ) 11 [z,у].256Гл.7.ВычислимостьРасширим сигнатуру ао до сигнатуры а, ~ ао U (с2 , 11 , r 1) и алгебраическую систему n обогатим до r2 1 так, что сп.
1 = с, zn. 1 = l и rn. 1 = r.В соответствии с предложением5.8.6Е-предикаты (Е-функции) наn.будут Е-предикатами (Е-функциями) наВ(х, у,z)n,Рассмотрим до-формулусигнатуры а,:::Jw::,; l(x)(s(s(c(z, y))r(x))w/\\/и,,;;zC иz--+ ~=3w:=:::JV\/u::,; l(x)\/w~:=:::Jl(x))/\l(x)(s(s(c(u, y))r(x))w~ l(x)Г(s(s(c(u,y))r(x))wи соответствующий ей предикат вп. 1 [х, у,:=:::J:=:::Jl(x)))Vl(x)) /\ z :=:::JО)z] на r2 1 •(5) Предикат вп., [х, у, z} является графиком функции /3: w2 --+ wk Е w и по, ... , nk Е w существует т Е wтакое, что /З(т, i) = ni для всех i ,,;; k.такой, что для любыхПроверим сначала, что вп. 1 [z, у, z] является графиком. Пусть п, т ЕЕw.Возможны два случая.Случай1:существуетЕ w такое, что числоk= (c(k,m) + 1)r(n) + 1 делит l(n),т.е.
существуетs(s(c(k, m))r(n))wВыбираем наименьшееkoметим, что в этом случаеr(n) =О, тоko =О. Еслиs(s(c(k, m))r(n)) =w такой, что= l(n).такое, что s(s(c(ko, т))r(п)) делит l(n).ko ~ l(n). Действительно, если l(n) = Оr(n) -=f. О, тоko,,;; c(ko, т) < s(c(ko, т)) ,,;; s(c(ko, m))r(n) < s(s(c(ko, т))r(п)) ,,;;Заилиl(п).Следовательно,n,р=::Ju::;; l(n)::Jw,,;; l(n)(s(s(c(u, m))r(n))wи если (п, т, k) Е вп. 1 [х, у, z], то kСлучай2:несуществуетk=:=:::Jl(n))k0 .сосвойством,указаннымвслучае 1. Очевидно, имеем лишь (п, т, О) Е вп.
1 [х, у, z]. Таким образом,вп. 1 [х, у, z] - график двуместной функции, которую обозначим через /3.Докажемвторую частьутвержденияmax{c(ni,i) + 11 i ~ k} ичисла ja + 1 и la + 1 взаимнос~(5).Пустьпо,... , nk Е w,j <l ~ са= с!. Покажем, что при О::;;просты. Предположим противное: пусть(la + 1) - (ja + 1) = (l - j)a. Тогдаl - j ~ с, получаем, что р делит а = с!.простое число р делит их разностьр делитl- jили а. Но так какТак что в любом случае р делит а. Но тогда аа' Е w иja+ 1=(ja')p+1Приходим к противоречию.= ра'для некоторогои это число не может делиться на р.§ 7.2.'Е-предикаты и 'Е-функции на П257ПолагаемЬ ~ П ((c(ni, i) + 1)а + 1),т ~ с(Ь, а).i,;;_kПокажем, что m таково, что /З(т,i) = ni для всех i ~ k.s(s(c(ni,i))a) = ((c(ni,i) + 1)а+ 1) делитЬ (а=Предположим, что для некоторого и~ ni числоs(s(c(u, i))a) также делит Ь.
Так как и~ ni, имеем с(и, i) ~ c(ni, i) < с.Ввиду взаимной простоты чисел вида ja + 1 и la + 1 для j # l < сполучаем, что с( и, i) + 1 должно совпадать с некоторым с( nJ, j) + 1 дляj ~ k. Но если c(u,i) + 1 = c(nJ,j) + 1, то c(u,i) = c(nj,j), i =j, и и== ni. Таким образом, ni является наименьшим из таких z (~ Ь = l(m)),что s(s(c(z, i)r(m)) делит l(m). Поэтому /З(т, i) = ni.Пустьk. Тогдаr(т), Ь = l(m)).l~Функцию/3,числообычно применяемую для кодирования конечных последовательностей натуральных чисел, используем лишь один раз длявведения более удобного кодирования.(6)Следующаядвуместнаяфункцияl*:w 2 --+ wявляетсяI',-функцией на П, (на Щ:Цп,О)Цп,Установим, чтоl*k + 1)z)= l(Цп, k)),п,kЕ w.есть I',-функция на П 1 , где П 1сигнатуры ст; ~ ст U (/3 2 ) иА(х, у,= п,/Jri; = /3.-обогащение П 1 доРассмотрим следующую I',-формулу(сигнатуры ст;)::Jи(/З(и, О)~ х А Vv ~ у(/З(и,s(v))~ l(/З(и,v))Аz~ /З(и, у))).Нетрудно проверить, что Г 1 • = лri; [х, у, z].Замечаниеесли-7.2.3.
Справедливы следующие утверждения:l*(n,i) > О, то Цп,i + 1) < Цп,i), и Цп,i) =Опри i~ п;l*(Цm,i),j)=Цm,i+j),m,i,jEw.Определим функцию Г: w 2 --+ w по формуле Г(х, у) ~ r(Цх, у)).Поскольку Гг = :Jи(Л(х, у, и) А z ~ r(u))ri; [х, у, z], справедливоСледствие7.2.4.Функция Г является I',-функцией на П 1 (П 1 ).Пусть ст2 ~ ст; U (Г 2 ) и П2 - обогащение Щ до сигнатуры ст2 такое,что гri 2 = Г. Покажем, что функция Г обладает тем же важнейшимсвойством, что и функцияq1() ЛFnнюн. Е. А.
Палютин/3.258Гл.(7)Г(m,i)Вычислимость7.Для любых по, ... , nk Е w существует т Е w такое,= niдля всехчтоi ~ k.Действительно, легко проверить, что Г(m,i)= niдля всехi~k,еслит ==; с(с( ... с(с(О, nk), nk-1), ... , n1), по) ....__._...,k+IДля Г справедливо более сильное утверждение.(8)Функция Г обладает следующими свойствами:f:w--, w такой, что f(i) = О для всехkJ Е w, существует т Е w такое,что Г(т, i) = f(i) для всех i Е w;если то -/=- т1, то существует i Е w такое, что Г(то, i) -/=для любой функцииi> kJ,-/=- Г(т1,и для подходящегоi).Первое свойство вытекает из того факта, что если т выбрано дляпоследовательности по==;тельстве(7), то Г(m, i)f (О), ... , nk 1= f(i)==;для всехf (kJ)так же, как в доказаi Е w.Второе свойство легко вытекает из следующего общего свойства,проверяемого индукцией поk:для любыхm, kЕw, k -/=-О, имеет местосоотношениет= ,,___,,..._,с(с( ...
с(l*(т, k), Г(т, k -1)), ... , Г(m, 1)), Г(m, О)).kЗамечаниеГ(т, k)f:=w--, wвзаимно7 .2.5.Для любыхmЕw и k ~ т верно равенствоО. Следовательно, соответствие ттакая, чтоf(i) =Г(т,i)для всеходнозначным соответствиемодноместными функциямиfнаw,i.лiГ(т, i) (= функцияw), где т Е w, является1---+Емежду натуральнымичисламии<<стремящимися к нулю на бесконечности,> (т. е. такими, что существуетkJсо свойствомf(i) =О дляi > k1 ).С функцией Г можно связать также некоторую эффективную нумерацию семейства всех конечных подмножествw: для любого п Е w- конечное подмножество w,k Е Fn ==:;,- k ~ п.
Если F ~ w конечно и XF: w --, w - характеристическая функция F, т. е. XF(n) = 1 при п Е F и XF(n) = О при п ~ F, тосогласно замечанию 7.2.5 существует m Е w такое, что Г(m, i) = XF(i)для всех i Е w. Следовательно, F = Fm.полагаем Fn ==; {kI Г(п, k) = 1}. Тогда FnУкажем еще ряд свойств класса частичных ~-функций, попутноопределяя необходимые понятия.§ 7.2.~-предикаты и ~-функции наn259Определение. Пусть Н: D --+ w, D ~ wn+I.
Функция h: /j --+ w,8 ~ wn, получена из Н минимизацией (h(x) = µуН(х, у)), если (io, .... . . , iп-1) Е 8 тогда и только тогда, когда существует i Е w такое, чтодля всех j < i выполняетсяпричем--+(io, ... , iп-1,j) Е D,H(io, ... , iп-1,j) #(io, ... ,in-1,i) Е D,H(io, ... ,in-1,i)h(io, ... , iп-1)=iдля этогоО,= О,i.(9) Если Н: D --+ w, D ~ wn+I, - частичная Е-функция, а h: /j --+w, 8 ~ wn, получена из Н минимизацией, то h также являетсячастичной Е-функцией.Если ГнГh= Фn[хо, ...
, Xn-1, Xn, Xn+1J= (Ф(хо, ... , Xn-1,0)для Е-формулы Ф, то/\\/у~ Хп(У ~ Хп VV :3z(Ф(хо,... ,Xn-1,z) /\ ~ z ~ O))n[xo, ... ,хп].Определение. Пусть h: до--+ w, 80 ~ wn и Н: D--+ w, D ~ wn+ 2 .Функция g: 8--+ w, 8 ~ wn+I, получена из h и Н примитивной рекурсией, если-(io, ... ,in-1,0) Е 8 тогда и только тогда, когда (io, ... ,in-1) Е до,g( io, ...
, iп-1, О) = h( io, ... , iп-1);для i Е w соотношение (io, ... , iп-1, i + 1) Е 8 имеет место тогда ипричем в этом случае-только тогда, когда(io, ... ,in-1,i) Ед(io, ... ,in-1,g(io, ... ,iп,i),i+ 1)ЕD,причем в этом случаеg( io, ... , iп-1, i+ 1) = Н( io, ... , iп-1, g( io, ... , iп-1, i), i + 1).(10) Если h: до--+ w, до~ wn и Н: D--+ w, D ~ wп+ 2 , - частичныеЕ-функции, а g: /j --+ w, 8 ~ wn+I, получена из h и Н примитивнойрекурсией, тоg-частичная Е-функция.Пусть Гh = Ф~[хо, ... ,Хп-1,У] и Гн = Фf[xo, ... ,Xn-1,Y,Z,u] для'1! сигнатуры а2:подходящих Е-формул Фо и Ф,.
Определим Е-формулуw(xo, ... 'Xn-1, Xn, Xn+I) :::::; :3v\/y ~ Хп:3z(Фо(хо, ... 'Xn-1, Г( V, 0))/\/\(у~Xn V Ф1 (хо, ... , Xn-1, Г(v, у), у+ 1, Г(v, у+ 1))) /\ Xn+I ~ Г(v, Хп)).Нетрудно проверить, что Гg9*=wП 2 [xo, ... ,Xn-i,Xn,Xn+IJ-Гл.260Замечаниетоg -7.ВычислимостьЛегко убедиться, что если7 .2.6.hи Н-Е-функции,Е-функция.Определение. Пусть Q ~ r.,i - k-местный предикат. Характеристической функцией XQ: wk -+ w предиката Q называется функцияXQ(i)i=для любого(l l)Еслифункцияi Е Q,О,i ~ Q,(io, ...
, ik-1) Еwk.Е-предикат наQ -= Фr[хо, ... , Xk-1],u)k \то его характеристическаяQ,n.является Е-функцией наXQПусть Ql,={= Фf [хо, ... , Xk-1]Qдля подходящих Е-формул Фо и Ф1. Еслито Г XQ= Фn[хо, ... , Xk-1, хk]-Определение. Пусть Q ~ wk -k-местный предикат. Частичнойхарактеристической функцией предикатаXQ: Q-+ wтакая, что( l l ') Если Q ~XQ(i) = lXQЕдля всехj#n,то его частичная харак~ s(O))n[xo, ... , Xk-1, Хk]-Далее понадобится функция ch: w3= Г( п, j)называется функциято= (Ф(хо, ...
, Xk-1) /\ Xkсвойством: для любыхQQ.является частичной Е-функцией.= Фn[xo, ... ,Xk-1],Г хЪiЕ-предикат наwk -теристическая функцияЕсли Qдляn,mEwi и Г( п', i)-.если= т.w, обладающая следующимn'=ch(n,m,i),то Г(п',j)=Нетрудно проверить, что этафункция удовлетворяет следующим соотношениям (и ими характеризуется): для всех п, т,iЕw,ch(n, т, О)ch(n,m,i= c(l(n), т),+ l) = c(ch(l(n),m,i),r(n)).Это определение напоминает определение примитивной рекурсии, однако таковым не является, так как во втором соотношении встречаетсянеch(n, m, i),аch(l(n), т, i).Тем не менее, рассуждая аналогично,§ 7.2.Е-предикаты и Е-функции на П261как в случае примитивной рекурсии, можно установить следующеепредложение.(12) Функция ch: w3----+w является Е-функцией.Пусть----+ Г(и,у) ~----+:3z(s(z)~r(y)c(l(l(y)),x1))Л Г(и, у)~ с(Г(и,ЛCr(y)~0----+c(l(l(y)), z)), r(l(y)))))]ЛЛхз ~ Г(и,с(хо,х2)).= Ф 112 [хо,х1,х2,хз].Тогда ГсhПрежде чем сформулировать и доказать главное утверждение настоящего параграфа, отметим следующий достаточно очевидный факт:(13) Алгебраическая система П является ограниченной (в смысле§ 5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
