Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров (1048837), страница 38
Текст из файла (страница 38)
Пусть Р(х„хь у) =Рг(„„„, .(у) (пример 5.12,6). Тогда м„»,Р(хь хь у) равен наименьшему общему кратному (НОК) х1 и хь если г- НОК, и равен г, если г( (НОК. Ограниченный и-оператор примитивно-рекурсивен: г а ру„, Р (х„..., „, у) = '5', П (1 — Х„( „-, „,,1)) е~п г=з Ограничение з в ограниченном и-операторе дает гарантию окончания вычислений, поскольку оно оценивает сверху число вычислений предиката Р, Возможность оценить сверху количество вычислений является существенной особенностью примитивно-рекурсивных функций, Уже отмечалось 1см. (5.2), (5.3) и далее1, что если ((хь ..., х„, й) = =й„(д, Ь), то для вычисления 1(хь ..., х, й) понадобится й+1 вычислений по схеме (5.2): одно вычисление.у и й вычислений Ь, Правда, каждое из них может, в свою очередь, состоять из некоторого количества вычислений функций, входящих в определение д и Ь; но в силу конечности общего числа операторов 5" и Я,ь использованных для построения 1 из базисных функций О, х' и У", для любого й можно оценить количество элементарных действий (т.
е. вычислений базисных функций), необходимых для вычисления )(хь ..., х„й). В дальнейшем будет показано, что неограниченный и-оператор не является примитивно-рекурсивным. и-оператор (как ограниченный, так и неограниченный) является удобным средством для построения обратных функций. Действительно, функция д(х) =1гу(((у) х) («наименьший у, такой, что Г(у) =х»)'является обратной к функции 1(х).
Поэтому в применении к одноместным функциям [з-оператор иногда называют оператором обращения. Пример 5.14. а. С помощью ограниченного [з-оператора определим деление, точнее функцию [х/х1 (частное от деления х на х — см, пример 5,1!,б), как функцию, обратную ' умножению: [г/х) = [зу„, (х (у + 1) > г). б. Целая часть 3~ х — функция ЦГх) — примитивно-рекурсивная, так как [1'х1 = рр. ° ((р+ 1)' > х). в. [1одах)=[ау„„(як+')х), следовательно, целая часть логарифма по любому целому основанию я примитивно-рекурсивна. Еще один ПР-оператор — это оператор совместной или одновременной рекурсии, точнее, целое семейство операторов (!саа).
С помощью гс,а строится рекурсивное описание .сразу нескольких функций ~ь ..., [ь от (и + 1)-й переменной, причем значение каждой функции у+1 зависит от значения всех функций в точке у: [, (х„..., х„, О) = д, (х„..., х„); (а(хз, ..., х„, О) =- д (х,..., х„); )".,(х„..., х„, у+ 1) = Ь,(х,, „, х„, у, !т(хм ..., х„, у), ..., !".ь(хм ... х„, у)); [,(х„..., х„, у+ 1) =- й„(х„..., х„, у, ), (х„..., х„, у), ..., [а(х„..., х„, у)).
По существу совместная рекурсия дает рекурсивное описание функции-вектора ((ь ..., !а). Для того чтобы доказать примитивную рекурсивность совместной рекурсии, нужно закодировать этот вектор числом, причем так, чтобы существовала однозначная и примитивно-рекурсивная расшифровка этого кода (т. е. извлечение нужного разряда вектора). В качестве такого кода можно предложить число ' !!елая часть от деления — функция, «не совсем обратная» умножеинкч точнее, обратная ему только в тек точках, где в делится нацело на л. Поцтому в ее описании используется пе преднкат равенства (как в определении обратной функции), а преднкат ), !87 чр(хь, хз, у) =2ггсхм-"" 'э! .Згз.бгз.....Р1ь! т -"а э! где р, з-е простое число (2 считается 0-м простым числом), Продемонстрируем эту идею на примере оператора )тм.
Пусть 1!(х, У), 1з(х, У) заданы совместной РекУРсией: )'т(х, 0) = йтт(х); ~з(х, 0) =да(х); ~т(х, у+ 1) = й,(х, у, р,(х, у), 1,(х, у)); 1з(х, у+ 1) = 1!з(х, у, !'т(х, у), 1з(х, у)). Определим кодируюшую функцию Р: Р (х 0) — 2апх! .Запю ° Р(х -'- 1' = 2 и"'юйоьмлнюю~ Зч!ююйпююлн"'эп х, у+ Тогда 1! ( х, у) =!ха, „<„„! (Р4, +т(Р(х, у))), т. е, равна показателю при 2 в разложении Р(х, р) на простые множители; (з(х, у) =)ьг, гх ю(рдза+т(Р(х, у))), т.е. равна показателю при 3 в разложении Р(х, у) на простые множители. ,(Определение предиката Ро см.
в примере 5.12,а). Следует иметь в виду, что такая кодировка вовсе не предлагается в качестве метода рекурсивного вычисления функций-векторов. Наоборот, предлагается прямой и более простой метод совместной рекурсии, а кодировка является лишь доказательством того, что этот метод относится к числу примитивно-рекурсивных средств вычисления.
Можно предложить полезную схемную интерпретацию примитивной рекурсии вообще и совместной рекурсии в частности. На рис. 5.12, а изображена схема, состоящая нз устройства, вычисляющего за один такт функцию Ь от двух переменных, и элемента задержки иа один такт; по каналам схемы могут передаваться натуральные числа.
Время т будем считать дискретным: 1=0, 1, 2... Схема нмеет один вход х и выход й Однако выход 1 зависит не только от значения х, но и от мо. мента й в который он рассматривается, т.е. представляет собой некоторую функцию 1(х, т). Рассмотрим эту зависимость подробнее. Будем считать значение х иа все время рассмотрения, начиная с 1=0, произвольным, но фиксированным, В начальный момент 1=0 значение второго входа Ь является константой с, зависящей от начального состояния схемы: 1(х, О) =Ь(х, с) =я(х). В момент 1= 1 1(х, 1) =Ь(х, )'(х, О)); в общем случае 1(х, 1+1)=й(х, 1(х, т)). Таким образом, схема рис. 8.12,а реализует примитивную рекурсию по переменной д т.е. по времени.
Нетрудно убедиться, например, что если й выполняет умножение, а с=1, то 1(х, !) =х'+'. Прн аналогичной интерпретации (с иачальнымн 188 константами сь с,) схема на рис. 5.12,б реализует схему совместной ренурсии, причем рекурсия танже ведется по времени, общему для устройств Ь, и йт. Доказательство того, что совместная рекурсия — это Пр-оператор, в терминах таких схем означает, что перекрестные обратные связи иа рис, 5.12, б можно замевить простыни контурами обрат- Рис.
5.12 ной связи типа приведенных на рис. 5.12,а, Структура схемы при этом станет проще, однако понадобятся дополнительные вычислительные устройства, формирователь числового кода вентора Ць )з), передаваемого но одному каналу, и декодирующее устройство с двумя выходами й и )з, Описанная схемная интерпретация примитивно-ренурсивиых функций проходит при одном предположении, что за один такт любой напал схемы способен передать, а вычислительное устройство — воспринять и переработать любое, сколь угодао большое натуральное число Такое предположение физически нереализуемо, поэтому теория таких схем не будет представлять самостоятельного интереса.
Если же наложить ограничения ца возможности ианалов и элементов схем, то это приведет к теории конечных автоматов и схем из автоматов, о которой будет идти речь в гл. 8. Подведем некоторые итоги. Из простейших функций = константы О, функции к+1 и функций тождества 1" — с помощью операторов суперпозицнн и примитивной рекурсии было получено огромное разнообразие функций, включа1ощих основные функции арифметики, алгебры и анализа (с поправкой на целочисленность). Тем самым выяснено, что вти функции имеют примитивно-рекурсивное описание, которое однозначно определяет процедуру их вычисления; следовательно, их естественно отнести к классу вычисли= 189 Продолжим зту последовательиостгч положив по определению фв+ (а, О) =1; Фаз.г(а, !) =а; Фа+д(а, У+1) ф„= (а„Фа+а (а, У)).
(6. 6) 190 мых функций. Попутно сделаем два замечания. Во-первых, все примитивно-рекурсивные функции всюду определены. Это следует из того, что простейшие функции всюду определены, а операторы 5" и )г, это свойство сохраняют. Вовторых, строго говоря, мы имеем дело не с функциями, а с их примитивно-рекурсивными описаниями. Различие здесь имеет тот же смысл, что и отмечавшееся неоднократно в гл. 3 различие между функциями и их представлениями в виде формул. Примитивно-рекурсивные описания также можно разбить на классы эквивалентности, отнеся в один класс все описания, задающие одну и ту же функцию. Однако задача распознавания эквивалентности примитивно-рекурсивных описаний, как будет показано, алгоритмически неразрешима.
Функции Аккермана. Пора уже задать вопрос: все ли функции являются примитивно-рекурсивными? Простые теоретико-множественные соображения показывают, что нет, В гл. 1 (пример 1,8,г) было показано, что множество всех функций типа Лг-~.дг (т.е. одноместных целочисленных функций) несчетно, тем более зто нерио для функций типа Л'"-~-Лг. Каждая примитивно-рекурсивная функция имеет конечное опнт саине, т. е. задается конечным словом в некотором (фиксированном для всех функций) алфавите. Множество всех конечных слов счетно, позтому примитивно-рекурсивные функции образуют не более чем счетное подмножество несчетного множества функций типа Ль'-ьЛ!. В действительности здесь рассматривается более узкий вопрос; все ли вычислимые функции можно описать как примитивно-рекурсивные? Чтобы показать, что ответ на этот вопрос также является отрицательным, построим пример вычислимой функции, не являющейся прнмитивиорекурсивной.
Идея примера в том, чтобы, построив последовательность функций, каждая из которых растет существенно быстрее предыдущей, сконструировать с ее помощью функцию, которая растет быстрее любой примитивно-рекурсивной функции. Начнем с построения последовательности функций Фм фь фь Положим Фз(а, у)-а+р; Ф,(а, у) аги Фт(а, у) =ат. эти 'функции связаны между собой следующими рекурсивными соотношениями: Ф,(а, у + 1) = а + ау = <рз (аг, Фг (а, р)); ~рг (а, 1) = а! фз (а, у + 1) = аа" = фг(а, Ф (а, у)); гр (а, 1) = а.
Эта схема имеет вид примитивной ренурсии, следовательно, все функции ф примитивно-рекурсианые. Растут они крайне быстро; например, аз(а, 1) =а; фз(а, 2) =<уз(а, а) =а'1 <рз(а, 3) =а«~; ...; аз(а, й) =а" ' )* г". Зафиксируем теперь значение а.а=-2. Получим последовательность одноместных функций; ф,(2,у), ф,(2, у)... Определим теперь функцию В(х, у), которая перечисляет эту последовательность: В(х, у)=ф,(2, у), т.е. В(0, у) ~р,(2, у)=2+у; В(1, у)=ф,(2, у) 2у и т.д., а танже диагональную функцию А(х) =В(х, х).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
