Математическая логика. Шапорев С.Д (1019113), страница 36
Текст из файла (страница 36)
3. Введем функцию, определяющую чиапо делителей ггатурщзьньгх чишп пб(х)= 2,'б!т(х,!). Рассмотрим пример. Пусть х= 5. Тогда, очевидно, ~=о пб(5) = 2. Проверим это, подробно распиаав выражение дяя пб(5): Тлена б. Теория алгарвпяов По теорема 5.3 о мажорируемой неявной функции следует, что !чЯ примитивно рекурсивна. Вместе с июо примитивно рекурсивной валящая и ! г12 функция д(х)=х — ргх1 .
Аналогичным ооразом доказыввется примн- тинная рекурсивность и м~югих других арифметических функций. рассмотрим одноместные примитивно рекурсивные функции и следующие операции нвд ними 1. Двухместная огмрацня слолгсния одноместных функций (/ г б )(х) = 1'(х) ь б (х). 2. Двухместная операция комщииции одноместных функций (Т е б ~(х) = ! (б (х)) 3. Одноместная операции нюрнроаания одноместной функции, опрсделяе- ,Т(О) = О, маясясдующимобразом... „или 1 =г б. (.Т(л ч !) = 3Ил)) В последнем пункте функция / возникает операцией игерирования функции б.
Тварюга 5.4 1гггеорема Р Робшюояа 1. Все одпоме нные ирнмитивмо рс. курсмвиые функции н только онн могут быть получены нз функций л(х)=хч1 и б(х)=х — (згх~ «онечпым числом операций сложении, композиции и итерировавии фупкцпй. При рассмотрении общерекурспвных функций, класс когорых шире класса примитивно рекурсивных функций, прививка~от специальные виды рекурсии, например, рекурсии второй ступени для двухместных функций.
Пример 1. Доказагь, что функаии щах(х,у) и щгп(х,у) примитивно рскурсивиы, Вспомним несколько вспомогательных функций; (1 хнО, . (х — у х>у, — (! х=О, збп(х) = ~ ' , х — 1 = , збп(х) = Рас(О, х = 0 ~ О, х < у (О, х > О. (х, т>у, смотрим первую из задвнныя функций щах(х, у) = Тогда (у, х<у лаве б. Геадвя а яо вп ав 2зг б) ф(х!,хз,...,хл !)= 1(х!,хилз...,лв !) — отождествление аргументов. !.4.2. Доказать, что следующп» функциа примитивно рекурсивны а) 1(х)=хогг, б) 1'(х)=гг; в) 1"(х,у)= х-ь у. !.4,3.
Доказать примитивную рекурсивиосщ следующих функций. а) !х — у); б) т(х) — число лелпгелсй числа х, гле т(0)=0; в) я(х) — число простых чисел, не прсвссколящих .т, г) 11г(х) — число простыв делителей гисяа .т, где 11г(0)= 0; д) р(т) — х.е простое число р,, причем р(0)=2, р(!)= 3, р(2)=5,...; е! !хмг21; «г! Сг (С) = ! цри у дх) з44 Доказать, гго из О(х) и !,",,(хпхз....,.г„) с помощью суперпозицнй и схем примитивной рекурсии нельзя получить функции х+! и 2х. (х+у) +Зх+ у з.4.5. Доказан, что функция с(т,у)= !кантороаская' ну- 2 мерующая функция) осуществлает взаимно однозначное сгкнаегствис мсягду ДГ и М (нумерует пары иазуралывих чисел).
Пусть 1(х) и г(х) таковы, что с(1(х)г(х))=х. Доказан, что Дя) н г(л) примитивно рскурснены и !(с(х, у)) = х, г(с(х, у)) = у 5.4.6. Доказать, что функция, перечисляющая по порядку числ» йгибонвччи 1(0)=0, 1(!)=1, ) примитивно рекурсивна. Г ое~ Кьщсвцяав-!С!аз — г Я а м«в Л ва М Г ыч Н ° ~ 0~за-!Зас! — в~ асма мог в Чаем 1 Магемапмескаяпсгик 5.42. Доказать, что следующие функции частично рекурсивны; а) нигде не определенна» функция ю, т. е, функция ю с пустой областью опредмен ия; б) т (х,у)= х — у, если хку, не определена в о стал ыгых случаях; в) 1 (х, у) = М еслн Л~=х, не определена в остальных случаяк. 548.
Доказать, что функция 1 (х„хг,...,х„,х„м), возникаю~язва из функций ф(хыхт,...,ха) и йг(хилз,...,х„,х„и,х„„) с помощью оператора примитивной рекурсии, может быть получена с помощью специальной ре- Д(х,б)= О, курени вида . . . , „ и супсрпозиции из функций (р'(т ~+~)=~(~(~ у)) гр(хыхз,.„,х„), 9(х„хм...,х„х„ч,х„„), 0(х), ь(х), 1„"'(хохм...,х„) и с(х, у), г(х), 1(х) из задачи 5.4.5. 5.4.9. Доказать: а) г~1+Ц=вйп(х); б) 1~хт1т~ — Щф2х — 1; в) (х + 1+ (чйх е 1~ ~ = х + х, где 1 (х) = гй (х) — операция итери рования функций. 5А,10. Показать, что следующие функции могут быть получены нз функций 1з й(х)=х+1 и 9(х)=х — (Чх1 с помощью операций подстановки, итерации и сложени» двух функций: а) вйо(х); б) зйп(х); в) 1„(х„х,...,х„); г) ахчбуч-с; д)х.
улав а. Тео ля ми рипеов 999 б.б. Словарные множества и функции Важнейшие классы алгоритмов можно описать в терминах апории слов е иекозором алфавите у!ак узко отмечалось, произвовыыя ьонечн я совокупносп букв называогсн гмфаашвом. Пссяедоватеяьность из нескольких буке называетсясгоеоч например, если алфавиз сосюит из букв А, В,С, то последовательности А ВАА, СА, СС, АСВАВ будут словами в этом алфавите Длиной слово называется число входящих в него букв.
Пусть символы а и В обозначают слова, записанные в алфавите, не содержащем самих символов а и (!. Тогда через пб обозначвсюя слово, получающееся, если сначала выписать слово а, а затем приписан, к нему слово (1. Слово пб называется комвозииией !иногда лроизеедеиюпг! слов и и б. Операция композиции слов, очевидно, ассоциативна, но не коммугативна. Слово и нате~ввозов лодсеоеом слова (1, если (! можно представить в виде р = уаб, где у,б — подходящие !возьзозюю пустые) слова. Пусть А = (,а,аз,...,гг ) — какой-нибудь конечный набор символов Обозначим через а совокупность всех слов в алфавите Л, вкяючая пустое слово Л Всевозможные полчножсства совокупности и, в том числе пустые, будут называться слоеоримзю миоэсесюеи, л в алфавите Л Для нумерации словарных множеств вводится понятие олфоеиив ыт иоиерое следующим образом !!омер пустого слова Л полагается равным нулю.
Далее в каком-нибуль порялке числами 1,2,3,...р нумерунггс» символы ачфавита Пусть а, — символ с номером г. Тогда номером сюаа а =а, ..а а,, наг зываегся число с(а)= го е!! Рт!з р е- тг, 'р . рассмотрим предыдущий пример Из данного определения номера следует. что каждое слово совокупности а„будет иметь единственный и отличный от других алфавитный номер. Пусть и =(А,В,Сф а слава а=АСВАВ. Сз'3 ' з1 з тогда с(а) = 2 Зо ь 1 3' + 2 3з е 3 Зз ь 1 3 . По своему составу и методу получения зто обычное число в троичной системе счисления. Множество алов М в алфавите А называется нри.
итивио рекурсивным, если соответственно примитивно рекурсивма совокупность алфавитных номеров всех слов из М. Чащь ! Маммаимесмм ящике Говорят, что в алфавите А задана и-местная словарная функция Г, если некоторыьг и -квм а„а„...,п„слов из па поставлены в соответствие однозначна огзределеиные слова Г(а„а,...,а„) в А . Числовая и-местная функция Г называется функцией, представляющей словарную функцию Г в нумерации К, если Г(Кх,К~,.„,КЗ,)=К/(З,х„...х„) для всех нвтуральнык х,х„...,х„и, следовательно, Г(пппз,...,ая)= К1(спмсаз,...,са„) или У(Ж ~ - х,)=с(Г(КЗ,Кт„...,Кх )), где К вЂ” первоиачавьивя нумера.
ция алфавитных символов. Здесь с(а) — алфавитный номер слова а, Кх,— слово, имеющее номер х, в нуиерации К, Рассмотрим предыдущий пример. Пусть и, =)А ВС~ и Г (а)=ц.а~ = =ц А. Тогла /!(х)=с(Р~(Кх))=с(Кх ° А), т. к. по определению представляющей функции изменяется только аргумент, а не прочие символы, входящие веесостав.
с(Р~(а))=с(Кх ° А)=с(п А)=1+ р.с(п).Действительно, а=АСВАВ,а А=АСВАВ А, 1 3 3 ! з зза~ з с(ц А)=1 р +2 Г!+1 р +2 р +3 ГЯ ч- ч1 р =1я-р(2-ь! р+2 р +3 р +1 р")=1+с(о) Я=3 — основание системы счисления при нумерации символов аифавита. Тогда т,(х)=! + рх= 1-ь Зх — числовая функция, представляющая словарную фуикциго Р~(п)=а А. Если же Гз(ц)=а, и= А п,то 2з(х)=с(Г (Кх))=с(А Кт), с(Гз(п))=с(а, п)=с(А а)= с(А АСВАВ)=с(а)+1 ргм =с(п)+ ! рз.
Тогда г (х) = х+ 3 — числоаа» функци». представляющая словарную 5 функцию Гз(ц)= А а. Итак, свойство словарных функций быть рекурсивными связано с рекурсивносгью совокупности влфавитнык номеров всех слов. Ясно, и определение словарной функции зто подтверждает, что свойство быть рекурсивным множеством слов не зависит ни от нумерации К символов алфавита, ни от того, в каком алфавите зто множество рассматривается.
По аналогии с основными вычислимыми операциями над числовыми функциями можно определить операции подстановки 1суперпозиции), рекурсии и минимизации, производимме над словарными функциячн. При помощи 24! Глана 5 Теоркл ало ркгмсв зтих "словарных операторов" легко и без каких-либо вычисяеннй показывается примитивна» рекурсивность всех наиболее употр«бнтельных словарных функций. Например, так же вводятся основные злеиентариые операторы сдвига, аннулирования и проектирования Пусть алфавит А состоит из букв аоа, ,а„. Словарные функции блО и 1,",, (гл = 1,2...,г = 1,2,..., р, гл < л), определенные в авфавнте Л равенствами 5 (п)=п а„О(п)=Л, Г„,(пипл,...,а„)=пи, называютсл яростейнгимн.
Рассмотрим теперь какие-нибудь частичныс словарные функции О и НмН„...,Н соответственно от и и и ч 2 переменньщ, заданных в алфавите А, состоящею из букв а„аз,,..,аг Результатом операции словарной примитивной рекурсии над функциями О, НмН„...,Нл называется 1л . 1)-местная словарная функция Г, которая длл любых слов аыаз,...,ал,(5 в алфавите Л удовлетворяет равенствам г(апаз,...,п„,Л)=О(пыаз,...,п„) Е(ппаз,...,пя,0.а,)= Н,(ппаз,...,п„,(1ыц(аппз,,п„,б)) Р(пыла,...,а„,Р аз)= Нз(а,,аг,пч,б, Р(пиал,,а„,Я) 15 5.П л(аг,аз,,а„,)3 ср)= Н„(лиаз,...,а„,~,г(пипл,...,п„,р)).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
