Teoremy

R (примитивная рекурсия) → 5

Μ (минимизация) → 6

(→ 7

) → 8

, → 9

xi → i+10

Возьмем ряд простых чисел: 2,3,5,7,…Дальнейшая процедура аналогична геделевой нумерации примитивно-рекурсивных функций. Т.о. мы получили геделев номер частично-рекурсивного описания. Геделевы номера эффективно распознаются среди натуральных чисел, следовательно, частичнорекурсивные функции можно эффективно перечислить, Q.E.D.

Back

Общерекурсивные функции не поддаются эффективному перечислению.

На уровне тезисов:

Из тезиса Чёрча: всякая арифметическая функция, вычислимая в обычном смысле (ВАФ), есть общерекурсивная функция (ОРФ), а всякая частичная арифметическая функция, вычислимая в обычном смысле (ЧВАФ), есть частично рекурсивная функция (ЧРФ).

Известно (на основании теоремы Тьюринга), что ВАФ эффективно не перечислимы. Отсюда следует, что и ОРФ эффективно не перечислимы

Допустим, что множество общерекурсивных функций n-переменных эффективно перечислимо.

Тогда существует алгоритм, по которому их можно перечислить. Применим этот алгоритм. Получим последовательность:

f0(x1,…,xn), f1(x1,…,xn),.. fn(x1,…,xn),..

Построим диагональную функцию:

fx1(x1,…,xn)+1, x1=…=xn

g(x1,…,xn)=

0, в противном случае

Укажем процедуру вычисления g. Для любых значений x,y,z мы можем сначала провести операцию сравнения, и затем, если x=y=z, отыскать функцию fx. Это вполне рекурсивная операция (сравнение аргументов). Если результат сравнения отрицательный (ложь), значение функции g(x1,…,xn)=0. Если результат сравнения положительный (истина), далее можем применить к ней алгоритм вычисления функции fx(x,x,x) в заданной точке. Такой алгоритм существует в силу рекурсивности функций вида fi(x1,…,xn). Прибавление к результату вычисления единички есть тривиальная рекурсивная функция. Т.о. видно, что эта диагональная функция будет тоже общерекурсивной.

Раз построенная функция принадлежит к множеству общерекурсивных функций, то она должна быть среди ранее эффективно перечисленных функций, но по построению она не может быть среди них, так как от каждой функции она отличается хотя бы в одной точке. Получили противоречие, следовательно, общерекурсивные функции нельзя эффективно перечислить,Q.E.D.

Back