Математическая логика. Шапорев С.Д (1019113), страница 34
Текст из файла (страница 34)
п. Могут быть случаи, когда не все функции !о 1;,...,„Г„, зависят от всех л ар. гуменюв х„х„...х„. В этих случаях для получения суперпозиции используются фиктивные аргументы и функции 1', (х», х»,...,х, ). Например, Глкюа тес я и лкп и ггл гр(л, У, г)= Ф(Д (х),Ут (х, У, г) У, х).=ь Ф(х„ хз,хз, хе ), Д(х)= Г(х,у,г)ут(х,утг)=тгт(х,р,г) Уз(х, ух)= Уз(ху,х) Г (х;у,х)= 1.,'(хух), причем используется суперпозини» Ф,Гт,ут,ут,Гь Примитивная рекурсия Пусть имеются дее функции гр(хт,хз,...,х„) и зу(хм хе,...,х„м ), и > 1.
Оп- ределим насую функцию У(О,.тт,»з,...,. „)=Ф(хз,х„,х„) И 2 1) У(У+1,х,хм..,,х„)= Ф(У,У(У,хт,хт,...,х„)хт,х„...,хк), у зависит от л яргументое, Ф от и — 1, я Ф от и+ 1 аргумента. ГОворят, что функция г получене из Ф и р по сжме лрюгилюелоа рекур- сии. Очееидно, что У интуитивно яычислимк, если Ф и Ф вЂ” интуитивно яычнслимые функции. Дейспнпельно, пусть Х, = ап Х = ат,...,х„= а„. Тсгдя У (О а,, а„,..., а„) = гр(аз, аз,..., а„) =- Ьс, Г(1 а„а„...а„)= Ф(ОЛ(О а„...,а,)а„,,а„)= Ф(О Ь„а„,а„)= Ь,, „У(2,а„ам,,а„)=Ф(1,У(1,а„...,а„)ат,...,а„)=Ф(1,Ьпа„,а„)=Ьт ит.д. В частности, длл функции двух переменных у" (у,х) будем иметь у"(О, х) = гр(х) ,. Если же аргумент у у коего один, то г(О) = и , где а — постояинел.
ГовоРЯт, что фУнкциЯ У(У,хт,хз,...,хл) пслУчкетсЯ из Ф(хз,хт,...,х„) и Ф(У у~ ут - у, хз,хз,...,х„) еозераюлойрагурсией, если оик может быть зеленя схемой ! У(О,хт,хз,...,х ) ь Ф(хт,хз -'«,) (У,У(п,(ут1)хз,хз,...,х„)... У(у+1,х„х,,...,«„)= гр( (..., У(а,(у т1)х„хз,...,.тч) хт,хз,...,хк где а,(у+1)< у, ат(у+1)< у,,а, (у+1)< у. те тзм Часп 1. У юмлючеаюаялоле Будеьг говорить, что функция у (х) получается из функции б(х) с помощью у(о)=о, гперации, и обозначать у (х) = 1б(х), юлн (у'(х+1)=д(у(х)) Встает вопрос: лля каждых ли частичных функций ф,ц от и — 1 н л+1 пе- ременных существует функция Г от и переменных, удовлетворяющая усло- виям примитивной рекурсии и будет ли такая функция единственной? Так как область определения функций есть множество всех натуральных чисел, то ответ на этот вопрос, очевидно, положителен.
Формулы примитивной ре- курсии символически изображают так: т =!!(ф,дг) и рассматривмот !! как символ двухместной операции, определенной на мнозщстве Р функций. Функция у называется просто лр мчтлело рекурснелои, если ее можно по- лучить конечным числом операций подстановки и примитивной рекурсии исходя лишь из простейших функций !ч0,1„. Операции подстановки 1су- перпозиции) и примитивной рекурсии, будучи применены ка всюду опреде- ленным функциям, дают в результате снова всюду определенные функции. Поэтому все примитивно рекурсивные функции всюду определены.
Функция г'(х„~,...,х„) называется частично рекурсивной, если сна может быть получена за коночное число шагов из простейшггх функций Х,0,1„" при помощи операции суперпозиции, схем примитивной рекурсии и операции минимизации. Функция У(~,хз.....х,) называется абщерекурсиелой, если она частично рекурсивиа и всюду определена. Г(б,х)= х, Пример 1. ' ' . При таком задании сразу видна ' (у"(уе1,х)=,г(у,х)+!' ф(х)=х, ио цг(х,у,я) надо устанавливать. по определению лриьги- тивиои реку1кии /(уе1 х)= дг(уУ(ух)х)=( ' ) = = гу(у, /(у я)з)= ( ) = ц(х у(х г) г)= = (у(ха) = у) = ц(х у я).
Но у(у+1 х)= У(у х)+1=(таккаку(у х)= у) = у+1. Ганы б Теория еге гмав ляг Итак, су(х,у,т)=у+1. Тогда числовые значения также легка нахо- дятая: Г(0,0) = О, У'(0,1) = 1, Г(0,2) = 2, У(10)= ы(О, Г(ОО)О)= ц (О О О)= 0+!= 1, У'(2 0) = су(1, у (1 0) 0) = цг(1 1 0) = 1-ь ! = 2, Г (30) = 3с(2, у (2 0)0) = су(2 2 0) = 2 т ! = 3, у(1!) = су(О,у (01)1) = су(011) =!т1 = 2, !"(2,1)=су(1,Г"(11)!)= !с(1 2!)=2+1=3, Р (3 1) = цг (2, ~ (2 1) ! ) = су (2 3 1) = 3 + 1 = 4, ! (12) = ср(0 У(0 2)2) = су(0 5З(2)2) = дг(0 2 2) = Г(02) Е 1 = 2+ 1 = 3, ! (2 2) = су(1, г(1 2) 2) = Г (! 2)+ 1 = дг(! 32) = 3 Е 1 = 4, Г"(3,2)= ср(2 Г"(22)2)=у(2,2)+!=су(2,4 2)=4+1=5 и т.д.
Помес- тим эти значения в зябл. 5.2.!. Интересно выяснить, квк аналитически выглядит функция ! (у,х) в этом примере. Иие- сьс Г (у е 1, х) = ! (у, х) т 1, алелавательно, Г(у+ я, х) = ! (у, х)+ х. Положим у=О, тогда У(я,.с)= Г(0 х)+к= х+ х, т.е. поскольку имя аргумента может быль любым, вюкно лишь ссо меато в функции ! (у,х)= у ах.
Тяйтнке 5.!.! Ч сп Г. Мами пяе кзл лепки Особенно отчетливо зго видно из способа вв~численил функции 5" (у,х), а именно: у (О, х) = .т, У(1,х)=15 У(о,х)= ! ел, у'(2,х) =1+ 5'(1,х)=14-(1 е х) = 2 ч-х, уз-х. У (3 х) = 1 с Дг х) = 1+ (2+ х) = 3+ х ~ у(о,х)=о, Пример 2...,, . Вычисляем функцию 15 позой (у (у+ 1, т) = у(у, х)+ х а=о жескеме у(у+1,х)=р(у,з (у,х)х)= у=х, =р(х,у,т).
5"(х,з)= у/ Аналогично, т. к. Г(у+1,х)= г (у,х)ч х, га .у (у + 1 х) = 9 (х у з) = у + з . Числовые значения вы числа ююа таким же образом. Например, 5"(0,0)= О, Г(0,!)= О, у'(0,2)=0, 5(1,0)= (ОМ,О)о)= (ооо)= + =, .У(2,0)= (!М1,0)0)= (1,0,0)=040=0, х(3.0)= (г,х(г,о)о)= (г,о,о)= У(!1) = Р(О, У(01) 1) р р(ОО 1) = О о! = 1, Х(21)=р(! У(1,!)1)= (1,1,!)=1 1=2, У(3,1)=р(г,у(г !)!)=р(2,2,1)=2+1=3, Х(1,2) = р(о,г'(о,г)г) = р(о,о,г) = о+ г = г, У (2 2) = гр(1, ~ (1 2)2) = р(1 2 2) = 2+ 2 = 4, .Г (3,2)= 3г(г,зг(2,2)2) = Р(1,4,2)=45-2 =б !см табл, 3 22) т алика 5Л2 Глав д.
Ге пня лгояипнм Згм ~енггя функции 1 при других значениях аргументов х и у могуэ быть вычислены аналогично. Определим аналитн ~вский инд 1(х, у). В этом случае Г(уе!х)= г(у х)эх, тогда /(уэзт)= 1(у х)+ х Опять полагая У=О, получим 2(х,х)= г'(О,х)тг х=О+з.х=с-х, т.с. эг(у,х)= у х. таким жс образом из способа вычисления э'(у,х) видна ее аналити люкая структура Г(б,х)=О Т(1,х)=.т+ У(О,з)= х -ь О, У'(2, х) = х + Д1, х) = х + х 1 = 2 х, у . х. /(З,х)=х-ь 1(2,х)=х+х 2=3.х,~ Пример 3. Рассмотрим ту же самую функцию, что и в первом пример», только заданную несколько иначе. Пусть 5(х, у)= х+ у и по схеме примитивной рекурсии она задана слсдуюшим образом: хтб=х, ( 5(хб)=х х+(у+!)= (х ь у)е! )5(ззуе1)=5(х,у)ь1 где 5(хО)=1,'(ь) 5(х,ув1)=ь(5(х,у))=р(х,у,г).
Таким образом, функция двух переменных 53х, у) получается по схеме примитивной рекурсии из функции одной переменной ф(х)= 1г(х) и функции трех переменных дг(х, у,г) = Х(5(х, у)) — оператора сдвига. Итак, вспомним сше раз определение примитивной рекурсии для функции двух аргумегп-ов 1перевычисляемый рекурсивно аргумент стоит 1 (х,О) = гр(э:) на втором месю!..., „.
В пашем случае Ях, у -ь 1) = гу (х, у, Т!х, у)) ( Оех=х =1,'(х) ибо Г(х,у+1)= х+(у+ 1)=1+(х+ у)=!+ ' эг'(ху)= 5(х, у)= х+ у, а грстий аргумент функции гу есть з, т.е. р(х, у, Г) = !я- Х . Зэо то гке самое, чго и а первом примере; там при замене переменных формула 1(у,х) стояла на втором месте в списке вргуьюптое формульг р(у,з (у,х)х), поэтому ранее мы получили дг(л.у, )=1+ у. При вычислении значений функции ! (х,у) это ие Чалим Маюматкчесмм лелем должно сказываться. Вмчислим опять несколько значений функции по формуле примитивной рекурсии: У(0,0)=0, „У(1,0)=1, Д(2,0)=2, У'(3,0)=3, 5(01)= У(00+1)=!+У(ОО)=зр(х,у,т)=ф(000)=1+0=1, 5(0 2)= 5(01+1)=1+ 1(01)= зр(0 11)=! +1= 2, 5(0 3) = 5 (О 2+ 1) = 1+ 5 (О 2) = зу (О 2 2) =! + 2 = 3, У(1 1)= У(1 ОЧ.1)=1+ ~(! 0) и еу(х,у,х)= р(1 О 1)=1+ 1= 2, Х(1.2)= У(1,!+!)и!+ У(!Д)= р(1,1,2)= 1сг=3, у(! 3)= у(! 2ь!)=1ч у(! 2)= р(! 23)=1+3 =4, У(21)=У(20С1)=!ела(20)=зу(202)=1+2 м3 итд, !табл 523!.
Теалиае 5.7.5 Получена та же таблица, что и в первом примере, только повернутая на 90' по отношению к первоначальной. Пример 4. Доквзать общерекурсивность функции Р(х,у) = х у. Зададим зту функцию следующей схемой примитивной рекурсии: Р(х, 0) = 0 х = 0 = О(х) Р(х,у+1)=х (у+1)=х у ах =хч-Р(х,у)= Б(х,Р(х,у)), т.е. Р(ж у) получаезся пз схеме примитивной рекурсии из функций 0(х) и о(х,у)=х-ту, которые сбщерекурснвны и, следовательно, функция Р(х, у) также общерекурсивна. Так как используемое здесь оп- 7 (х, О) = 0(х) = 0 ределение примитивной реку!юии имеет вид 17(х,у+!)-ч(х,у,У(мух) Глвщ 5 Теория алюлгпмов ДЯ5 х 0=0(х) а Р(.г, у) определена как, то вид функции р будет (х (уж!)=х у+.т следующий: Р(х ут1)=з (у ь1)= х ус х= хе с =зр(хух).
расчет ее значений даст такие же результаты, что во втором примере. (1, хиО, Пример 5. Доказать сбщерскурсианость функции зйп(х) = (О, х=О. Функцию вйп(х) можно определить с помощью простейшей рекурсии таким образом: ,()и зйп(0)=0, ~ зйп(0)=0(х) илн, где С,(у)и! зйп(у 4 1) = 1 (зйп(уз-!) = С (у)' Тогла по определению вйп(х) общсрекурсивиа.
Пример 6. Пусть дана функция 6(х, у)= х'. Олредслиьг «» по схеме х'=1, ( С(х,О)=С,(.г) примитивной рекурсии , или Таким образом, функция П(х,у) может быть получена ло схеме примитивной рекурсии из общерекурсивных функций Р н С,, следовательно, она сан» является общерекурсивной. Опредслиьг функцию р .
Так как 1(х,О)=С,(х)=1, .Р(;ус!)= р(х,у,.Г(х,у)) то ! (ху-';1)=хг"' =х" х=х х" =х г =х Р(х у)=р(х у х). Вычислим таблицу значений этой функциидля х=0,1,2, у=0,1,2,3 Г(0 0) = 0' = 1, „Г(1 0) = 1' = 1, / (2,0) = 2' = 1, .Р(1,!)=У(1,0ь!)=р(1,0,!)=! 1=1, 2'(1,2)= Р(1,1ь1)=дг(1,1,1)=1 1=1, !(1,3)= Р(1,241)=р(1,2,!)=1 1=1, г'(2,1)= /'(2,0т!)=р(2,0,1)= 2 1=2, Р(2,2)=я (2,1 е1)=р(2,1,2)= 2 2=4, Р(23)= ! (22е!)=р(224)=2 4=8 ит.л. Част ! Ззегвм и каялсгяк 01=1, Пример 7. Функция х! удовлетворяет равенствам ((у+1)1=у!(у -!) О1= С! (х) = 1, или ~ ) <( ( ( )) ), т.е. функция х может быть полу- чена по схеме примитивной рекурсии из общерекурсивных функций С, и !з(Р(у1, у + 1),х, у), слодавательно, М общерекурсивна.
Опус. делим аначитичсский вид функции гр . Как и в предыдущем случщ, ( У(О)=1, ( 01=1, У(уе1)=р(у,Х(у)) Ъе1)=у!(уе1) т.е, у(ут1)=у!(у+1)=(уе1)!Я1=(уь1) т (у)=(у+1) я=у(ху,я). Вычислим теперь несколько последовательных значений Д(0) = 1, .У(!)=у'(О )= (у, )= (ОЛО))=р(О,!)=(+ ) =, У'(2)=У(1е1)=Ч(у, )=Ч(1,Л1))=р(и)=(!е!) 1=2. Д(З)= У(2+1)=р(у,х)=дг(2, Г(2))=дг(2,2)=(2+!) 2=6 ит.д.
Пример 8. Какая функция получается из ф н чг с помощью схемы примитивной рекурсии, сеян ф(х)= х, р(х,у,а)= х "г по определет'(х,О)= х, нию У(х, у+ !) = т". Итак, искомак функция !'(х, у) задана схемой примитивной рекурсии Вычислим по втой схеме последовательно нсскцчько значений данной у (х,О) = х, Г(хД)= У(хО-ь!)=гр(хО У(хО))=гр(хО,т)=х"' первую строку можно опустить.
г(х2)= у(х!т1)= йг(х 1,г(х1))= Чг(х! х*)= (х" ) = х', У(хЗ)=У(х2ь1)=Зг(х2У(х2))=О(х1,х* )=(х ) =х*""=х" и т.д. Ясно, что /(х,у)= х . Вычислим некоторые числовые значе. ния. г"(2,0)= 2,тогда У(21)=У(20+!)=гр(20 У(20))=р(202)= г" =2 =4, гйг Глаша тес!маял»с измял ((2,2)=У(2!+1)=ф(21,«(21))=зу(234)=:* =4 =16, ~(23)= у(22+1)=ф(22, у(22))=я»(2116)=Х' =16 =256. Пример 9. Какая функция получаюся из ф н йг с гюмощыо схемы примитивной рекурсии, если ф(х)=х, 9(х,у,х)=х'2 Задача решается анаиогич~ю предыдущей, распишем схему примитив«" (х,О) = х, иой рекурсии по форме ~ ( ) (, . Тогда «(х,О) = х, «(к!) = Дхб ч 1) = яг(»О, У(х 0)) = ф(хО х) = х '.
Аныюгичные вычисления дают «(х, 2) = г"(х,1ь1) = !г(х,1,«'(х,1)) = ф(х,1, х" «= хл = (х)», «(х,3)=«(х,2ь!)=зу(х1,«(»2))=9(х1,(х)» )=хс =(х)!" и т. д. О ~евндно, что «(х, у) = х Пример 10. В области натуральных чисел разность .т- у естественно считать двухместной функцией ст х и у, определенной лишь Ллл х> у, т.к. отрицательные числа ие входят в рассматриваемую область. Но примитивно рекурсивные функции должны быть всюду определены. Позтому в теории примитивно рекурсивных функций вь»есто обычной вводят усеченную разность, обозначаемую симво.юм — и (х — у, х>у, определяемую так: х — у = ~ Наприь»ер, 5 — 3 = 2, О, х<у.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
