Философская энциклопедия - разрешимое и перечислимое множества

РАЗРЕШИМОЕ И ПЕРЕЧИСЛИМОЕ МНО́ЖЕСТВА

осн. понятия теории алгоритмов и теории рекурсивных функций (и предикатов). (Определение этих понятий на основе понятия алгоритма см. в ст. Алгоритм, раздел Основные понятия теории А.)

Простейшим примером разрешимого множества может служить множество всех формул к.-л. исчисления (относительно множества всех конечных последовательностей символов алфавита этого исчисления), а примером перечислимого множества – множество теорем (доказуемых формул) исчисления. (В случае разрешимости этого второго множества говорят, что имеет место разрешимость самого исчисления.)

Независимо от понятия алгоритма понятия Р. и п. м. (натуральных чисел) можно также определить в терминах вычислимых (или "рекурсивных") функций: (1) Множество натуральных чисел наз. разрешимым, или, как чаще говорят, (обще-) рекурсивным, если существует обще-рекурсивная функция, принимающая к.-л. фиксиров. значение (напр., 1) на элементах этого множества и к.-л. другое фиксиров. значение (напр., 0) на натуральных числах, не принадлежащих этому множеству (р а з р е ш а ю щ а я ф у н к ц и я). (2) Множество натуральных чисел наз. (рекурсивно-) перечислимым, если существует обще-рекурсивная функция, множеством значений к-рой является это множество (п е р е ч и с л я ю щ а я ф у н к ц и я). Понятия Р. и п. м. связаны и с понятием обще-рекурсивного предиката, причем их определения допускают соответствующие естеств. переформулировки. Напр., для обще-рекурсивного множества С предикат x∈С обще-рекурсивен (и, конечно, обратно). Понятия Р. и п. м. могут быть выбраны и в качестве исходных уточнений интуитивных представлений об "эффективной разрешимости" и "эффективной определимости" св-в (предикатов) конструктивных объектов, на основе к-рых затем уже можно определить понятия алгоритма и вычислимой (обще-рекурсивной) функции, не впадая в порочный круг. Проблема нахождения разрешающего алгоритма для данного множества конструктивных объектов (напр., формул определенного вида из к.-л. исчисления) наз. его разрешения проблемой.

См. также Рекурсивные функции и предикаты, Массовая проблема.

Философская Энциклопедия. В 5-х т. — М.: Советская энциклопедия. Под редакцией Ф. В. Константинова. 1960—1970.