ПЕРЕЧИСЛИМОЕ МНОЖЕСТВО, рекурсивно-перечислимое множество, множество натуральных чисел или к.-л. других конструктивных объектов, занумерованных натуральными числами, являющееся множеством значений нек-рой общерекурсивной функции. См. Рекурсивные функции.
- множество, возникающее в результате развертывания какого-либо конструктивного порождающего процесса. Такой процесс можно мыслить как процесс вычисления значений нек-рого алгоритма с исходными данными в виде натуральных чисел, и потому, напр., определению П. м. натуральных чисел можно придать следую. частично рекурсивная функция, что это множество является множеством ее значений.
Всякое разрешимое множество натуральных чисел является П. м. Обратное неверно: можно указать пример неразрешимого П. м. Этот факт, установленный в 1936 А. Чёрчем (A. Church), является одним из фундаментальных результатов общей алгоритмов теории. На нем основаны (или могут быть основаны) все известные отрицательные решения алгоритмических проблем. Если какое-либо множество и его дополнение суть П. м., то это множество разрешимо (теорема Поста). Изучение и классификация П. м. являются предметом исследований алгоритмич. теории множеств.
Лит.:[1] Успенский В. А., Лекции о вычислимых функциях, М., 1960. Н. М. Нагорный.