Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров (1048837), страница 37
Текст из файла (страница 37)
Существенным в операторе примитивной рекурсии является то, что независимо от числа переменных в 1 рекурсия ведется только по одной переменной у; остальные и переменных хь ..., х на момент применения схем (5,2), (5.3) зафиксированы и играют роль параметров. Функция называется примитивно-рекурсивной, если она может быть получена из константы О, функции х' и функций Р" с помощью конечного числа применений операторов суперпозиции и примитивной рекурсии. Этому определению можно придать более формальный индуктивный вид. 1, Функции О, х' и т'" для всех натуральных и, т, где т(п, являются примитивно-рекурсивными. ИО 2. Если д~ (хь ..., »„),...,д (хь ..., х„), Ь(х„..., х ) — примитивно-рекурснвные функции, то 5" (й, пь „,, и ) — примитивно-рекурсивные функции для любых натуральных и, пт.
3. Если д(хь ..„х„) и Ь(хь ..., х„д, г) — прнмитивно-рекурсивные функции, то К,(д, Ь) — примитивно-рекурсивная функция. 4. Других примитивно-рекурсивных функций.нет. Из такого индуктивного описания нетрудно извлечь процедуру, порождающую все примитивно-рекурсивные функции. Пример 5.9 (сложенне, умножение, возведение в степень). 1. Сложение ~+(х, д) =х+д примитивно-рекурснвно: ~ч (х, 0) = х = (~ (х); (х, у + 1) = ~+ (х, д) + 1 = (~„ (», д))'. Таким образом, )+(х, у) = Р~(Г, '(х), й(х, у, г)), где Й(х, д, х) е в =я+ 1. 2.
Умножение 1 (х, у) =хд прнмитнвно-рекурсивно: Рк (» О) 01 (х, д + 1) = ~„(», у) + х = ~+(», ~„(», у)). 3. Возведение в степень ~,„„(х, д) = хг примитивно-рекурсивно: ,г,„р (х, 0) = 1; 1ехр (»~ у + 1) = х » = 1х (»~ )ехр (» у)) Определим функцию х — 'д (арифметическое или урезанное вычитание) следующим образом: 1'» — д, если х > у; (О в противном случае. Пример 5.10 (вычитание).
Примитивно-рекурсивными являются следующие функции: 1) 1(х) =х — '1, определяемая схемой: 7(0) = 0-'1 = 0; Р(д+ 1) =д; , 2) ) (», у) = х -д, определяемая схемой: 1(», 0) =х; ~ (х, д + 1) = х -' (д + 1) = (х-' д)-' 1 = ~ (х, у) -' 1 1В1 (для определения функции из п. 2 использована функция из п. 1); 3) /(х, у) = ~х — у~ = (х-'у)+(у-'х); )'О, если х = 0; (1, если х аО; ее схема имеет вид: за (О) = О; зд(х+ 1) =1; 5) ппп(х, у) =ха (х-'у); 6) шах (х „у) = у + (х — ' у), С помощью функции зц (сигнум) из примера 5.10,г и ее отрицания зн(х) =1 — 'зн х построим примитивно-рекурсивное описание функций, связанных с делением.
Пример 5Л1 (деление). а. Функция «(х, у) — остаток от деления у на х: «(х„О) =- 0; «(х, у + 1) =. («(х, у) + 1) зп () х — («(х, у) + 1) (). Смысл второй строки определения в следующем: если у+1 не делится на х, то зд(~х — '(«(х, у)+1)1)=1 и «(х, у+1) =«(х, у)+1; если же у+1 делится на х, то «(х, у+ +1) =ад(! х — («(х, у) + 1) 1) =О. б. Функция д(х, у) =(у/х) — частное от деления у на х, т.е.
целая часть дроби у/х: д (х, 0) = 0; д (х, у + 1) =- о (х, у) + зн () х — (« (х, у) + 1) ~). Второе слагаемое, как и в случае «(х, у), зависит от делимости у+1 на х. Если у+1 делится на х, то д(х, у+1) на единицу больше, чем д(х, у); если нет, то д(х, у+1)= д(х, у). В рекурсивных описаниях функций примера 5.11 отчет лино видны логические действия: проверка условия (делимости у+1 на х) и выбор дальнейшего хода вычислений в зависимости от истинности условия. Займемся теперь более подробным выяснением того, какие возможности для логических операций имеются в рамках примитивно-рекурсивных функций. Из функций примеров 5.10,б„д,е легко получается при- митивная рекурсивность «арифметизованных> логических функций, т.
е. числовых функций, которые на множестве (О, 1) ведут себя как логические функции. Действительно, если х, уев(0, 1)„то х=1 — 'х. ! х ~/ у = шах (х, у); (5.4) хну = ппп(х, у). Из функциональной полноты (см. в З.З) этого множества функций и того, что суперпозиция является примитивно- рекурсивным оператором (см. далее), следует примитивная рекурсивность всех логических функций. Отношение Я(хь ..., х,) называется примитивно-рекурсивным, если примитивно-рекурсивна его характеристичесная функция та: > 11, если )с(х„ ..., х„) выполняется; 10 в противном случае. Ввиду взаимно однозначного соответствия между отношениями и предикатами (см.
$ 3.4) т«будет характеристической функцией и для соответствующего предиката. Напомним, что сам предикат принимает логические значения И и Л, с которыми нельзя производить арифметических действий, даже когда эти значения изображаются числами 0 и 1 (см. $3.1). Поэтому следует проводить различие между предикатамн и их характеристическими функциями. В алгоритмических языках типа АЛГОЛ предикат будет принимать значения 1гпе и (а!зе, а его характеристическая функция — значения 0 н 1. Предикат называется примитивно-рекурсивным, если его характеристическая функция примитивно-рекурсивна.
В силу соотношений (5.4), если предикаты Р,,, Р> примитивно-рекурсивны, то и любой предикат, полученный из них с помощью логических операций, примнтивно-рекурсивен. Пример 5,12 (предикаты и отношения). а. Предикат Рп' !х) «х делится на п» примитивно-рекурсивен для любого п: )!р«(х) = за(г(п, х)). б. Предикат РЫ„, (х) «х делится на т и на и» при митивно-рекурсивен для любых т и и, так как Р л(х)» =Р (х)йР,(х). д,(хм ..., х„), если Р(х„..., х„) истинно; и, (х„..., х„), если Р (х..., х„) ложно. ~(хм ..., х„) = (5.5) Теорема 5.3 утверждает, что В вычислим по Тьюрингу.
Примитивная рекурснвность В видна из следующего соот- ношения, эквивалентного (5.5): 1. (хп ..., х„) = д, (х„..., х„) 1(р (хп ..., х„) + + Пз (х„..., х ) 11Р (х,..., х ). Обобщение оператора В на случай многозначного пере- хода по преднкатам Р„..., Р„из которых истинен всегда один и только одни предикат: ((хь ..., х„) =В(йь -, йь Рь- ..., Рь), также примитивно-рекурсивно, поскольку 1 (х„-., х„) = а, Х,, + -. + а, Х, (отметим, что это соотношение определяет В н в том случае, когда ни один нз Рь, Р» не истинен: В при этом равно нулю). С помощью оператора В удобно задавать функции, оп- 184 в. Отношение х~)хз примитивно-рекурсивно: (х„х,) = зд (х, — ' х,). г, Если 1(х) и д(х) примитивно-рекурсивны, то предикат «((х) =д(х)» примитивно-рекурсивен, так как его функция т имеет вид: 11(х) = зп()((х) — д(х))).
Примитивно-рекурсивные операторы. Оператор называется примитивно-рекурсивным (сокращенно ПР-оператором), если он сохраняет примитивную рекурсивность функций, т. е. если результат его применения к примитивио-рекурсивным функциям дает снова примитивно-рекурсивную функцию. Операторы 5„"1 и Я являются ПР-операторами по определению. Рассмотрим теперь другие ПР-операторы. Их использование позволяет существенно сократить примитивно-рекурсивные описания функций. В й 5.2 мы встречались с оператором условного перехода (обозначим его здесь В), который по функциям п1(хь ... ..., х„), д,(хь ..., х„) и предикату Р(хь ..., х„) строит функцию ((хь ..., х.) =В (дь дм Р): ределенные на конечных множествах.
Правда, В, как и любой другой ПР-оператор, всегда определяет функцию на всем натуральном ряде, т. е. производит доопределение функции вне области задания. Например, функцию 1, определенную на множестве !, 2, 6, 17 равенствами 1(1) =5, 1(2) =1, !(6) =О, !(17) =8, с помощью оператора В можно описать так: 5, если хпп 1; 1, если х= 2; 1(х) = О, если х=б; 8 в остальных случаях. Такое описание полагает 7(х)=8 вне исходной области задания. ПУсть 7(хь ..., хпп У) — фУнкциЯ от (и+ 1)-й пеРеменной.
Хорошо известные операции суммирования ~~.', и перемноу<» жения П по переменной у с пределом г — это операторы, у<» которые.из функции )(хь ..., х„у) порождают новые функции д(хь...,хп, г)=,»»!(хь...,хп, У) и. п(хь- хп г)— у<» = П ((хь ..., х„, у), Покажем их примитивную рекурсиву<» ность: д(хи ..., х„, 0) = 0 (по определению); Й'(л'т - .
хп, г+ 1) = Д(х» -., хп, г) +) (хи „., хп, г); 'и (х,, ..., х„, 0) = 1; й(х,, ..., х„, г + 1) =- й (х„..., х„, г) ! (х,, х„г). Таким образом, д и й могут быть определены по схеме примитивной рекурсии с использованием сложения и умножения, примитивная рекурсивность которых доказана, а также функции 1. Следовательно, у и й примитнвно-рекурсивны, если ! примитивно-рекурсивна. С помощью ~~» и П нетрудно показать, что операторы у<» у<» »» 'у', н П (т. е. суммирование и умножение от й до г) — таку у у=у же ПР-операторы.
Рассмотрим теперь оператор, играющий важную роль в теории рекурсивных функций, — ограниченный оператор наименьшего числа (1у-оператор), называемый также огра- 185 ни«енным оператором минимизации, который применяется к предикатам и определяется так: наименьшему у г, такому, что Р(хь ..., х„, у) истинно, если такой у существует; г в противном случае. ру„„, Р(х„..., х„, у) = 186 Из предиката Р(хь ..., х„, у) с помощью оператора ру„», получается функция Г(хь ..., х„, г), Второй случай в определении 1г добавлен для того, чтобы Г была всюду определена, Пример 5.13.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
