Перечислимое множество

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