Разреши́мое мно́жество, множество конструктивных объектов какого-либо фиксированного типа, допускающее проверку принадлежности к нему его элементов при помощи алгоритма. Фактически мы можем ограничиться понятием разрешимого множества натуральных чисел, т. к. более общий случай может быть сведён к данному при помощи соответствующей нумерации рассматриваемых объектов. Множество $M$ натуральных чисел называется разрешимым, если существует такая общерекурсивная функция $f$, что $M=\{n \mid f(n)=0\}$. В этом случае $f$ и представляет собой алгоритм, проверяющий принадлежность к $M$ натуральных чисел. В самом деле, $n \in M$ равносильно тому, что $f(n)=0$. Разрешимое множество натуральных чисел часто называют также общерекурсивным, или рекурсивным, множеством.

Многие известные математические проблемы (такие, как проблема тождества, проблема гомеоморфии, 10-я проблема Гильберта, проблема разрешимости в математической логике) состоят в требовании доказать или опровергнуть утверждение о том, что некоторые конкретные множества суть разрешимые множества. Известные (отрицательные) решения перечисленных выше проблем состоят в установлении неразрешимости соответствующих им множеств (см. также Алгоритмическая проблема).