Т. А. Сливина математическая логика и теория алгоритмов

§ 2. Разрешимые и перечислимые множества

Пусть имеется некоторый алфавит. Обозначим через S множество всех слов в данном алфавите, а через М - подмножество множества S.

Определение 1. Множество М называется разрешимым, если для него существует алгоритм, решающий проблему вхождения слова х в М.
Определение 2. Множество М называется эффективно перечислимым, если существует алгоритм, позволяющий перечислить все элементы этого множества (возможно с повторениями).
Теорема 1. Если множества М и L эффективно перечислимы, то эффективно перечислимы множества M L и M L.
Доказательство. Пусть множества М и L эффективно перечислимы. Тогда для каждого из них существует свой алгоритм, позволяющий перечислить все элементы данного множества. Алгоритм для эффективного перечисления множеств M L и M L получается путем одновременного применения алгоритмов для эффективного перечисления множеств М и L.
Теорема 2 (Поста). Множество М разрешимо тогда и только тогда, когда оно само и его дополнение эффективно перечислимы.
Доказательство. Пусть множество М и его дополнение СМ эффективно перечислимы, то есть существуют алгоритмы А и В, с помощью которых можно перечислить элементы этих множеств. Но тогда при перечислении элементов множеств М и СМ в их списке встретится элемент х. Следовательно, существует алгоритм С, позволяющий узнать, принадлежит элемент х множеству М или не принадлежит.
Пусть множество М разрешимо. Тогда существует алгоритм, решающий проблему вхождения х в М. Пользуясь этим алгоритмом, составим список элементов, входящих в М, и список элементов, входящих в СМ. Следовательно, мы получим два алгоритма А и В, позволяющих перечислить множества М и СМ. Примерами эффективно перечислимых множеств являются:

1. 
   множество М = (1,4,9,...,n²,...) квадратов натуральных чисел,
   
2. 
   множество упорядоченных пар натуральных чисел.
   

Действительно, множество М = n² перечислимо, т.к. для получения его элементов нужно последовательно брать натуральные числа и возводить их в квадрат. Более того, это множество является также и разрешимым: для проверки того, принадлежит ли некоторое натуральное число х множеству М, нужно разложить число на простые множители, и это даст возможность установить, является ли оно точным квадратом.
Множество упорядоченных пар натуральных чисел может быть эффективно перечислено с помощью так называемого диагонального метода. Действительно, выпишем все упорядоченные пары натуральных чисел в следующем виде:

(0,0)	(0,1)	(0,2)	(0,3)	(0,4)	…
(1,0)	(1,1)	(1,2)	(1,3)	(1,4)	…
(2,0)	(2,1)	(2,2)	(2,3)	(2,4)	…
(3,0)	(3,1)	(3,2)	(3,3)	(3,4)	…
…	…	…	…	…	…

Перечисление осуществляется последовательным прохождением по диагоналям, начиная, с верхнего левого угла. Начальный список этих пар запишется так:

(0,0), (1,0), (0,1), (2,0), (1,1), (0,2), (3,0), (2,1), (1,2), (0,3), (4,0), ...