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

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

М -подмножество множества S.

Определение 1. Множество М называется разрешимым, если для него существует алгоритм, решающий проблему вхождения слова х в М.

Определение 2. Множество М называется эффектив­но перечислимым, если существует алгоритм, позволяю­щий перечислить все элементы этого множества (возмож­но с повторениями).

Теорема 1. Если множества М и L эффективно перечислимы, то эффективно перечислимы множества M  L и M  U.

Доказательство. Пусть множества М и L эффектив­но перечислимы. Тогда для каждого из них существует свой алгоритм, позволяющий перечислить все элементы данного множества. Алгоритм для эффективного перечисления множеств М  L и M  L получается путем одновременного применения алгоритмов для эффективного перечисления множеств М и L.

Теорема 2 (Поста). Множество М разрешимо тогда и только тогда, когда оно само и его дополнение эффек­тивно перечислимы.

Доказательство. Пусть множество М и его дополнение СМ эффективно перечислимы, то есть существуют алгорит­мы А и В, с помощью которых можно перечислить элемен­ты этих множеств. Но тогда при перечислении элементов множеств М и СМ в их списке встретится элемент х. Следовательно, существует алгоритм С, позволяющий узнать, принадлежит элемент х множеству М или не принадлежит.

Пусть множество М разрешимо. Тогда существует алгоритм, решающий проблему вхождения х в М. Пользуясь этим алгоритмом, составим список элементов, входящих в М, и список элементов, входящих в СМ. Следовательно, мы получим два алгоритма Л и Б, позволяю­щих перечислить множества М и СМ. Примерами эф­фективно перечислимых множеств являются:

1) множество М = < 1, 4, 9,..., га,...> квадратов натуральных чисел,

2) множество упорядоченных пар натуральных чи­сел.

Действительно, множество М = |л2| перечислимо, т.к. для получения его элементов нужно последователь­но брать натуральные числа и возводить их в квадрат. Более того, это множество является также и разреши­мым: для проверки того, принадлежит ли некоторое на­туральное число х множеству М, нужно разложить чис­ло на простые множители, и это даст возможность уста­новить, является ли оно точным квадратом.

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

(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),...

Теорема 3. Существует перечислимое, но неразрешимое множество натуральных чисел.

Для доказательства теоремы, как это следует из теоремы Поста, достаточно привести пример такого множества натуральных чисел U, которое само было бы перечислимым, а его дополнение CU перечислимым не было.

Пусть М₀, M₁ M₂,... - эффективное перечисление всех перечислимых множеств натуральных чисел, т.е. такое перечисление, что по любому n  N можно восста­новить само множество Мn.

Рассмотрим теперь алгоритм А, который последова­тельно перечисляет все элементы множества U. На шаге с номером (m, n) этот алгоритм вычисляет элемент с номером т множества Мn, и если этот элемент совпадает с n, то он относит его в множество U, т.е. n  U  n  Мn.

Отсюда ясно, что множество CU отличается от любо­го перечислимого множества хотя бы одним элементом, т.к. CU состоит из всех таких элементов n, что n  Мn. Поэтому CU не является перечислимым. Следовательно, согласно теореме Поста U не разрешимо.

Доказанная теорема фактически включает в себя в неявном виде теорему Гёделя о неполноте формальной арифметики, приведенную ранее без доказательства.