3. Рекурсивно перечислимые множества и отношения

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

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

Пусть а обозначает слово в данном алфавите, и пусть рекурсивно перечислимые множества слов в том же алфавите. Введем следующие определения.

(читается «а принадлежит или «а является элементом множества ), если а доказуемо в системе Поста

если а не принадлежит т. е. если любое доказательство в системе Поста оканчивается словом, отличным от .

если любое слово в данном алфавите, доказуемое в системе Поста доказуемо также в

если

Два примера рекурсивно перечислимых множеств были уже приведены в предыдущем пункте. Добавим к ним следующие чуть менее тривиальные примеры.

Пример. Множество чисел, не являющихся простыми.

(см. скан)

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

(см. скан)

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

Пусть рекурсивно перечислимые множества слов в алфавите

объединение множеств определяется как система Поста, схемами которой являются схемы первого множества, отмеченные знаком схемы второго, отмеченные знаком и новые схемы

Здесь мы не стали явно выписывать знаки, вспомогательные знаки и переменные определяемых нами систем Поста. Мы часто будем допускать такого рода неточности, если не будет опасности путаницы. Непосредственно видно, что если а — слово в алфавите то тогда и только тогда, когда или Этим оправдывается наше определение.

Заменяя последние две схемы из определения на

мы получаем пересечение обладающее тем свойством, что тогда и только тогда, когда

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

Предположим теперь, что даны два алфавита Рекурсивно перечислимое отношение — это рекурсивно перечислимое множество слов вида в алфавите где а и слова в соответствующих алфавитах (т. е. а есть слово в алфавите слово в алфавите Мы будем использовать запись чтобы выразить тот факт, что принадлежит отношению

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

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

Пример, Сложение натуральных чисел.

(см. скан)

Пример. Умножение натуральных чисел,

(см. скан)

Пример. Факториал.

(см. скан)

Пример. Лексикографически следующий.

(см. скан)

Пример. Лексикографическая гёделевская нумерация.

(см. скан)

вместе со схемами из предыдущего примера.

Область определения рекурсивно перечислимого отношения между словами в и словами в это рекурсивно перечислимое множество, получаемое с помощью нанесения метки на схемы рассматриваемого отношения и добавления новых схем

Аналогичным образом мы получаем область значений, заменяя последнюю схему на

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

Образ рекурсивно перечислимого множества слов в относительно рекурсивно перечислимого отношения между словами в и словами в определяется схемами

вместе со схемами отображаемого множества, отмеченными символом и схемами рассматриваемого отношения, отмеченными символом Прообраз

получается тем же способом, только последняя схема заменяется на

Пусть рекурсивно перечислимое отношение между словами в и словами в и 5 — рекурсивно перечислимое отношение между словами в и словами в Композиция отношений и 5 определяется схемами

вместе с отмеченными схемами и 5.

Наконец, обращение рекурсивно перечислимого отношения это рекурсивно перечислимое отношение, получаемое добавлением схем

к схемам, отмеченным символом