В.И. Игошин - Задачи и упражнения по математической логике и теории алгоритмов - 2007 (1019105), страница 51
Текст из файла (страница 51)
Я,(хо ..., х„), если высказывание Р(х„..., х„) истинно, ~~(х,, ..., х„), если высказывание Р(х,, ..., х„) ложно. <р(х„ ..., х„ ) = Оператор условного перехода может иметь и более общую форму, когда переход носит не двузначный, а многозначный характер и определяется конечным числом преднкатов Рь ..., Р„, из которых истинен всегда один и только один предикат. 13.11. Докажите, что следующие предикаты примитивно рекурсивны: а) Ю„(х): «х делится на и»; б) Ю„„(х): «х делится на т и на и»; в) А(х, у): «х < у»; г) 1(х, у): «х = у»; д) Е(х): «хчетно»; е) Рг(х, у): «х и у взаимно просты»; ж) Я(х, у, с): «х+ у = г»; з) Р(х, у, с): «х у = „"», Р е ш е н и е. а) Этот предикат примитивно рекурсивен для любого и, так как его характеристическую функцию Хо„можно следующим образом представить в виде суперпозиции примитивно рекурсивных функций: то (х) = зй(г(п, х)).
13.12. Докажите, что если функции ~(х) и х(х) примитивно рекурсивны, то предикат «Дх) = я(х)» примитивно рекурсивен. 24б Если М, = ... = М„= Ф, то тр — функция, входящая в круг наших рассмотрений. Если те примитивно рекурсивна, то и предикат Р называется примитивно рекурсивным. Одним из часто встречающихся (особенно в теории алгоритмов) способов задания функций является их задание с помощью так называемого оператора условного перехода. Этот оператор по функциям Я(хо ..., х„), Я~(хп ..., х„) и предикату Р(х„..., х„) строит функцию 13.13.
Докажите, что если предикаты Р(х„..., х„) и Д(хо ..., х„) примитивно рекурсивны, то следующие предикаты примитивно рекурсивны: а) -зР(хь ..., х„); б) Р(хь ..., х„) л Д(хь ..., х„); в) Р(х„..., х„) >~ 0(хп ..., х„); г) Р(х„..., х„) -+ Д(хь ..., х„); д) Р(хъ> «2> «3» " х»). 13.14. Докажите, что класс примитивно рекурсивных предикатов замкнут относительно взятия ограниченных кванторов общности и существования. Точнее, докажите, что если предикат Р(х„ ..., х„, у) примитивно рекурсивен, то примитивно рекурсивны и следующие предикаты: а) (чу)(у < ~ -+ Р(х„..., х„, у)); б) (3у)(у < < я д Р(х„..., х„, у)). 13.15.
Докажите, что: а) если функции Яь Я и предикат Р примитивно рекурсивны, то и функция <р, построенная из Я, Я~, Р с помощью оператора условного перехода, примитивно рекурсивна (этот факт выражают также, говоря, что оператор условного перехода примитивно рекурсивен); б) если функции Я, ...,,4 и предикаты Р„ ..., Р» примитивно рекурсивны, то и функция ~р, построенная изб„..., 4, Р„..., Р» с помощью оператора условного перехода, примитивно рекурсивна. Решение.
а) Нетрудно понять, что с помощью характеристических функций предиката Р и его отрицания -ьР функцию >р можно выразить следующим образом: ~р(хп ..., х„) = Я,(хь ..., х„) . . х,(х„..., х„) + Я,(хь ..., х„) т„р(хп ..., х„), откуда и вытекает требуемое утверждение. 13.16. Докажите, что все функции, заданные на конечных множествах, примитивно рекурсивны. Оператор минимизации. Общерекурснвные н частично рекурсивные функции.
Говорят, что функция Дхп ..., х„) получена из функции Я(хп ..., х„, ~) с помоЩью опеРатоРа минимизаЦии (1»-опеРатора), и обозначают ~(хп ..., х„) = 1»~(я(хо ..., х„, Х) =01, если выполнено условие: ~(х„..., х„) определена и равна г тогда и только тогда, когда я(х„..., х„, 0), а(хо ..., х„, 1), ..., 8(хо ", х„ ~ — 1) определены и не равны О, а я(х„..., х„, г) = О. Оператор минимизации можно рассматривать как оператор, заданный на множестве числовых функций и принимающий значения в нем же. В этом своем качестве оператор минимизации является удобным средством для построения обратных функций.
Действительно, функция ~'-'(х) = ру(Яу) = х) («наименьший у такой, что у(у) = х») является обратной для функции Ях). (Поэтому в применении к одноместным функциям оператор минимизации иногда называют оператором обращения.) Функция называется частично рекурсивной, если она может быть построена из простейших функций О, Я, 1" с помощью конечно- 247 го числа применений суперпозиции, примитивной рекурсии и р-оператора. Если функция всюду определена и частично рекурсивна, то она называется общерехуреивной.
13.17. Рассмотрите действие оператора минимизации для получения обратных функций. К каким функциям они являются обратными? Для каких значений аргументов эти функции определены? а) а(х, у) = рх[у + е = х]; б) д(х,у) = р4у г=х]; в) Гх = ру[у~ = х]; г) 1оа, х = ру [а" = х]. Рассмотрите всюду определенные аналоги этих функций, построенные с помощью р-оператора: д) [х — у] = р4у+ е > х] = ре[у + е+ 1 > х]; е) [х/у] = р~[у~ > х] = рх[у(г+ 1) > х]; ж) [ Гх ] = ру[уз > х] = руНу + 1)з > х]; з) [1о8, х] = ру [а' > х] = ру[а"' > х]. 13.18. Докажите, что функции из предыдущей задачи а) — г) частично рекурсивны, а функции д) — з) — общерекурсивны. 13.19.
Приведите пример частично рекурсивной нигде не определенной функции. 13.20. Докажите, что всякая примитивно рекурсивная функция будет и частично рекурсивной, и общерекурсивной. 13.21. Докажите, что класс частично рекурсивных функций шире класса примитивно рекурсивных функций. 13.22. Докажите, что: а) класс частично рекурсивных функций имеет счетную мощность; б) существует частичная числовая функция, не являющаяся частично рекурсивной; в) класс общерекурсивных функций имеет счетную мощность; г) существует всюду определенная числовая функция, не являющаяся обще рекурсивной.
Указание. Для доказательства утверждений б) и г) с учетом утверждений а) и в) достаточно доказать, что класс всюду определенных числовых функций имеет мощность континуума. 13.23. Докажите, что класс общерекурсивных функций замкнуг относительно суперпозиции функций. и 14. Нормальные алгоритмы Маркова Нормальные алгоритмы Маркова являются еще одной формализацией интуитивного понимания алгоритма. Теория нормальных алгоритмов была создана в конце 40-х — начале 50-х гг. ХХ в.
советским математиком Андреем Андреевичем Марковым (1903— 1979), который называл их нормальными алгоритмами. Класс всех 248 нормально вычислимых функций, т.е. функций, вычислимых с помощью таких алгоритмов„совпадает с классом всех функций, вычислимых по Тьюрингу. Марковские подстановки. Марковская подстановка — это операция над словами в данном алфавите А (допускается и слово, не содержащее ни одной буквы, называемое пустым и обозначаемое Л). Эта операция задается с помощью упорядоченной пары слов (Р, Д) и состоит в том, что в заданном слове Я находят лераое вхождение слова Р (если таковое имеется) и, не изменяя остальных частей слова Я, заменяют в нем это вхождение словом Д. Полученное слово называется результатом применения марковской подстановки (Р, 0) к слову Я.
Если же первого вхождения слова Р в слове Я нет (и, следовательно, нет вообще ни одного вхождения Р в Я), то считается, что марковская подстановка (Р, Д) не применима к слову Я. Марковскую подстановку, задаваемую с помощью упорядоченной пары слов (Р, Д), обозначают Р -э Д. В связи с возможностью рассмотрения пустых слов возникает вопрос, что значитмарковская подстановка Л вЂ” ~ и, т.е. что значит в данное слово в подставить слово и вместо первого вхождения в и пустого слова Л? По определению полагают, что результатом указанной подстановки является слово ив. 14.1.
Пусть для слов в алфавите А = (а, Ь, с, с1) заданы следующие марковские подстановки: а) аЬ-+ Ыс; г) ас-+ Ис; ж) сЬа-+Л; к) Ь-+ а; б) Ьс -+ а; д) сЬ -+ Ы; з) с(а -+ Л; л) а -+ Ы в) Ы -+ ЬЬ; е) аЬс -+ Л; и) бас -+ асИ; Примените каждую из них к слову аЬс~ЫасЬа.
Р е ш е н и е. Для применения марковской подстановки Р -+ Д к данному слову важно обнаружить в данном слове лервое вхождение подслова Р и заменить его словом Д. В данном случае для подстановок а) — и) подслово Р входит в данное слово только один раз. Это вхождение легко заменяется на подслово 0. Например, для подстановки б) получаем результат: аа~ЫасЬа. Обратите внимание на то, что для подстановки г) первым вхождением подслова ас в данное слово служит аЬсгЫвеЬа, а не аЬсМасЬа.
Поэтому в результате получим: аЬсйЫсЬа. Подстановка з) даст аЬсйсЬа. Наконец, в подстановках к), л) каждое из первых слов входит в данное слово неоднократно, поэтому имеет смысл говорить о первом вхождении. Для этих подстановок получаем результаты алссЫасЬа и ЫЬссЫасЬа.
14.2. Каждую из марковских подстановок задачи 14.1 примените к слову ~ЫасЬаЬс. 14.3. Каждую из марковских подстановок задачи 14.1 примените к слову сЬаЬсдас. 14.4. Пусть для слов в алфавите А = (а, Ь, с) заданы следующие марковские подстановки: 249 а) Ь-+а; г) Бе — «еа; ж) Ьеа-+ Л; к) Беаб-«Л; б) е-+Ь; д) еа-+аЬ; з) еаЬ-+Л; л) а-+Ь. в) аЬ-+Ье; е) аЬе-+Л; и) аЬеа-+а; Примените каждую из них к слову аЬеаЬеаЬеаЬ максимально возможное число раз. Р е ш е н и е. а) Последовательность получающихся слов можно представить следующим образом (происходит последовательная замена в данном слове всех вхождений буквы Ь на букву а): абеаЬеабеаб» ааеаЬеаЬеаЬ» аасааеабеаб =«ааеааеааеаЬ» » ааеаасааеаа.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
