Т.14.1.(1)Теорема
Примитивно-рекурсивные функции эффективно перечислимы.
Доказательство
Из теоремы Клини следует, что примитивно-рекурсивные функции могут быть представлены в виде операторного терма, т.е. в виде схемы примитивной рекурсии, в которой используется всего несколько функциональных символов: для трех функций Cqn, S (без индексов), Umn и двух операций: Smn с двумя индексами для подстановки и Rn для примитивной рекурсии.
Построим доказательство эффективной перечислимости примитивно-рекурсивных функций на основе геделевой нумерации.
Для этого надо ввести кодовые номера для всех символов:
Введем такие номера
S (следование) ® 1
C ® 2
U ® 3
S (подстановка) ® 4
R (примитивная рекурсия) ® 5
(® 6
) ® 7
, ® 8
xi ® i+9 (здесь xi – номер переменной)
Возьмем ряд простых чисел: 2,3,5,7,…Дальнейшая процедура аналогична геделевой нумерации, например, алгоритмов Маркова.
Например,
x+y=R2[U11,S13(S,U13)]= 25*312*56*73*1110*1310*178*…
Т.о. мы получили геделев номер примитивно-рекурсивного описания функции суммы двух аргументов. Геделевы номера эффективно распознаются среди натуральных чисел, следовательно их описания можно эффективно перечислить, а значит множество ПРФ – эффективно перечислимо, Q.E.D.
Т.14.1.(2)Теорема
Множество частично-рекурсивных функций эффективно перечислимо.
Доказательство
Для наших целей важно, чтобы перечисление частично-рекурсивных функций было эффективным, т. е. чтобы у нас был эффективный способ нахождения n -й функции списка или хотя бы способ нахождения ее определения. Хотя это может показаться странным, но будет достаточно знать, что перечисление существует - нам даже не потребуется выяснять какие-либо подробности о его свойствах. Следовательно, вместо подробного доказательства, достаточно привести убедительный довод в пользу его возможности, т. е. что мы могли бы построить его, если бы это потребовалось.
Почему мы все же могли предположить, что существует эффективное перечисление частично-рекурсивных функций? В конце концов, они образуют фантастически богатое, причудливое и неупорядоченное множество объектов, поскольку в это множество входят объекты, соответствующие всем возможным рекурсивным определениям.
На самом деле при ближайшем рассмотрении ясно, что определение каждой частично-рекурсивной функции состоит из конечного набора уравнений, каждое из которых включает конечное число символов, обозначающих нуль, тождество, следование, примитивную рекурсию, суперпозицию и наименьшее число в сочетании с конечным числом запятых и скобок. Точные правилаих расположения не важны. Важно то, что в любой такой ситуации, всегда можно ввести некоторого рода бесконечное лексикографическое упорядочение составных объектов. Хотя эта ситуация кажется более сложной, есть способ сделать ее даже проще. Действительно, поскольку большинство частично-рекурсивных функций (или, скорее, определений) вовсе не определяет истинного окончания процесса вычислений, нам не надо слишком заботиться, чтобы при перечислении определений все последовательности символов были правильными. Действительно, мы можем рассмотреть какую-либо процедуру, которая, в конце концов, образует любую (и все) последовательности символов, требуемых для определений. Имеется только одна техническая проблема - остаться в рамках фиксированного алфавита. Она решается использованием, скажем, двоичного кодирования неограниченного числа названий переменных и функций, которые могут потребоваться. Тогда простая схема числового упорядочения будет эффективным перечислением при условии, что существует способ правильной интерпретации n -го описания.
Бесконечное лексикографическое упорядочение составных объектов легко нумеруется при помощи алгоритма Геделя. Из теоремы Клини следует, что частично-рекурсивные функции могут быть представлены в виде операторного терма, т.е. в виде схемы частичной рекурсии, в которой используется всего несколько функциональных символов: для трех функций Cqn, S (без индексов), Umn и трех операций: Smn с двумя индексами для подстановки, Rn для примитивной рекурсии и μ для минимизации. Учитывая этот факт, снимается вопрос о правильной интерпретации n -го описания: если кодировать будем не системы уравнений, а схемы частично-примитивных рекурсий в виде операторных термов, то такая интерпретация будет автоматической.
Построим доказательство эффективной перечислимости на основе геделевой нумерации. Для этого надо ввести кодовые номера для всех элементов при помощи геделевой нумерации.
Введем такие номера
S (следование) ® 1
C (константа) ® 2
U (тождества) ® 3
S (подстановка) ® 4
R (примитивная рекурсия) ® 5
Μ (минимизация) ® 6
(® 7
) ® 8
, ® 9
xi ® i+10
Возьмем ряд простых чисел: 2,3,5,7,…Дальнейшая процедура аналогична геделевой нумерации примитивно-рекурсивных функций. Т.о. мы получили геделев номер частично-рекурсивного описания. Геделевы номера эффективно распознаются среди натуральных чисел, следовательно, частично-рекурсивные функции можно эффективно перечислить, Q.E.D.
Предостережение: не делайте никаких далеко идущих предположений! Некоторые функции fn(x) не могут быть определены даже хотя бы для одного значения x. Некоторые функции с разными индексами, например fi (x) и fj (x), могут быть одинаковыми: fi(x) = fj(x) для всех x. Действительно, некоторые функции могут появляться в списке бесконечно часто, что соответствует совершенно разным определениям. Единственное, в чем мы уверены, это то, что если функция частично-рекурсивна, то она имеет по крайней мере один индекс в перечислении.
Т.14.1.(3)Теорема
Общерекурсивные функции не поддаются эффективному перечислению.
На уровне тезисов:
Из тезиса Чёрча: всякая арифметическая функция, вычислимая в обычном смысле (ВАФ), есть обще рекурсивная функция (ОРФ), а всякая частичная арифметическая функция, вычислимая в обычном смысле (ЧВАФ), есть частично рекурсивная функция (ЧРФ). Известно (на основании теоремы Тьюринга), что ВАФ эффективно не перечислимы. Отсюда следует, что и ОРФ эффективно не перечислимы.
Доказательство
Допустим, что множество общерекурсивных функций 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
§ 14.2. Эффективная распознаваемость рекурсивных функций
Т.14.2.(1)Теорема
Примитивно-рекурсивные функции не поддаются эффективному распознаванию среди общерекурсивных функций.
Доказательство
Возьмем общерекурсивную, но не примитивно-рекурсивную функцию f(x). Построим g(x) следующим образом:
f(x) если машина Т не остановится за первые x+1 тактов
g(x) =
0 во всех иных случаях
Функция g(x) тоже общерекурсивна (в силу того, что она везде определена и вычислима). Но на самом деле, если Т все-таки остановится, то g(x) будет являться также примитивно-рекурсивной (потому что функция, отличная от нуля в конечном числе точек всегда примитивно-рекурсивна). Пусть мы умеем (знаем какой-то алгоритм) распознавать примитивно-рекурсивные функции среди общерекурсивных функций. Применим этот алгоритм к общерекурсивной функции g(x). Если удастся сказать, является ли она примитивно-рекурсивной, значит, окажется решенной и задача об остановке машины Тьюринга, что противоречит ранее доказанной теореме.
Значит наше предположение не верно, следовательно, примитивно рекурсивные функции не поддаются эффективному распознаванию среди всех общерекурсивных функций, Q.E.D.
Т.14.2.(2)Теорема