§ 12.13. Рекурсивно-перечислимые и рекурсивные множества

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

Сделаем теперь относительно этих определений несколько замечаний:

Замечание относительно . Доказано, что если некоторое множество можно пересчитать общерекурсивной функцией с повторениями, то оно может быть пересчитано и без повторений (некоторой другой общерекурсивной функцией).

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

иначе

Равенство может рассматриваться как общерекурсивное отношение равенства двух общерекурсивных функций:

где

Замечание относительно . Определение является лишь уточнением определения .

Замечание относительно ЗБ. Из выполнения условия ЗБ следует выполнение условия . Действительно, пусть множество С перечисляется общерекурсивной функцией , а С — функцией .

Для того чтобы узнать, принадлежит ли данное число множеству С, будем параллельно вычислять последовательности

Так как число у принадлежит либо С, либо С, то оно рано или поздно должно встретиться или в ряду I, или в ряду II. Если оно встретилось в ряду I, , если в II — . Поэтому имеется алгоритм распознавания принадлежности любого у множеству С.

Замечание относительно . При условии также имеется алгоритм распознавания принадлежности любого у множеству С. Действительно, будем вычислять последовательность . Если при некотором , то процессу вычисления можно остановить и сделать вывод, что ; если же встретится такое, что , то .

Приведем примеры рекурсивных множеств:

1) Двухэлементное множество рекурсивно в силу условий или .

2) Любое конечное множество рекурсивно в силу условий или .

3) Множество четных чисел рекурсивно. Здесь , и множество рекурсивно в силу условия или , и множество рекурсивно в силу условия .

Приведем теперь примеры рекурсивно-перечислимых и не рекурсивно-перечислимых множеств.

Согласно определению рекурсивно-перечислимым множеством будет множество тех у, для которых при некотором общерекурсивном . Можно так подобрать , что множество будет рекурсивно-перечислимым, но не рекурсивным; его дополнение будет множеством тех у, для которых

(где Q — общерекурсивный предикат); это множество

будет не рекурсивно и не рекурсивно-перечислимо.

Множество гёделевских номеров z тех систем Е, которые определяют общерекурсивную функцию, не рекурсивно и не рекурсивно-перечислимо.

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

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

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