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