- •8. Рекурсивные функции
- •8.1. Вычислимые функции
- •8.2. Частично рекурсивные функции
- •8.2.3. Примитивно-рекурсивные функции
- •Определение
- •Теорема 8.1
- •Доказательство
- •8.2.4. Частично-рекурсивные функции
- •Определение
- •8.3. Тезис чёрча
- •Класс всех интуитивно вычислимых числовых функций совпадает с классом частичнорекурсивных функций
- •8.4. Нумерация частично-рекурсивных
- •8.5. Алгоритмическая разрешимость
- •8.5.1. Разрешимые множества
- •8.5.2. Проблема остановки
- •8.5.3. Проблема всюду определенности
- •8.5.4. Проблема эквивалентности
Теорема 8.1
Функция f(x1, . . . , xn+1), задаваемая выражением
f(x1, . . . , xn+1) = g(x1, . . . , xn,i) примитивно-рекурсивная функция, если g(x1, . . . , xn, xn+1) является примитивно-рекурсивной.
Доказательство
Очевидно, что функция f может быть задана следующей схемой примитивной рекурсии:
f(x1, ... , xn, 0) = g(x1, . . . , xn, 0);
f(x1, ... , xn, y+1) = f(x1, . . . , xn, y) + g(x1, . . . , xn, y + 1).
Доказательство окончено.
ТЕОРЕМА 8.2
Пусть заданы такие примитивно-рекурсивные функции gi(x1, . . . , xn), i = 1, . . . , k, что на всяком наборе значений переменных лишь одна из этих функций равна 0.
Кроме того, пусть заданы примитивно-рекурсивные функции hi(x1, . . . , xn), i = 1, . . . , k.
Тогда функция f(x1, . . . , xn), определяемая выражением:
h1(x1, . . . , xn), если g1(x1, . . . , xn)=0
f(x1 , . . . , xn) = . . .
hk(x1, . . . , xn), если gk(x1, . . . , xn)=0 является примитивно-рекурсивной.
Доказательство
Очевидно, что f можно представить с помощью следующего выражения:
f(x1, . . . , xn) = (hi(x1, . . . , xn) (gi(x1, . . . , xn)).
Доказательство окончено.
Заметим, что примитивная рекурсивность функции div(x, y) может быть установлена на основании теоремы 8.1 с помощью соотношения:
div( x, y) = ( (iy x)).
8.2.4. Частично-рекурсивные функции
Функция f(x1, . . . , xn+1) получается из функции g(x1, . . . , xn+1) с помощью операции минимизации, если справедливо следующее соотношение:
f(x1, ... , xn+1) = t(g(x1, . . . , xn, t) = xn+1) (1)
Приведенная запись означает, что должны выполняться следующие два свойства:
1) f(x1, . . . , xn+1) равно наименьшему t, при котором выполняется равенство в правой части соотношения (1);
2) все значения g(x1, ... , xn, i), i t определены.
Нетрудно проверить, что если функция g является вычислимой, то функция f, получаемая из g с помощью операции минимизации, также оказывается вычислимой.
Действительно, для того, чтобы найти значение f(x1, . . . , xn+1), достаточно последовательно определять значения g(x1, . . . , xn, 0), . . . , g(x1, . . . , xn, i), . . . , до тех пор, пока в такой последовательности значений впервые не встретится значение, равное xn+1. При этом каждое следующее значение получаемой последовательности не вычисляется до тех пор, пока не вычислено предыдущее значение.
Тогда первое значение i, для которого g(x1, . . . , xn, i) = xn+1, берется в качестве f(x1, . . . , xn+1).
Пример. Если g(x, y) = x+y, то f(x, y) = t(g(x, t) = y) это следующая функция:
f(x, y) = .
Приведенный пример показывает, что функция f, получаемая из функции g с помощью операции минимизации, может оказаться не всюду определенной, или частичной вычислимой, функцией.
Упражнение. Показать, что если числовая функция f(x) имеет обратную функцию, то f1(x) = t(f(t) = x).
Определение
Функции, получаемые из простейших с помощью конечного числа применений операций суперпозиции, примитивной рекурсии и минимизации, называются частичнорекурсивными функциями.
Все частично-рекурсивные функции являются вычислимыми, поскольку вычислимы элементарные функции и все операции, применяемые в определениях частично рекурсивных функций.