Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
Пусть («і, ..а„+і) — произвольный набор чисел из Полагаем
/(«», аП) 0) = ф(аі, ..., а„).
Если ф на этом наборе пе определена, то считаем, что не определена Цаи ..аи, 0), а также /(оц, ..., ап, у) при любом у. В противном случае полагаем
/(ос15 а„, 1) ~ г|?(а,, ..а„, 0, а„, 0))'.
Если правая часть не определена, то считаем, что /(оц, ..., ап, І), а также /(сс^ ..., ап, у) не определены при любом у, у > 1 ит. д.
Через конечное число шагов мы либо определим /(аь ..., ап, ай+1), либо установим, что на этом наборе } не определена.
Из данного рассуждения видно, что если /(аі, . .* ап, ай+1) не определена, то при р > ап+, не определена будет также и /(ам ..., ап, $). Про функцию / будем говорить, что она получена из функций ф и ф при помощи операции примитивнохі рекурсии.
Пр имер 7. Покажем, что функция і(хи хг) = Хі + + хг может быть получена через примитивную рекурсию из простейших вычислимых функций.
•) Некоторые из переменных у ф и ф могут отсутствовать.
10*
148 Ч. I. ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ
В самом деле,
Замечание. Операция Пр позволяет для каждой
функции ф(#1, хп) вводить несущественные переменные, а именно:
/(^, Хп, 0) = ф(хь *„),
1{хи хп> у+ 1) = ф(а:ь яп)'.
Операция минимизации определяется следующим образом. Пусть ф(дгь хп~и ?„) — произвольная функция из Я«0* Построим функцию }[хи ..., аг„-1, хп) через оператор минимизации
/(^1, . .., 3?п) р1/(ф{Д!,1, .. Хп~ 1, I/) хп),
что означает, что для произвольного набора («1, ..ап) составляется уравнение
а) Если существует у из являющееся решением
этого уравнения, то берем минимальное из решений и обозначим его через р„. Если значения
б) В противном случае, т. е. в случае, когда либо уравнение не имеет решений, либо хотя бы одно из значений ф(а15 а*-!, 0), ..., ф(аь ..., ос„_ь Ц»“1) не
определено, функция /(с^, а„) также не определена.
Про функцию / говорят, что она получена из функции ф при помощи операции минимизации.
Пример 8. Пусть ф> (я) = х + 1. Определим через операцию р функцию f(x):
1{хх, 0) =/! ю,
f(x 1, У + 1 ) = S(f{x1, у)).
Ф (сц, ? • *, Ctn—I, у) ct„.
Ф(аь ..., cin-i, 0)....................ф(«1, ап_!, ри-1)
также определены, то полагаем
/((%!, • » ?, СС.п—I, Кп)=
/(.г) = р.и{ф(у) = х).
Ясно, что
не определена при ж = 0, х — 1 при х > 0,
х — 1
ГЛ. 4. ВЫЧИСЛИМЫЕ ФУНКЦИИ 149
Данные операции позволяют построить три следующие функциональные системы,
I. Множество РчР всех функций, которые можно получить из системы функций (0, <S(x), хф), 1< < т ^ п, п~1, 2, ,.при помощи операций С, Пр и ц, называемое классом частично-рекурсивных функций,
II. Класс рекурсивных функций^ т. е. множество Рр всех всюду определенных функций из Рчр.
III. Класс примитивно-рекурсивных функций, т. е. множество Рпр всех функций, которые можно получить ИЗ системы {О, S (,т), , #п),1 ^ гп ^ п, п — 1, 2, ...} при помощи операций С и Пр.
Очевидно, что
Pav ^pl0‘
Предыдущий пример показывает, что класс Рчр существенно шире, чем класс Рр. Можно показать, что и класс Рр существенно шире, чем класс Рцр,
Рассмотрим примеры примитивно-рекурсивных функций. Возьмем функции
Sg(л:), Sg(a:), [x/2l 2\ х,-х2 и xt ? х2,
где
Ю при х = 0, __ [1 при х = О,
Sg (х) при х ф 0, ^ ^ {О при х Ф 0Л
О прп хх < x2i
Х1 Х2 ПРП Х1 ^ Ха,
Функции [х/2], 2х и хх • хг имеют обычный смысл: целая часть х/2, показательная функция и умножение. Их примитивная рекурсивность вытекает из следующих соотношений:
Sg(0) = 0, f si(0)=lt
Sg(x + l) = l, lSg{x + 1) = 0,
X! ? 0 = 0, f 2° = 1,
Xt (хг + 1) = х%х2 4- xlt \ 2x+i = 2-2*.
Здесь копстанта 1 получается суперпозицией 0 и S(x), xt + хг примитивно-рекурсивна, а 2х получается из пее
150 Ч. I. ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ
суперпозицией;
0 — 1 = 0, I Ху — 0 = хи \х+ 1) — 1 =Х, 1^! -(^2+ 1) = (^1 — Я*)“ 1,
И-о,
Ж~Чт1-
Здесь х — 1 — вспомогательная функция.
Данные примитивио-ре курсивные функции позволяют строить многие другие примитивно-рекурсивные функции. Например, /(#1, ж„), равная нулю за исключением ко-
нечного числа точек, в которых ее значения принадлежат Е к0,—примитивно-рекурсивна,
В самом деле, пусть Цхи ...,хп) =-
Р* при (лгг, ..., ?„) = (а*, ,. ,д а«) (? = 1, .. .д $)
0 в ос-тальпых точках
и р*е Е*о(1 = 1, 5).
Рассмотрим функций М#), где
... [1 при I =г, . •
[0 при хфь.
Очевидно,
-?- (* — 1)) Sg(;r-^г) при г Ф 0 и ;0(ж) = 8д(а:).
Положим
[1 при («!, . . Хп) = (?!, . . 1*и)(
10 в остальных случаях.
7н,...лл (я"п =
Мы имеем
ГЛ. 4. ВЫЧИСЛИМЫЕ ФУНКЦИИ
Ш
Последнее является аналогом разложения в дизъюнктивную нормальную форму.
В заключение заметим, что операции С и Пр, примененные к всюду определенным функциям, дают всюду определенные функции. Отсюда вытекает, что класс Рр замкнут относительно операций С и Пр.
Далее мы займемся изучением связи классов Рьыч и Рчр. Основная цель состоит в установлении тождественности этих классов,
§ 6, Вычислимые функции и операции С, Пр, ц
Теперь мы займемся изучением особенностей операций С, Пр и ц над вычислимыми функциями.
Как и в случае предыдущих функциональных систем, мы будем рассматривать функции Цхи ..., ?„) с точностью до добавлений и изъятий несущественных переменных и, более точно, несущественных переменных определенного вида. Это связано с тем, что вычислимая функция ${хи х„) определена на некотором множестве Е,л которое пе обязательно совпадает с множеством всех наборов (аь ..., «„) чисел из расширенного натурального ряда. Б этом случае, если рассматривать несущественную переменную по аналогии с функциями из 1\ как переменную, от которой для наборов из Е} функция не зависит, то возникают некоторые трудности. Например, процесс изъятия несущественных переменных может быть неоднозначным. (См. соответствующее рассуждение для не всюду определенных функций из Рк в гл. 3.) Ввиду ЭТОГО переменную XI функции 1(хи . . Я,,) ИЗ Рьыч
