Частично-рекурсивные функции

Функция f(x₁, . . . , x_n+1) получается из функции g(x₁, . . . , x_n+1) с помощью операции минимизации, если справедливо следующее соотношение:

f(x₁, ... , x_n+1) = mt(g(x₁, . . . , x_n, t) = x_n+1) (1)

Приведенная запись означает, что должны выполняться следующие два свойства:

1) f(x₁, . . . , x_n+1) равно наименьшему t, при котором выполняется равенство в правой части соотношения (1);

2) все значения g(x₁, ... , x_n, i), i t определены.

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

Действительно, для того, чтобы найти значение f(x₁, . . . , x_n+1), достаточно последовательно определять значения g(x₁, . . . , x_n, 0), . . . , g(x₁, . . . , x_n, i), . . . , до тех пор, пока в такой последовательности значений впервые не встретится значение, равное x_n+1. При этом каждое следующее значение получаемой последовательности не вычисляется до тех пор, пока не вычислено предыдущее значение.

Тогда первое значение i, для которого g(x₁, . . . , x_n, i) = x_n+1, берется в качестве f(x₁, . . . , x_n+1).

Пример. Если g(x, y) = x+y, то f(x, y) = mt(g(x, t) = y) - это следующая функция:

f(x, y) = .

Приведенный пример показывает, что функция f, получаемая из функции g с помощью операции минимизации, может оказаться не всюду определенной, или частичной вычислимой, функцией.

Упражнение. Показать, что если числовая функция f(x) имеет обратную функцию, то f^-1(x) = mt(f(t) = x).