Войти
В теории вычислимости, a набор из натуральных чисел называется рекурсивным, вычислимым или разрешимым, если существует алгоритм который принимает число в качестве входных данных, завершается через конечное количество времени (возможно, в зависимости от данного числа) и правильно определяет, принадлежит ли число к набору или нет.
Невычислимое множество называется невычислимым или неразрешимым .
. Более общий класс множеств, чем разрешимые, состоит из рекурсивно перечислимых множеств, также называемые полуразрешимыми множествами. Для этих наборов требуется только наличие алгоритма, который правильно определяет, когда число находится в наборе; алгоритм может не дать ответа (но не ошибиться) для чисел, не входящих в набор.
Подмножество S из натуральные числа называется рекурсивным, если существует total вычислимая функция f такая, что f (x) = 1, если x∈S и f (x) = 0, если x∉S. Другими словами, множество S является рекурсивным тогда и только тогда, когда индикаторная функция 1Sвычислима.
Примеры:
Непримеры:
Если A - рекурсивный набор, то дополнение к A является рекурсивным множеством. Если A и B - рекурсивные множества, то A ∩ B, A ∪ B и образ A × B при использовании функции спаривания Кантора являются рекурсивными множествами.
Набор A является рекурсивным набором тогда и только тогда, когда A и дополнение к A являются рекурсивно перечисляемыми наборами. прообраз рекурсивного набора под вычислимой функцией total является рекурсивным набором. Образ вычислимого множества при полной вычислимой биекции является вычислимым.
Набор рекурсивен тогда и только тогда, когда он находится на уровне Δ. 1арифметической иерархии .
Набор является рекурсивным тогда и только тогда, когда он является диапазоном неубывающего итогового вычислимого функция или пустой набор. Образ вычислимого множества при неубывающей общей вычислимой функции является вычислимым.
