Пусть имеется некоторый алфавит. Обозначим через \(S\) множество всех слов в данном алфавите, а через \(M\) подмножество множества \(S\).
Множество \(M\) называется разрешимым, если для него существует алгоритм, решающий проблему вхождения слова \(x\) в \(M\).
Множество \(M\) называется эффективно перечислимым, если существует алгоритм, позволяющий перечислить все элементы этого множества (возможно с повторениями).
Теорема 1. Если множества \(M\) и \(L\) эффективно перечислимы, то эффективно перечислимы множества \(M \bigcup{} L\) и \(M \bigcap{} L\).
Доказательство. Пусть множества \(M\) и \(L\) эффективно перечислимы. Тогда для каждого из них существует свой алгоритм, позволяющий перечислить все элементы данного множества. Алгоритм для эффективного перечисления множеств \(M \bigcup{} L\) и \(M \bigcap{} L\) получается путём одновременного применения алгоритмов для эффективного перечисления множеств \(M\) и \(L\).
Теорема 2 (Поста). Множество \(M\) разрешимо тогда и только тогда, когда оно само и его дополнение эффективно перечислимы.
Доказательство. Путь множество \(M\) и его дополнение \(CM\) эффективно перечислимы, то есть существуют алгоритмы \(A\) и \(B\), с помощью которых можно перечислить элементы этих множеств. Но тогда при перечислении элементов множеств \(M\) и \(CM\) в их списке встретится элемент \(x\). Следовательно, существует алгоритм \(C\), позволяющий узнать, принадлежит элемент \(x\) множеству \(M\) или не принадлежит.
Пусть множество \(M\) разрешимо. Тогда существует алгоритм, решающий проблему вхождения \(x\) в \(M\). Пользуясь этим алгоритмом, составим список элементов, входящих в \(M\), и список элементов, входящих в \(CM\). Следовательно, мы получим два алгоритма \(A\) и \(B\), позволяющих перечислить множества \(M\) и \(CM\). Примерами эффективно перечислимых множеств являются:
1) множество \(M = \begin{Bmatrix} 1, 4, 9, ..., n^{2}, ... \end{Bmatrix}\) квадратов натуральных чисел;
2) множество упорядочных пар натуральных чисел.
Действительно, множество \(M = \begin{Bmatrix} n^{2} \end{Bmatrix}\) перечислимо, так как для получения его элементов нужно последовательно брать натуральные числа и возводить их в квадрат. Более того, это множество является также и разрешимым: для проверки того, принадлежит ли некоторое натуральное число \(x\) множеству \(M\), нужно разложить число на простые множители, и это даст возможность установить, является ли оно точным квадратом.
Множество упорядоченных пар натуральных чисел может быть эффективно перечислено с помощью так называемого диагональноrо метода. Действительно, выпишем все упорядоченные пары натуральных чисел в следующем виде:
Перечисление осуществляется последовательным прохождением по диагоналям, начиная с верхнего левого угла. Начальный список этих пар запишется так: $$(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_{0}, M_{1}, M_{2}, ...\) – эффективное перечисление всех перечислимых множеств натуральных чисел, то есть такое перечисление, что по любому \(n \epsilon N\) можно восстановить само множество \(M_{n}\).
Рассмотрим теперь алгоритм \(A\), который последовательно перечисляет все элементы множества \(U\). На шаге с номером \(m,n\) этот алгоритм вычисляет элемент с номером \(m\) множества \(M_{n}\), и если этот элемент совпадает с \(n\), то оно относит его в множество \(U\), то есть \(n \epsilon U \Leftrightarrow n \epsilon M _{n}\).
Отсюда ясно, что множество \(CU\) отличается от любого перечислимого множества хотя бы одним элементом, так как \(CU\) состоит из всех таких элементов \(n\), что \(n \not\epsilon M_{n}\). По-этому \(CU\) не является перечислимым. Следовательно, согласно теореме Поста \(U\) не разрешимо.
