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

Множество конструктивных объектов какого-либо фиксированного типа, допускающее проверку принадлежности к нему его элементов при помощи алгоритма. Фактически мы можем ограничиться понятием Р. м. натуральных чисел, т. к. более общий случай может быть сведен к данному при помощи соответствующей нумерации рассматриваемых объектов. Множество Мнатуральных чисел наз. р а з р е ш и м ы м, если существует такая общерекурсивная функция f, что В этом случае f и представляет собой алгоритм, проверяющий принадлежность к Мнатуральных чисел. В самом деле, равносильно тому, что f(n)=0. Р. м. натуральных чисел часто наз. также о б щ е р е-к у р с и в н ы м, или р е к у р с и в н ы м, м н о ж ес т в о м. Многие известные математич. проблемы (такие, как проблема тождества, проблема гомеоморфии, 10-я проблема Гильберта, проблема разрешимости в математич. логике) состоят в требовании доказать или опровергнуть утверждение о том, что нек-рые конкретные множества суть Р. м. Известные (отрицательные) решения перечисленных выше проблем состоят в установлении неразрешимости соответствующих им множеств (см. также Алгоритмическая проблема). Лит.:[1] У с п е н с к и й В. А., Лекции о вычислимых функциях, М., 1960. Н. М. Нагорный.