Введение
В теории вычислимости множество натуральных чисел называется вычислимым, рекурсивным или разрешимым, если существует алгоритм, который принимает число на вход, завершается за конечное время (возможно, зависящее от данного числа) и корректно определяет, принадлежит ли число этому множеству или нет. Множество, которое не является вычислимым, называется невычислимым или неразрешимым. Более общий класс множеств, чем вычислимые, составляют вычислимо перечислимые (в. п.) множества, также называемые полуразрешимыми множествами. Для этих множеств требуется лишь наличие алгоритма, который корректно определяет, когда число принадлежит множеству; алгоритм может не давать ответа (но не неверного ответа) для чисел, не входящих в множество.
In computability theory, a set of natural numbers is called computable, recursive, or decidable if there is an algorithm which takes a number as input, terminates after a finite amount of time (possibly depending on the given number) and correctly decides whether the number belongs to the set or not. A set which is not computable is called noncomputable or undecidable. A more general class of sets than the computable ones consists of the computably enumerable (c. e.) sets, also called semidecidable sets. For these sets, it is only required that there is an algorithm that correctly decides when a number is in the set; the algorithm may give no answer (but not the wrong answer) for numbers not in the set.
Формальное определение
Подмножество натуральных чисел называется вычислимым, если существует тотальная вычислимая функция такая, что если и если . Иными словами, множество вычислимо тогда и только тогда, когда вычислима его функция-индикатор.
Свойства
Если A – вычислимое множество, то дополнение к A – вычислимое множество. Если A и B – вычислимые множества, то A ∩ B, A ∪ B и образ A × B под функцией Кэнтора – вычислимые множества. Множество A является вычислимым тогда и только тогда, когда A и дополнение к A оба вычислимо перечислимы (c. e.). Предобраз вычислимого множества под тотальной вычислимой функцией является вычислимым множеством. Образ вычислимого множества под тотальной вычислимой биекцией является вычислимым. (В общем случае, образ вычислимого множества под вычислимой функцией является вычислимо перечислимым (c. e.), но не обязательно вычислимым). Множество A является вычислимым тогда и только тогда, когда оно находится на уровне арифметической иерархии. Множество A является вычислимым тогда и только тогда, когда оно является либо областью не убывающей тотальной вычислимой функции, либо пустым множеством. Образ вычислимого множества под не убывающей тотальной вычислимой функцией является вычислимым.