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

РАЗРЕШИМОЕ И ПЕРЕЧИСЛИМОЕ МНОЖЕСТВА
РАЗРЕШИМОЕ И ПЕРЕЧИСЛИМОЕ МНО́ЖЕСТВА
осн. понятия теории алгоритмов и теории рекурсивных функций (и предикатов). (Определение этих понятий на основе понятия алгоритма см. в ст. Алгоритм, раздел Основные понятия теории А.)
Простейшим примером разрешимого множества может служить множество всех формул к.-л. исчисления (относительно множества всех конечных последовательностей символов алфавита этого исчисления), а примером перечислимого множества – множество теорем (доказуемых формул) исчисления. (В случае разрешимости этого второго множества говорят, что имеет место разрешимость самого исчисления.)
Независимо от понятия алгоритма понятия Р. и п. м. (натуральных чисел) можно также определить в терминах вычислимых (или "рекурсивных") функций: (1) Множество натуральных чисел наз. разрешимым, или, как чаще говорят, (обще-) рекурсивным, если существует обще-рекурсивная функция, принимающая к.-л. фиксиров. значение (напр., 1) на элементах этого множества и к.-л. другое фиксиров. значение (напр., 0) на натуральных числах, не принадлежащих этому множеству (р а з р е ш а ю щ а я ф у н к ц и я). (2) Множество натуральных чисел наз. (рекурсивно-) перечислимым, если существует обще-рекурсивная функция, множеством значений к-рой является это множество (п е р е ч и с л я ю щ а я ф у н к ц и я). Понятия Р. и п. м. связаны и с понятием обще-рекурсивного предиката, причем их определения допускают соответствующие естеств. переформулировки. Напр., для обще-рекурсивного множества С предикат x∈С обще-рекурсивен (и, конечно, обратно). Понятия Р. и п. м. могут быть выбраны и в качестве исходных уточнений интуитивных представлений об "эффективной разрешимости" и "эффективной определимости" св-в (предикатов) конструктивных объектов, на основе к-рых затем уже можно определить понятия алгоритма и вычислимой (обще-рекурсивной) функции, не впадая в порочный круг. Проблема нахождения разрешающего алгоритма для данного множества конструктивных объектов (напр., формул определенного вида из к.-л. исчисления) наз. его разрешения проблемой.
См. также Рекурсивные функции и предикаты, Массовая проблема.

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


.

Игры ⚽ Нужно сделать НИР?

Полезное


Смотреть что такое "РАЗРЕШИМОЕ И ПЕРЕЧИСЛИМОЕ МНОЖЕСТВА" в других словарях:

  • Перечислимое множество — Не следует путать с счётным множеством. В теории множеств, теории алгоритмов и математической логике, перечислимое множество (эффективно перечислимое, рекурсивно перечислимое, полуразрешимое множество[1])  множество конструктивных объектов… …   Википедия

  • Разрешимое множество — В теории множеств, теории алгоритмов и математической логике, множество натуральных чисел называется разрешимым или рекурсивным, если существует алгоритм, который, получив на вход любое натуральное число, через конечное число шагов завершается и… …   Википедия

  • СКОЛЕМ — (Skolem), Торальф Альберт (р. 23 мая 1887) – норв. логик, математик, философ; кандидат философии (1913), д р философии (1926), доцент ун та в Осло (1918–30), научный сотрудник Ин та науки и свободомыслия (ин т Кристиана Микельсена, 1930–38), проф …   Философская энциклопедия

  • ОПРЕДЕЛЕНИЕ — дефиниция (лат. defenitio ограничение) логическая операция, раскрывающая содержание понятия. Напр., обычное определение термометра указывает, что это, во первых, прибор и, во вторых, именно тот, с помощью которого измеряется температура. Важность …   Философская энциклопедия

  • ФОРМАЛЬНАЯ ЛОГИКА — наука, занимающаяся анализом структуры высказываний и доказательств, обращающая основное внимание на форму в отвлечении от содержания. Определение «формальная» было введено И. Кантом с намерением подчеркнуть ведущую особенность Ф.л. в подходе к… …   Философская энциклопедия

  • ТЕРМ —         (англ. term, франц. terme, от лат. terminus граница, предел, позднее выражение, определение), в логико математич. исчислении аналог подлежащего или дополнения естеств. языков, т. е. выражение, обозначающее (или описывающее см. Дескрипция) …   Философская энциклопедия

  • РЕКУРСИВНЫЕ ФУНКЦИИ И ПРЕДИКАТЫ — один из важнейших для оснований математики и математич. логики классов понятий, служащих уточнениями содержат. понятий эффективно вычислимой арифметической функции и эффективно разрешимого арифметического предиката, а в конечном счете, – и… …   Философская энциклопедия

  • АЛГОРИТМ —         [от algorithm!; algorismus, первоначально лат. транслитерация имени ср. азиат. учёного 9 в. Хорезми (Мухаммед бен Муса аль Хорезми)], программа, определяющая способ поведения (вычисления); система правил (предписаний) для эффективного… …   Философская энциклопедия

  • Алгоритмов теория —         раздел математики, изучающий общие свойства Алгоритмов. Содержательные явления, приведшие к образованию понятия «алгоритм», прослеживаются в математике в течение всего времени её существования. Однако само это понятие сформировалось лишь… …   Большая советская энциклопедия

  • Арифметическое множество — В теории множеств и математической логике, множество натуральных чисел называется арифметическим, если оно может быть определено формулой в языке арифметики первого порядка, то есть если существует такая формула с одной свободной переменной что… …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
… Нажмите правой клавишей мыши и выберите «Копировать ссылку»