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

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

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

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

На самом деле при ближайшем рассмотрении ясно, что определение каждой частично-рекурсивной функции состоит из конечного набора уравнений, каждое из которых включает конечное число символов, обозначающих нуль, тождество, следование, примитивную рекурсию, суперпозицию и наименьшее число в сочетании с конечным числом запятых и скобок. Точные правилаих расположения не важны. Важно то, что в любой такой ситуации, всегда можно ввести некоторого рода бесконечное лексикографическое упорядочение составных объектов. Хотя эта ситуация кажется более сложной, есть способ сделать ее даже проще. Действительно, поскольку большинство частично-рекурсивных функций (или, скорее, определений) вовсе не определяет истинного окончания процесса вычислений, нам не надо слишком заботиться, чтобы при перечислении определений все последовательности символов были правильными. Действительно, мы можем рассмотреть какую-либо процедуру, которая, в конце концов, образует любую (и все) последовательности символов, требуемых для определений. Имеется только одна техническая проблема - остаться в рамках фиксированного алфавита. Она решается использованием, скажем, двоичного кодирования неограниченного числа названий переменных и функций, которые могут потребоваться. Тогда простая схема числового упорядочения будет эффективным перечисле­нием при условии, что существует способ правильной интерпретации n-го описания.

Бесконечное лексикографическое упорядочение составных объектов легко нумеруется при помощи алгоритма Геделя. Из теоремы Клини следует, что частично-рекурсивные функции могут быть представлены в виде операторного терма, т.е. в виде схемы частичной рекурсии, в которой используется всего несколько функциональных символов: для трех функций C_qⁿ, S (без индексов), U_mⁿ и трех операций: S_mⁿ с двумя индексами для подстановки, Rⁿ для примитивной рекурсии и μ для минимизации. Учитывая этот факт, снимается вопрос о правильной интерпретации n-го описания: если кодировать будем не системы уравнений, а схемы частично-примитивных рекурсий в виде операторных термов, то такая интерпретация будет автоматической.

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

Введем такие номера

S (следование) ® 1

C (константа) ® 2

U (тождества) ® 3

S (подстановка) ® 4

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

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

(® 7

) ® 8

, ® 9

x_i ® i+10

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

Т.14.1.(3)Теорема