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

множество конструктивных объектов какого-либо фиксированного типа, допускающее проверку принадлежности к нему его элементов при помощи алгоритма. Фактически мы можем ограничиться понятием Р. м. натуральных чисел, т. к. более общий случай может быть сведен к данному при помощи соответствующей нумерации рассматриваемых объектов. Множество Мнатуральных чисел наз. р а з р е ш и м ы м, если существует такая общерекурсивная функция f, что [img: http://localhost:8080/file/041865-38.jpg] В этом случае f и представляет собой алгоритм, проверяющий принадлежность к Мнатуральных чисел. В самом деле, [img: http://localhost:8080/file/041865-39.jpg] равносильно тому, что f(n)=0. Р. м. натуральных чисел часто наз. также о б щ е р е-к у р с и в н ы м, или р е к у р с и в н ы м, м н о ж ес т в о м. Многие известные математич. проблемы (такие, как проблема тождества, проблема гомеоморфии, 10-я проблема Гильберта, проблема разрешимости в математич. логике) состоят в требовании доказать или опровергнуть утверждение о том, что нек-рые конкретные множества суть Р. м. Известные (отрицательные) решения перечисленных выше проблем состоят в установлении неразрешимости соответствующих им множеств (см. также Алгоритмическая проблема).