Эффективная перечислимость и распознаваемость множеств
Определения
Эффективно перечислимым множеством называется множество, элементы которого можно перечислить по алгоритму (пронумеровать натуральным рядом без пропусков и повторений). Подмножество В множества А эффективно распознается в А, если существует алгоритм, позволяющий однозначно для каждого элемента множества А определить, принадлежит ли данный элемент множеству В или дополнению В до А. Теорема Поста Если множество А эффективно перечислимо, то подмножество В эффективно распознается в А тогда и только тогда, когда В и А\В оба эффективно перечислимы. Доказательство: необходимость Пусть В распознается в А. Множество А представляет собой набор элементов А={a1,a2,…}. Вытаскиваем ∀ элемент ai из множества A. Если ai∈B, то нумеруем его в B, Если ai∉B, то нумеруем его в А\B. Т.к. A эффективно перечислимо, то таким образом будут вытащены все его элементы. Таким образом эффективно перечислены множества B и А\B.
