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

На основную теорему предыдущего пункта мы будем ссылаться как на теорему о перечислении для рекурсивно перечислимых множеств. В дальнейшем нам понадобятся несколько других теорем о перечислении. Все они будут выведены из усиленного варианта теоремы, которую мы уже доказали.

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

Пример. Множество четных чисел, определенное в имеет базис

является кодом доказательства того, что четыре — четное число.

Имеется разрешимое отношение V между натуральными числами и общерекурсивная функция переводящая натуральные числа в слова в данном алфавите, такие, что тогда и только тогда, когда есть гёделевский номер некоторого рекурсивно перечислимого множества и есть номер доказательства некоторого элемента а этого множества, причем в этом случае

Эту теорему можно считать аналогом теоремы Клини о нормальной форме. Она представляет универсальное отношение в виде композиции разрешимого отношения V и общерекурсивной функции

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

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

Построение общерекурсивной функции даже проще. Если лексикографический гёделевский номер слова в оканчивающегося на а, где а — слово в то Иначе полагаем, например,

Эта теорема важна по той причине, что, как указывается ниже, она позволяет для всякого порождать в определенном порядке элементы рекурсивно

перечислимого множества, гёделевский номер которого есть

(см. скан)

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

Если дано рекурсивно перечислимое отношение мы можем найти частично рекурсивную функцию с той же областью, такую, что влечет за собой

Достаточно порождать элементы принадлежащие описанным выше способом и определить если для всех

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

Существует частично рекурсивная функция такая, что если есть гёделевский номер частично рекурсивной функции то тогда и только тогда, когда

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

в том, что не все они — функции. Пусть дано произвольное натуральное число и мы порождаем последовательно элементы того множества, гёделевский номер которого равен если такие имеются. Если имеет вид где слова в соответственно, и свойство функциональности еще не нарушено, для некоторых влечет мы полагаем Так определенное очевидным образом частично рекурсивная функция, и если уже было гё-делевским номером некоторой частично рекурсивной функции то тогда и только тогда, когда Доказательство закончено.

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