В теории вычислимости, А набор из натуральных чисел называются вычислимым, рекурсивным или разрешимым, если существует алгоритм, который принимает число в качестве входных данных, завершается после конечного количества времени (возможно, в зависимости от заданного числа) и правильно решает, является ли число принадлежит набору или нет.
Невычислимое множество называется невычислимым или неразрешимым.
Более общий класс множеств, чем вычислимые, состоит из вычислимо перечислимых (с.п.) множеств, также называемых полуразрешимыми множествами. Для этих наборов требуется только наличие алгоритма, который правильно определяет, когда число находится в наборе; алгоритм может не дать ответа (но не неправильного ответа) для чисел, не входящих в набор.
Подмножество из натуральных чисел называется вычислимой, если существует общая вычислимую функцию таким образом, что, если и, если. Другими словами, множество вычислим тогда и только тогда, когда индикаторная функция является вычислимой.
Примеры:
Не примеры:
Основная статья: Список неразрешимых проблемЕсли A - вычислимое множество, то дополнение к A - вычислимое множество. Если A и B вычислимые множества, то A ∩ B, A ∪ B и образ A × B при использовании функции спаривания Кантора являются вычислимыми множествами.
Вычислимое множество тогда и только тогда, когда А и дополнение в А оба с. Прообраз вычислимого множества при полной вычислимой функции является вычисляемым множеством. Образ вычислимого множества при полной вычислимой биекции вычислим. (В общем, образ вычислимого множества при вычислимой функции - это ce, но, возможно, не вычислимый).
А представляет собой множество вычислимы тогда и только тогда, когда он находится на уровне от арифметической иерархии.
A является вычислимым множеством тогда и только тогда, когда оно является либо диапазоном неубывающей общей вычислимой функции, либо пустым множеством. Образ вычислимого множества при неубывающей общей вычислимой функции является вычислимым.