Шаг 15.
Понятие рекурсии.
Частично рекурсивные функции

    На этом шаге мы рассмотрим частично рекурсивные функции.

    Пусть задана функция f(x1, ..., xn, y).

    Определение. Говорят, что φ(x1, ..., xn) получена из f(x1, ..., xn, y) с применением операции ограниченной минимизации, если имеет место следующее равенство:

(44)

и обозначают φ(x1, ..., xn) = μγ(f(x1, ..., xn, y) = 0). (45)

Лемма 2.
Операция ограниченной минимизации сохраняет свойство примитивной рекурсивности функции.

    Действительно, если имеется алгоритм Af, вычисляющий функции f(x1, ..., xn, y), то есть и алгоритм Aφ, вычисляющий функции φ(x1, ..., xn).

Доказательство.
Пусть требуется вычислить значение функции φ на произвольном наборе (x1, ..., xn).

    Применим алгоритм Af к набору (x1, ..., xn, 0). Если через конечное число шагов алгоритм завершает свою работу результативно, т.е. вычислено значение f(x1, ..., xn, 0) и f(x1, ..., xn, 0) = 0, то значение функции φ на наборе (x1, ..., xn) считаем равным 0. Если f(x1, ..., xn, 0) <> 0, то переходим к следующему этапу, на котором применяем алгоритм Af к набору (x1, ..., xn, 1).

    Если через конечное число шагов алгоритм завершает свою работу на данном наборе результативно, т.е. вычислено значение f(x1, ..., xn, 1) и f(x1, ..., xn, 1) = 0, то значение функции φ на наборе считаем равным 1. Если f(x1, ..., xn, 1) <> 0, то переходим к следующему этапу и т.д.

    Если на (t+1) шаге вычислено значение f(x1, ..., xn, t) и f(x1, ..., xn, t) = 0, то значение функции φ на наборе (x1, ..., xn) считаем равным t. Если f(x1, ..., xn, t) <> 0, то переходим к следующему этапу.

    В случае, когда алгоритм Af завершает свою работу на каком-то этапе безрезультативно, или работает бесконечно, то будем считать, что значение φ не определено на данном наборе, т.е. на наборе (x1, ..., xn).


    Пример 1. Пусть

    Тогда

т.е. функция φ(x) только при y = x принимает значение нуль.


    Пример 2. Пусть f(x,y) = |x - 2y|. Определим φ(x) = μγ[|x - 2y| = 0].

    Очевидно, что функция φ определена только на числах вида 2k, k = 0, 1, 2, ...; и для каждого из них φ(2k) = k.


    Пример 3. В качестве примера не всюду определенной функции можно привести следующую функцию:

    Действительно, при этом функция φ(x) не определена во всех натуральных наборах, так как φ(x) = μγ[C82(x,y) = 0]- не имеет места ни для одного y. Следовательно, будем говорить, что φ(x) - нигде не определенная функция.

    Из этих примеров следует, что операция минимизации, вообще говоря, не сохраняет свойство всюду определенности функции (примеры 2, 3) и наоборот, применение операции минимизации к функции не везде определенной может дать всюду определенную функцию (пример 1).

    Определение. Частично рекурсивным описанием (ЧРО) функции f называется конечная последовательность функций φ1, ..., φk, удовлетворяющих следующим условиям:

  1. φk = f;
  2. Для любого i, 1<=i<=k, φk - является либо элементарной функцией, либо получается из предшествующей ей последовательности функций с помощью одной из операций: подстановки, примитивной рекурсии или ограниченной минимизации.

    Определение. Функция f называется ЧРФ, если существует ее ЧРО.

    Определение. Функция f называется общерекурсивной, если она ЧРФ и всюду определена. (Такие функции еще называют тотальными или просто рекурсивными.)

    Не трудно показать, что всякая частично рекурсивная функция алгоритмически вычислима и операции подстановки, примитивной рекурсии и минимизации сохраняют свойству алгоритмическую вычислимость функций.

    Очевидно, каждая примитивно рекурсивная функция является частично рекурсивной, но обратное неверно.

    Введем обозначения:

    Тогда между этими классами имеется соотношения:

KПРФ ⊆ KОРФ ⊆ KЧРФ.

    Таким образом, класс ЧРФ - самый богатый из построенных классов вычислимых функций и имеет место следующее включение:

KЧРФ ⊆ КВФ,

где КВФ - класс вычислимых функций.

    Тезис Черча-Клини представляет гипотезу, из которой следует обратное включение, т.е.

КВФ ⊆ KЧРФ

    Таким образом, класс алгоритмически вычислимых функций совпадает с классом частично рекурсивных функций. Как уже отмечались, это утверждение не может быть доказанным, так как в нем участвует понятие вычислимой функции. Тем не менее можно привести следующие два довода в пользу тезиса Черча - Клини:

    На следующем шаге мы рассмотрим итерацию.




Предыдущий шаг Содержание Следующий шаг