Разрешимое множество

---

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

Более общее определение таково: множество разрешимо, если существует алгоритм, который по любому объекту даёт ответ на вопрос, принадлежит он данному множеству или нет. Таким образом, разрешимое множество — это множество с алгоритмически разрешимой проблемой вхождения.

Множество является разрешимым, если и только если его характеристическая функция вычислима. Согласно тезису Чёрча, вычислимость характеристической функции означает её частичную рекурсивность. А значит, и её вычислимость по Тьюрингу. Поэтому разрешимое множество называют также частично рекурсивным (или рекурсивным) множеством.

Также можно говорить о разрешимом множестве, состоящем из любых конструктивных объектов, кодируемых натуральными числами. Любое разрешимое множество является перечислимым и арифметическим. Разрешимые множества соответствуют уровню ${\displaystyle \Delta _{1}^{0}}$ арифметической иерархии^[en].

В общем случае, подмножество ${\displaystyle {\mathfrak {M}}_{1}}$ множества ${\displaystyle {\mathfrak {M}}_{2}}$ конструктивных элементов называется разрешимым относительно ${\displaystyle {\mathfrak {M}}_{2}}$, если существует алгоритм, применимый к объектам из ${\displaystyle {\mathfrak {M}}_{2}}$ и в случае применения к некоторому объекту ${\displaystyle {\mathfrak {M}}_{2}}$ дающий ответ на вопрос, принадлежит ли этот объект ${\displaystyle {\mathfrak {M}}_{1}}$^[1].

---