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

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

Другими словами, X разрешимо, если его характеристическая функцияχ(n) = (if n ∈ X then 1 else 0 fi) вычислима.

Очевидно, пересечение, объединение и разность разрешимых множеств разрешимы. Любое конечное множество разрешимо.

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

Такой алгоритм не имеет входа; напечатав несколько чисел, он может надолго задуматься и следующее число напечатать после большого перерыва (а может вообще больше никогда ничего не напечатать тогда множество будет конечным).

Существует много эквивалентных определений перечислимого множества. Вот некоторые из них:

• Множество перечислимо, если оно есть область определения вычислимой функции.

• Множество перечислимо, если оно есть область значений вычислимой функции.

• Множество X перечислимо, если его (как иногда говорят) " полухарактеристическая " функция, равная 0 на элементах X и не определенная вне X, вычислима.

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

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

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

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

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

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

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

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

Напротив, если P перечислимое множество, перечисляемое алгоритмом A, то оно есть проекция разрешимого множества Q, состоящего из всех таких пар   , что xпоявляется в течении первых n шагов работы алгоритма A. (Это свойство, очевидно, разрешимо.)