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

в логике, множество, расположенное в некоторой совокупности конструктивных объектов (См. Конструктивные объекты) (т. е. множество, составленное из каких-то объектов этой совокупности), для которого существует Алгоритм, разрешающий это множество (относительно объемлющей совокупности) в следующем смысле: алгоритм применим к любому объекту объемлющей совокупности и даёт в качестве результата ответ на вопрос, принадлежит ли этот объект к рассматриваемому множеству или нет.

мат. decidable set

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

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

Лит.:[1] У с п е н с к и й В. А., Лекции о вычислимых функциях, М., 1960. Н. М. Нагорный.