2.3. Перечислимое неразрешимое множество

Теперь мы можем доказать обещанное утверждение.

Теорема 11. Существует перечислимое неразрешимое множество. (Переформулировка: существует перечисли­мое множество с неперечислимым дополнением.)

<] Рассмотрим вычислимую функцию f(x), не имею­щую всюду определённого вычислимого продолжения. Её область определения Р будет искомым множеством. В са­мом деле, Р перечислимо (по одному из определений пе­речислимости). Если бы Р было разрешимо, то функция

 

f(x), если х £ F О, если X '£ I

была бы вычислимым всюду определённым продолжени­ем функции / (при вычислении д(х) мы сначала проверя­ем, лежит ли х в F, если лежит, то вычисляем f(x)). \>

Полезно проследить, какое именно множество в итоге оказалось перечислимым и неразрешимым. Легко понять, что это множество тех п, при которых U(n,n) опреде­лено. Если вспомнить конструкцию функции U, то это множество тех п, при которых п-я программа остана­вливается на п. Поэтому иногда говорят, что «проблема самоприменимости» (применимости программы к своему номеру) неразрешима.

Заметим, что отсюда следует, что и область опреде­ления всей универсальной функции U является перечи­слимым неразрешимым множеством пар. (Если бы про­блема выяснения применимости программы к произволь­ному аргументу была бы разрешима, то и её частный случай — применимость программы к себе — был бы разрешим.)

Перечислимые неотделимые множества

20. Пусть О — перечислимое множество пар натуральных чисел, универсальное для класса всех иеречислимых множеств натуральных чисел. Докажите, что его «диагональное сече­ние» К = {з; | (з;,з;) £ 0} является иеречислимым неразреши­мым множеством.

21. Некоторое множество 5 натуральных чисел разреши­мо. Разложим все числа из 5 на простые множители и со­ставим множество I) всех простых чисел, встречающихся в этих разложениях. Можно ли утверждать, что множество О разрешимо?

22. Множество I] С N х N разрешимо. Можно ли утвер­ждать, что множество «нижних точек» множества О, то есть множество

V =       У) I «ж> У) € и) и ({з;, г) £ О для всех г < у)}

является разрешимым? Можно ли утверждать, что V иеречи-слимо, если О перечислило?

23. Покажите, что существуют иеречислимые снизу, но не вычислимые числа в смысле определений, данных на с. 16. (Указание. Рассмотрим сумму ряда 5^2-* но всем к из како­го-либо иеречислимого множества Р. Она всегда перечислила снизу, но будет вычислимой только при разрешимом Р.)

Мы вернёмся к вычислимым действительным числам в задачах 31 и 60.