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

Теорема 2. Всякое разрешимое множество натураль­ных чисел перечислимо. Если множество А и его допол­нение (до множества всех натуральных чисел) перечисли­мы, то А разрешимо.

<] Если принадлежность числа к множеству А мож­но проверить некоторым алгоритмом, то А и его допол­нение перечислимы: надо по очереди проверять принад­лежность чисел 0,1, 2,... и печатать те из них, которые принадлежат А (или те, которые не принадлежат А).

В другую сторону: если у нас есть алгоритм, перечи­сляющий А, а также другой алгоритм, перечисляющий дополнение к А, то для выяснения принадлежности за­данного числа п к А надо запустить оба эти алгоритма и ждать, пока один из них напечатает п (мы знаем, что рано или поздно ровно один из них это сделает). Посмо­трев, какой алгоритм это сделал, мы узнаем, лежит ли п в А. >

Этот факт называют теоремой Поста.

Она говорит, что разрешимые множества — это пе­речислимые множества с перечислимыми дополнениями. Напротив, перечислимые множества можно определить через разрешимые:

Теорема 3. Множество Р натуральных чисел перечи­слимо тогда и только тогда, когда оно является проекци­ей некоторого разрешимого множества Q пар натураль­ных чисел. (Проекция получается, если от пар оставить их первые компоненты: х £ Р -<=> Зу((х, у) £ Q)-)

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

Напротив, если Р — перечислимое множество, пере­числяемое алгоритмом А, то оно есть проекция разреши­мого множества Q, состоящего из всех таких пар (х,п), что х появляется в течении первых п шагов работы ал­горитма А. (Это свойство, очевидно, разрешимо.) >