Математическая логика. Шапорев С.Д (1019113), страница 52
Текст из файла (страница 52)
Воспользуемся функцией гсвг(х,у), гсвг(х,у)=0, если х делится не у без ос»вткв, и гезт(х,у)> О, если не делится без осштка. Таким образом, если ! — делитель х, то швг(хН)= О. Нужна подачитать лишь число нулей при ! =1,2,...,х. Это можно сделать с помощью функции (1,х=О зйп(х)=~ ' . Итак, т(х)=~зйпгевг(х,!).Функцию т(х) ула- (О,х >0 лось представить суперпозицией примитивно рекурсивнык функций, следовательно, сача она»акже примитивно рекураивна; в) п(х) — число прость»х чнаел, не превоаходящих х. Ваапользуемся только что полученной функцией т(х), Все простые числа делится без остатка толька на себя и единицу; асатавные же имеют больше делителей.
Если число делителей чиала уменьшить на два, то для простых чисел пгжучим нуль. Осталась как в прелыдушем пункте (б) подсчитать число нулей. Следовательно, и(х) = 4, вйп((т(г) — г!), »ы при этом единица иа считается простым числом. Таким образом, опять удаасаь предо»явить функцию и(х) в виде ауперпозиции функций х Е у, ~з(, зйп(х) т(х), которые примитивно рекураивны; Глава ГО Геа яяел ьке г) Ог(х) — число простых делителей числа х. 18(0) = О.
Зта функция по строению похогка на предылущую л(х) 1шли у — простое число, то т(у)= 2, если при зтач аргумент х делится на зто простое число без остатка, то геяг(х, у)= О, в противном случае сумма ~ г(у)- 2~ + гез1(х, у) > О. Тогда 1й(х)= 2,яйпйт(!) — 2~+глаз(х,1)). 18(х) — примитивно р». курсивна, т, к, прелставляет собой суперпозицию примитивно реку!шинных функций', д1 здесь не обойтись без привлечения операции минимизации Пусть л(у) — число простых чисел, ие превосходящих у.
Тогда поскольку в данной функции р(х) нумерация простых чисел начинается с нуля, то уравнение л(у)-(х+ 1) = 0 выполняется лишь тогда, когда очередное простое число будет х-с по счету. Действительно, пусть, например, х = 4 . Четвертое простое числов зто 11. р(4) = р„[!л(у) †(4 + !) = О], у = О, /н(0)- ~ = 5 ы О, у = 1, ]л(1)-5/ = !О -~ = 5 и О, у = 2, ]л(2)- 5] = ]! — 5] = 4 и О, у=3. ]л(3) — 5!=]2-5]= 3ИО, у =4, ]к(4)-5]=/2-5/= 3ИО, у = 5, ]л(5)-5] =]3-5~ = г и О, у = б, !л(б)-5/ =]3 — 5] = 2 и О, у = 7, ]л(7)-5] = ]4 — 5] = 1 л О, з = 8, /л(8) — 5! = /4 — Я = 1 и О, у=9, !н(9)-5!=!4-~=1иО, у=10, /л(10)-5!=/4 — ~=! ыО.
у =11, ~н(11) — 5~ =]5 4=0 у =1! Р(4)=11 Поскольку использовалась операция чиниьгизацин, иеабходиью применить теорему 5 3. Для зтого надо составить примитивно р»- кУ1юивнУю мажоРантУ П(хи хм.,.,х„). В ~мшем слУчас Рг[~л(У) — (х+1] =0]оп(х).
Проще всего взять быстро возрас- тающую показвтельную функцию, например, 2 . Зта функция примитивна рекурсиапа !без доказашльства). Тогда так как р []к(у) — (хе!1=0]52Х, то р(х)=р„[~л(у)-(хь!)=0]— приьгитивпо рекурсивная функция; Ча ы Г» Оаюпг, ения, еааания е) эта функция определяется аналогично !ч'х] 1см. роэф 5.31 ьюжно взять 2х,т. к.
Г2х < 2х. Вычислив», например, [Л 4[= 5, т=О, 1 — 32=0, зйпО=ОЫ1, т=1, 4 — 32=0, вйпО=Ои1, я =2, 9 — 32=0, зйпО=Ои1, я=3, 1б — 32=0, зйпО=Ои1, х=4, 25 — 32 =О, зйпО= 0 и1, я = 5, Зб †32, абп4=1, х = [ Г2х4]= 5. По теореме 5,3 функция примитивно рекурсивна; ж) С» должна быль целочисленной функцией, поэтому определим сс через функции [х], зйп(х) и збп(х) таким образом, чтобы С,' =1 х» '-[-)+-)-- 1(х уЦ С» получена суперпозицией функций х1, [х], вйп(х), вйп(х), ~х — у[, хе у, х — у, поэтому являсгся примитивно рекурсивной.
5.44. Пусть»'(х,,х»„.,х„) получена суперпозицией и по схемам примитивной рекурсии с использованием функций 0(х) = 0 и 1„(х„х„, к„) Тогда для этой функции должны быть справедливыми следующие соотношения: а) Т'(0,0,...,0)=0; б) сели х, 51, г = 1 л, то У(х„х», „х ) <! . рассмотрим у,(х)= хч1. Эта функция не удовлетворяет условию 1а); »'з(х)= 2х не удовлетворяет условию !6) при х = 1.
Глав 10 Творю влгорипюв вв, 5.4.5 Пары натуральных чисел чожно разложить в простую последовательность разными спосабамн Рассмотрим та ппыываем»й канторовский способ. (0,0); (О,!), (1,0); (0,2), (1,!), (2,01, (О,З), (1,2), (2А ), (З,О!ь.. 8 этой последовательности пары чисел идут в порядке возрастания суммы их членов, а из пар с одинаковой суммой членов ранынс идет пара сменыним первым членом.
Начнем нумерациго пвр с нуля и обозначим череп с(х,у) номер пары (.с, у) в этой последовательности. Число с(т, у) называется ьошяороесккн ланерои лоры (э,у) Обозначив» через!(и) и г(п) левый п правый номер пары с номером л и найдем вид функций с(х, у), !(л) и г(п) Пара (х, у) находится пв отрезке (О т -ь у)(1 х»-у)...,(х+ у)...,(х ь у — 11)(т»- у О) иа .т-м месте после пары (О х+ у). Перед парой (О х+ у) в кангоровской последовательности находятся х»-у отрезков (отделены друг от друга точкой с запятой), содержащих всего 1+2+3+...+(х+у) пар Поэтому ! Ь+»( «+1, 1*.:.(л,г 2 2 Осли теперь т=!(п), у.= г(п) и н =г(х,у),то 2л =(х+ у) +Зх+у, 8п+1 = 4(хе у) +!2х+ 4у+1 = (2л т Зу) +12х+ 4у+! = 4х'+8ху+ т 4у'+4х+ 4у+118т =(2х 2уь1) +8 = (2г+2гьЗ) — бу-б, т.е. (2х+2у+!) +8х =8л+1=(2т+2ут3) — 8у — 8.
Уменьшим левое вырезке»»ггс и увсяичим правое: (2х+2у+1) <8п+1< (2т+2у+3) . 2х+ 2 у+1< (э(8» ь1)< 2т+ 2у т 3 (Дгг+1)т! нли х+ у+1«х+ у+2. 2 ([~З..4 11 Слез»сеятель»»о, .т+ у+1 =1(п)+ г(в)+1 = 1 ! М8л-ь(]»-(1 Пусгь А= ,то~да я+ у= А — 1 и из уравнения г с(т,у)= ' (х+ у х+ у+1) +х пояу ~ась» 2.г = 2п — Л(Л вЂ” 1), 2 Чвся д Огееие евммщ «аевиия А=х+у+1 [/8и+ !] — 1 [ г — ] ~ — л 2 2 у = (А — 1)- х = г(и) =— ! 2 [/Зп+ 1] ! 2 ( ) 1 [[Сгйл Е1]+1 2[ 2 Итак [Ди+ 1]-'1 2 ! у = г(и) =— 2 рай ] 2 Видно, что функции с(х, у), 1(и) и г(п) вырываются с помощью подстановок через элементарные арифметические функции х к+у х у !1х], [ — ],следователыю,онипримитнвнорекурсивны.
(2] Кроэзе того, из самого опредеяения функций «(т,у), 1(и) и г(н) как функций, связаннык с нумерацией пар, вытекавзт следующие тожчеетва: с(1(п) г(и))=п, 1(с(ау))=х, г(с(х,у))= у. Глава )О Те ияалго цюв 5.4.6. Рассмотрим схему возвратной рекурсии ! у (х,х,,...,х, пО) = гр(хохм..,,х„,) У(хо х„...,.т„„у+ 1) = Дх„х),...,х„„у, ((х„х„...,х„„ц (у +!)) У"(хох„...,хк паз(У 4 !)),...,У'(й,хм,,х„па,(У -;- !))) = где ц, (х) а, (х)... и, (х) — вс(оду определенные функции, удовлетворяющие всем значениям х при п,(х+1)<», 1=1,». Последоватсльносп чисел й)ибоначчи определяется уравнениями Г(О) = О, Г(О)= О, У(1)= 1, у(л42)-у(п)ту(л41) ~Д(пь1)=У(п)+/ л — ! ьзйю).
Действительно, у(0)=0. 1"(1)=у'(0)ьу" 0 — 1 ьзйп0=0+0+1=! г()=г(Ь)н ~- ° ()= () ( — ). Отсюда видно, чю функция у (л) возникает по схеме возвратной рекурсии из функций (р(х)=0, )у(х,у,х,,хт)=зйпть, +т, и функций о, (у) = у — 1, пз(у) = у — 2. Так как все з(и функции примитивно ре- курсивны, та функция у (г() также примитивно рекурсивна. 5 4уй а) в операции минимизации !си.рлзц 52) (Р(х,,х„...,х„)= =р (у(х,хз,,хе,у)фф] функции ф(х,,хз,...,х„) сч)пются неопределенной, если окажсгся, что Лля всех у /(х(,хз,...,х„, у)И й или для какого-го у 1(х,,х„...,х,,у) на определено Рассмотрим функцию 4)(х) = р, (Х(х)-» у = 0]. у= О, к(х) ту = хв1+ОиО, у =1, Х(х)4 у =х+1+! иО ит д.
Чаем Д Опмгы Гмнения уя аиия Очевидно, чтодля любого у а(х)тунО,т.е. гр(х) — неопределенная функция. Использована операция минимизации, слеловатеяьно, функция ф(х) частично рекурсивна; б) пусть у(х,у)=р,(~х — (хту1=0) и, например, х=4, у=2.
Тогда Х=О, )х — (с+у) =)4-(0+22 =))-2(= 2нО, Х=1, /х — (х+ У1=)4 — (1+2) =)т — Ч=!нО, х = 2, !х — (х + у) = !4 — (2+ 2) = /4 — 4( = О, т. е. 1" (х, у) = х — у = х = 2. Если же х=2, у=4, то Х=О, ~х — (с+у)=~2-(От4Х=2иО, г=1, (2 — (1е42=3нО, х=2, )2-(2т4)м4нО и т.д., т.е. у(х,у)=х — у неопределена Функция у(х,у) вычисляется через оператор минилэизации,значит, частично рекурсивна; в) 1'(х, у) = э не определена в остальных случаях. Пусть э' (х, у) = р, ~~х — хг ~ = 0~. Функция определена и вычисляется так 'ке, как в пункт» (б) 1.4.8.
С памоаэью нумераций пар натуральных чисел легко получить нумерации троек, четверок н т д. Введем следующие функции: сэ (х„хэ, хэ ) = с(с(хэ, хэ ) хэ ), с (хыхэ,хэ х„)= с (с(х, тэ)хэ хэ)" с (хпхэ,...,х э)=с (с(хэ,хэ)хэ, „х э). Число с (хпхэ,...,х„) называется «онтсровскин панелем и-ки чисел (х,,х„.,х„). Если с" (хпхы.,.,х4)= Г, то х„= э(Г), х„, = 4(1(Г)),.... .. = (1(- (1(г))-)). х, = 1(1( (1(г))-)) Действительно, пусть, наприьэер, л = 3 . Тогда с'(хпх,х,)=с(с(х„х,) х,)=г, х, =э4с(хпх,)хэ)="(г) с(тохэ)= 1(г), хз = э (!(г)) и хэ =1(1(г)).
Введем обозначениЯ с„(Г)= х„с„„,(Г)= х„,,..., се, (Г) = х, Тогда с"(сю(г)с„х(г)...,с„„(г))=г, с4„(с" (х,,х„,,х4))=х,. э'=1,ч. Эти формулы аналогичны соответствующим формулам задачи 5.4.5. зят Глава тс. Герека л пигмее Для получения основного резульгата задачи введем вспомогательную функцшо р(г,т)=свм(с„,(г)...,с„„(г) уу(с„г(г)...,с„„,(г) у)).
Пусть функция З (т„х„...,х„,х„, ) запагм примитивной рекурсией через функции й н й шким образом: 1'(х,,хт,...,.т„,О)= б(хг,.тз,...,.т„) /(х~ х„,...,х„,уз-1)=1г(хилз,...,х,,у, Г(хг,х„,х„, у)) Из функции йг(т,у) имеем 2(сю (Г)с„з (Г),...,с„, (Г) У) = У (хил„,х„, У) =- с„,з„„(ф(ГУ)) = = „з.„(.( („;, ..).)) Тогпазу(гб)=с" (с„,Ис„г(г),с,„(г)Од(с„г(г)с„г(г),...,с„„(г))),а з1г(г,Уч-1) = с""(сю(г)с„з(г) .,с„„(г)У,-1,1г(с„,(г)с„г(г)...,с„„(1) У, г,„,нз(йг(Г,У)))) Так как ф(Г,У-';1)=Ф(йг(Г,У)), гле функция Ф имесз вид Ф(и)= =-с' (се,з,(и)ся„т(п),с„,зям(н)з1,Б(смзг(гг)г„,зз(и),,с„,зоз(и))) Таким образом, функция У получается нз функций й,й,1,г; с, О,Л н 1, подстановкой и специалыюй рекурсией вида зр(з О)=П(х), зу(х,ут1)=Ф(гу(ху)), второе из уравнений коюрой прелставляет собой итерацию, т е. функция ф получена из Ф с по- мощью итерации 1сн рпзд 5,21 Заменим теперь функцию йг функцией Р посредством рекурсии Г(хО)=х.
Г(х,уе1)=Ф(Г(х,у)) Так как лля ф(х,у) и Г(т,у) справедяивы ссюгношения. гу(т,О) = С(х), чг(х,1) = Ф(йг(х,О)), зр (х 2) = Ф (йг(х 1)) = Ф (Ф(йг(х 0))). гу(т,з)= Ф(Ф(...Ф(йг(хб))..))=Ф(Ф(..Ф(С(х)). )); Г(з,й)= х, Г(х,1) = Ф(1г(х,о)), Часть Д Омвт», решения, аааиня г (х,2) = Ф (г (х,!)) = Ф(Ф(Р (х,О))), Р(х, у) = Ф(Ф(...Ф(г (х,О)) ..)) = Ф(Ф(...Ф(х) ..)), то »у(х у) = Е (О(х) у) .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
