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

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

enumerable set

- множество, возникающее в результате развертывания какого-либо конструктивного порождающего процесса. Такой процесс можно мыслить как процесс вычисления значений нек-рого алгоритма с исходными данными в виде натуральных чисел, и потому, напр., определению П. м. натуральных чисел можно придать следую. <щий точный вид: множество натуральных чисел наз. перечислимым, если существует такая частично рекурсивная функция, что это множество является множеством ее значений.

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

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

перерахо́вна множина́

перерахо́вна множина́