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