Игошин Математическая логика и теория алгоритмов (1019110), страница 84
Текст из файла (страница 84)
Рассмотрим ряд примеров примитивно рекурсивных функций. Пример 33.7. Покажем, как, исходя из простейших функций, с помощью оператора примитивной рекурсии получить следующую функцию, называемую усеченной разностью: х — у,еслих>у, х — 'у= О, если х < у. Во-первых, отметим, что функция х-1, получающаяся из функции х-у фиксированием второго аргумента, удовлетворяет следующим соотношениям: 337 0 — '1=0 = 0(х); (х+1) — '1 = х = 1~2(х,у), т.е.
получена из простейших функций 0(х) и 1~(х, у) с помощью оператора примитивной рекурсии. Во-вторых, нетрудно понять, исходя из определения усеченной разности, что эта функция удовлетворяет также равенствам: х-'0 = х = Уз(х, у); х-'(у+ 1) = (х-'у)-1 = п(х,у,х-'у) для любых х и у. Тождества показывают, что двухместная функция х — у получена с помощью оператора примитивной рекурсии из простейшей функции 1з(х, у) и функции й(х, у, с) = г —.1. Пример 33.в.
Покажем, что функция в(х, у) = х+ у может быть получена из простейших с помощью оператора примитивной рекурсии. Для функции верны следующие тождества: х+0 =х; х + (у + 1) = (х + у) + 1, которые можно записать в виде в(х, 0)=х; в(х, у+ 1) = в(х, у) + ! или в(х, 0) = фх); в(х, у+ 1) = Яв(х, у)), а это и есть схема примитивной рекурсии, основывающаяся на простейших функциях 1,' и Х Пример 33.9. Аналогично операции сложения, очевидные соотношения для операции умножения р(х, 0) = х .
0 = 0 = 0(х), р(х„у+ 1) =х у+х=р(х, у)+х=х+р(х, у) =в(х, р(х, у)) говорят о том„что функция р(х, у) = х у получена из простейшей функции 0(х) и функции в(х, у) = х+ у с помощью оператора примитивной рекурсии. Теорема 33.10. Функция, полученная суперпозицией примитивно рекурсивных функций, сама примитивно рекурсивна. До казател ьств о. В самом деле, компоненты этой функции получены из простейших функций О, 5, 1" с помощью конечного числа применений операторов суперпозиции и примитивной рекурсии.
Чтобы получить рассматриваемую функцию, нужно добавить еще одну суперпозицию. В итоге эта функция также получается из простейших функций в результате конечного числа применений операторов суперпозиции и примитивной рекурсии, т.е. является примитивно рекурсивной. П 338 С использованием этой теоремы в Задачнике доказывается примитивная рекурсивность еше ряда функций (см, задачи Х~ 13.3, 13.5, 13.6), среди которых содержатся и все булевы функции (см. задачу )ча !3.7). Примитивная рекурсивность предикатов.
Определив в самом начале Э 18 понятие предиката, мы отметили, что к этому понятию возможен и еще один подход. Предикат Р(хь ..., х„), заданный над множествами Мн ..., М„, есть функция, заданная на указанных множествах и принимающая значения в двухэлементном множестве (О, 1). В теории алгоритмов принято различать предикат Р и функцию, связанную с ним, а саму функцию называют характеристической функцией предиката Р и обозначают тр.
Таким образом, 1О, если высказывание Р(х„..., х„) — истинно, ",~р(хь...,х„) = 11, если высказывание Р(хн ..., х„) — ложно. Если М, = ... = М„= Ф, то тг — функция, входящая в круг наших рассмотрений, и имеет смысл поставить вопрос о ее примитивной рекурсивности. Определение 33.11.
Предикат Р называется примитивно рекурсивным, если его характеристическая функция ур примитивно рекурсивна. В Задачнике рассматриваются примеры примитивно рекурсивных предикатов (см. Хо 13.11 — 13.14). Отметим еше одно важное свойство, связанное с примитивной рекурсивностью функций. Мы используем его в последующих рассмотрениях. Одним из часто встречающихся, особенно в теории алгоритмов, способов задания функций является их задание с помощью так называемого оператора условного перехода.
Этот оператор по функциям 1',(хн ..., х,), Я(хп ..., х„) и предикату Р(хн ..., х„) строит функцию д: 1, (х„..., х,), если Р(х„..., х„) — истинно, ~р(хи ..., х„) = 1,(хн ...,х„),если Р(х„...,х„) — ложно. Нетрудно понять, что с помощью характеристических функций предиката Р и его отрицания — Р функцию у можно выразить следующим образом: 'Р(х~> ..., хч) = Я~(хь ...> хч) ' Хг(х!> ...> Хл) +.6(х)> " > хч) ' К-р(х! --> хп). Из этого выражения вытекает следующее утверждение.
Теорема 33. 12. Если функции1оЯ и предикат Р примитивно рекурсивны, то и фУнкцив е>, постРоеннаЯ из1о Ь Р с помощью опеРатоРа У~лонного перехода, примитивно рекурсивна. Зтот факт выразкают такзке говоря, что оператор условного перехода примитивно рекурсивен. 339 Оператор условного перехода может иметь и более общую форму, когда переход носит не двузначный, а многозначный характер и определяется конечным числом предикатов Р„..., Р„, из которых истинен всегда один и только один предикат. Ясно, что и в такой форме оператор условного перехода примитивно рекурсивен, так как и в этом случае производимую им функцию можно представить в аналогичном виде: р(хп -., х.) = Х Х, + - +Л - Х,.
Заметим, что это соотношение определяет д и в том случае, когда ни один из Р„..., Ре не истинен: в этом случае о равно нулю. Последнее замечание позволяет доказать примитивную рекурсивность функций, заданных на конечных множествах, ибо все их можно задать с помощью оператора условного перехода. Правда, при этом их придется доопределить с помощью какой-либо константы на всех остальных натуральных числах, на которых она не определена.
Например, функцию у, определенную на множестве (1, 3, 9, 17) равенствами ср(1) = 8, ср(3) = О, ср(9) = 4, ср(17) = 6, с помощью оператора условного перехода можно описать так: 8, если х =1, О, если х=3, 8, если х = 9, 6 — в остальных случаях. Таким образом, р(х) = 6 вне исходной области задания. В заключение обсуждения примитивно рекурсивных функций сделаем два важных замечания. Во-первых, все примитивно рекурсивные функции всюду определены. Это следует из того, что всюду определены простейшие функции, а операторы суперпозиции и примитивной рекурсии это свойство сохраняют. Во-вторых, строго говоря, мы имеем дело не с функциями, а с их примитивно рекурсивными описаниями.
Различие здесь точно такое же, как и различие между булевыми функциями и их представлениями в виде формул. Примитивно рекурсивные описания также разбиваются на классы эквивалентности: в один класс входят все описания, задающие одну и ту же функцию. Но задача распознавания эквивалентности примитивно рекурсивных описаний являет собой еще один пример алгоритмически неразрешимой задачи (см. также 5 36).
Вычислимость по Тьюрингу примитивно рекурсивных функций. Теперь мы готовы к тому, чтобы сделать еще один шаг на пути (в каком-то смысле аксиоматического) описания всех функций, 340 >числимых с помощью машины Тьюринга. Мы докажем, что всяая примитивно рекурсивная функция вычислима с помощью мап>ины Тьюринга. Для этого остается доказать следующую теорему.
Теорема 33.13. Функция >ь, возникающая примитивной рекурсией из правильно вычислимых на машине Тьюринга функций1 и я, сама правильно вычислима на машине Тьюринга. Доказательство. Для краткости записей будем считать, что функция >р связана с функциями У и я следующим образом: ц>(х, 0) = = »(х), >р(х, >+ 1) = Фх >Р(х, >)). Обозначим г" и 6 — машины Тьюринга, правильно вычисляющие функции Ти е соответственно. Пусть х, у — произвольные натуральные числа. Требуется сконструировать машину Тьюринга, вычисляющую значение в>(х, у). Как мы уже отмечали, для вычисления >р(х, у) предстоит вычислить у+ 1 значений >р(х, О), »>(х, 1), ..., <р(х, у — 1), ц>(х, у).
Начальная конфигурация такова: а>0!"01»0. Применим к ней следующую последовательность машин Тьюринга: Б'ВГВБ'Г. В результате получим последовательность конфигураций: Б+ в г в ь+ а>01"О!»О=ьОГа01»о=ьо!»ао!"О=ь 01»во!*ОГО=»ОГа01»01"О=ь Б' г = О!"О!»аОГО»ОГО!»а„О! о в>О. На последнем шаге, применив машину, вычисляющую функцию 3(х), к конфигурации а01-", мы получим значение 3(х), которое, согласно схеме примитивной рекурсии для >р, есть ц>(х, 0). (Промежуточным состояниям а мы намеренно не приписывали никаких индексов. Индекс с> получило лишь последнее в этой последовательности состояние.) Теперь мы можем приступить к вычислению >р(х, 1), используя в~орое соотношение схемы примитивной рекурсии: >р(х, 1) = я(х, »>(х, 0)).
Для этого применим сначала к последней конфигурации команды: а,о -» а„, >ОЛ, а„, » - а, >О. В результате получим конфигурацию: 01 "01» '>1„, >00!чы ь>0. Теперь нужно подготовить ленту машины к применению машины с», вычисляющей значение в(х, ц>(х, 0)), т.е. необходимо получить на ленте конфигурацию ЧО!"О!ч~" '>. Для этого применим к конфигурации 01"01' 'д, з 001 "ы >О последовательность машин АБ-ВБ'ВГВБ-ВБ'Б'ВБ . Получим последовательность конфигураций: л в- в 01"О!»->д„„ОО!мкь>О ОГО!»->аО! о в>ОО ОГдО!»->01ымв>» в ь" в г = О1->дОГО! ось>»О!»->ОГаО!и"'> О!»->О! <"'>йОГ г в ь- в = О! ->01ы" ь>аОГОГ= О! >ОГаО!"<" >ОГ Ор >дО!"О!'<" >ОГ.
в ь Б+ = ОГа01 >О!>х" >ОГ =ьОГОГ >а01>р(х,о)0!" = Б в Б ОГОГ- О!ы'ь>АКОГ ОГОГ- ОГдО! ы > =~ ОГОГ- дОГО)ы' >, 341 Теперь мы можем применить машину 0 и вычислить значеи р(х, П = е(х, о(х, О)): 01"01 <д 01 <" >. Применим к этой конфигурации команду: азΠ— + 4,0, заци< вающую программу. Получим конфигурацию: 01'01»'-'4„01«к л И. Начинается следующий цикл, осуществляемый команда„, идУщими после пеРвого поЯвлениЯ состоЯниЯ <1,. Этот цикл и образует конфигурацию вида О!"О!»-'д 01в<' л в конфигура< „ 01 01» <" «да01в <" " и при условии, что у > 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
