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

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

f (x ₁,..., x_{n +1}) = m t (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) = m t (g (x, t) = y) - это следующая функция:

f (x, y) = .

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

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

Дата добавления: 2015-03-31