Доказательство окончено. Пусть заданы такие примитивно-рекурсивные функции gi(x1

ТЕОРЕМА 8.2

Пусть заданы такие примитивно-рекурсивные функции g_i(x₁, . . . , x_n), i = 1, . . . , k, что на всяком наборе значений переменных лишь одна из этих функций равна 0.

Кроме того, пусть заданы примитивно-рекурсивные функции h_i(x₁, . . . , x_n), i = 1, . . . , k.

Тогда функция f(x₁, . . . , x_n), определяемая выражением:

h₁(x₁, . . . , x_n), если g₁(x₁, . . . , x_n)=0

f(x₁ , . . . , x_n) = . . .

h_k(x₁, . . . , x_n), если g_k(x₁, . . . , x_n)=0является примитивно-рекурсивной.

Доказательство

Очевидно, что f можно представить с помощью следующего выражения:

f(x₁, . . . , x_n) = (h_i(x₁, . . . , x_n) (g_i(x₁, . . . , x_n)).

Доказательство окончено.

Заметим, что примитивная рекурсивность функции
div(x, y) может быть установлена на основании теоремы 8.1 с помощью соотношения:

div( x, y) = ( (iy - x)).

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

Функция 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).

ОПРЕДЕЛЕНИЕ

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

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

ТЕЗИС ЧЁРЧА

Частично-рекурсивные функции - это класс числовых функций, представляемых точно определенными формальными средствами.

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

Класс всех интуитивно вычислимых числовых функций

совпадает с классом частично-рекурсивных функций

Приведенное утверждение носит название тезиса Чёрча, по имени сформулировавшего этот тезис американского математика.

Данный тезис связывает интуитивное понятие вычислимости числовых функций и формальное определение частичной рекурсивности. Поэтому он является недоказуемым.

О справедливости тезиса Чёрча свидетельствуют следующие имеющиеся факты:

1)для всякой конкретной числовой функции удается построить её рекурсивное определение;

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