8.4. Классификация множеств в иерархии

Интересно посмотреть, какое место разные конкрет­ные множества занимают в описанной нами иерархии. Например, что можно сказать о множестве номеров ка­кой-то фиксированной вычислимой функции в главной нумерации?

Мы уже говорили, что множество всех номеров всех функций с непустой областью определения перечислимо, то есть принадлежит классу Ец. Следовательно, его до­полнение, множество всех номеров нигде не определён­ной функции, принадлежит классу П\. (Классу Ец онопринадлежать не может, так как неразрешимо, см. тео­рему 21, с. 33.)

69. Докажите, что множество номеров нигде не определён­ной функции в любой главной нумерации является т-полным в классе Hi множеством.

А что можно сказать о номерах других функций? Например, что можно сказать о множестве номеров то­ждественно нулевой функции? Оказывается, можно по­лучить в некотором смысле полный ответ на этот вопрос.

Теорема 59. (а) Пусть U — вычислимая универсальная функция для класса вычислимых функций. Тогда мно­жество тех п, при которых Un всюду определено и то­ждественно равно 0, принадлежит классу Щ. (б) Пусть U — главная универсальная функция. Тогда указанное множество является т-полным в классе Щ.

Заметим, что требование главности в пункте (б) су­щественно: в однозначной нумерации (см. с. 35) это мно­жество состоит из единственного номера.

<] Интересующее нас свойство числа п можно запи­сать так: для любого к найдётся такое i, что за i ша­гов вычисление значения U(n,k) закончится и даст ре­зультат 0. Выделенная часть является разрешимым свой­ством, а перед ней стоят два квантора как раз нужного вида. Итак, пункт (а) доказан.

Докажем утверждение (б). Пусть имеется произволь­ное множество Р из класса Щ. При этом

х <Е Р     \/y3zR(x, у, z),

где R — некоторое разрешимое свойство. Рассмотрим теперь функцию S(x,y), вычисляемую таким алгорит­мом: перебирая все числа, ищем число z, для которо­го R(x,y,z); как только (и если) такое число найдено, выдаём на выход 0. Ясно, что х-ое сечение Sx функции S будет тождественно нулевой функцией в том и только том случае, когда х Е Р. Применим свойство главности и получим функцию s, для которой Us(x) = Sx. Она и бу­дет сводить Р к множеству всех номеров тождественно нулевой функции. >

Что можно сказать про другие функции? Для лю­бой вычислимой универсальной функции II и любой вы­числимой функции / множество всех [/-номеров функ­ции / является Щ-множеством. Верен даже более силь­ный факт: свойство 1}т = IIп (числа тжп являются номе­рами одной и той же функции) является Щ-свойством па­ры (т, п), поэтому тем более любое его сечение (т. е. мно­жество всех номеров любой конкретной функции) явля­ется Щ-множеством. В самом деле, свойство 1}т = IIп можно сформулировать так: «для всяких х и t\ найдёт­ся такое ^25 что если вычисление и(т, х) завершается за t■^ шагов, то вычисление II(п, х) завершается за 12 шагов с тем же результатом, и наоборот». Выделенная часть разрешима, а до неё стоит Щ-префикс.

Можно даже понять, для каких функций множест­во номеров является Щ-полным: для функций с беско­нечной областью определения. Если область определения функции конечна, то множество всех её номеров являет­ся О'-разрешимым (и потому не Щ-полным): имея оракул для проблемы остановки, можно убедиться, что функция определена всюду, где она должна быть определена (по­сле чего проверить, что значения правильны), а затем проверить, что ни в одной из оставшихся точек она не определена (процесс поиска точки вне данного конечно­го множества, в которой функция определена, является перечислимым процессом и потому его успешность мо­жет быть проверена с помощью О'-оракула).

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

70. Проведите это рассуждение подробно.

71. Покажите, что множество всех номеров всех всю­ду определённых функций (в главной нумерации) является Щ-полным.

72. В каком наименьшем классе арифметической иерархиилежит множество номеров всех функций с бесконечной обла­стью определения? Будет ли оно т-полным в этом классе?

73. Покажите, что для любой (не обязательно главной!) ну­мерации множество всех номеров всюду определённых функ­ций ненеречислимо. Более того, оно не имеет перечислимого подмножества, включающего в себя хотя бы одному номеру каждой вычислимой всюду определённой функции. (Указание: используйте диагональную конструкцию.)

В книге Х.Роджерса ([8], параграф 14.8) приведе­но много результатов подобного рода для многих дру­гих свойств вычислимых функций и перечислимых мно­жеств. Например, для любого т-полного множества К множество всех его номеров является Щ-полным. (Здесь и далее, говоря о номерах, мы имеем в виду главную ну­мерацию перечислимых множеств.) Множество номеров всех конечных множеств является Ег-полным. Множест­во номеров множеств, содержащих хотя бы один номер бесконечного множества, является Е,э-полным. Множест­во номеров всех разрешимых множеств является Е3-ПОЛ-ным. Множество номеров всех множеств с конечными дополнениями является Е3-ПОЛНЫМ.

74. Докажите перечисленные утверждения (или прочтите их доказательства в книге Роджерса [8]).

75. Рассмотрим квантор Э°°г;, который читается как «су­ществует бесконечно много х, для которых». Покажите, что все свойства из класса Щ (и только они) представимы в виде

Э°°г; (разрешимое свойство)

и что все свойства из класса Х)з (и только они) представимы в виде

Э°°г;Уу (разрешимое свойство).

(Аналогичное утверждение верно и для старших классов, см. теорему XVIII в разделе 14.8 книги [8].)