Пример 7

Рассмотрим примитивно рекурсивную функцию: g(x,y)  =  x – Sg(y), где Sg(y)  =  0, при y  =  0, и Sg(y)  =  1, для y  >  0. Тогда значения:

f(x) =  y[x-Sg(y)=  0]

не определены при x  >  1. Наименьшее среди y    N, удовлетворяющих 0 – Sg(y)  =  0, будет равно 0, а наименьшее среди y, при которых 1 – Sg(y)  = 0, равно 1. Следовательно, f(0)  =  0, f(1)  =  1, и f(x) не определены при x  >  1. Функция x – Sg(y) примитивно рекурсивная, значит, f(x) – частично рекурсивная.

Пусть А – подмножество натуральных чисел. Частичной характеристической функцией множества А называется частичная функция C_A: N  N, равная 0 в точках множества А и не определенная вне А. Множество А называется частично рекурсивным, если его частичная характеристическая функция частично рекурсивна. Множество А называется примитивно рекурсивным, если функция N  N, равная 0 на А и равная 1 вне А, является примитивно рекурсивной.

Теорема. Пусть f: N  N – примитивно рекурсивная функция, A    N – примитивно рекурсивное множество. Тогда частичная функция f_A: N  N, определенная как f_A(x)  =  f(x) для x    A и неопределенная при x    A, является частично рекурсивной.

Доказательство. Легко видеть, что f_A(x)  =  f(x) + C_A(x). Поэтому f_A частично рекурсивна, как сумма частично рекурсивных функций.

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

Тезис Чёрча. Класс алгоритмически (или машинно) вычислимых частичных числовых функций совпадает с классом всех частично рекурсивных функций.