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


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

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


Просмотров: 1322
Категория: Словари и энциклопедии » Философия » Философская энциклопедия





Другие новости по теме:

  • Важнейшие понятия христианского культа
  • ДЕЛЕНИЕ ОБЪЁМА ПОНЯТИЯ
  • ДЕОНТИЧЕСКИЕ ПОНЯТИЯ
  • КОНКРЕТНЫЕ И АБСТРАКТНЫЕ ПОНЯТИЯ
  • множество
  • МНОЖЕСТВО
  • НЕСОВМЕСТИМЫЕ ПОНЯТИЯ
  • НЕСРАВНИМЫЕ ПОНЯТИЯ
  • нечеткое множество
  • нормальное множество
  • объём понятия
  • ОБЪЕМ ПОНЯТИЯ
  • ограничение понятия
  • ОГРАНИЧЕНИЕ ТРЕТЬЕГО ПОНЯТИЯ
  • ОСНОВНЫЕ ПОНЯТИЯ
  • ПЕРЕКРЕЩИВАЮЩИЕСЯ ПОНЯТИЯ
  • ПОГРАНИЧНЫЕ ПОНЯТИЯ
  • ПОНЯТИЯ ОБЪЕМ
  • ПОНЯТИЯ ОСНОВНЫЕ
  • ПОНЯТИЯ РАССУДОЧНЫЕ
  • ПОНЯТИЯ СОДЕРЖАНИЕ
  • ПОНЯТИЯ ФОРМЫ
  • РАВНОЗНАЧНЫЕ ПОНЯТИЯ
  • разрешения проблема (разрешимости проблема)
  • РАЗУМА ПОНЯТИЯ
  • СОБИРАТЕЛЬНЫЕ ПОНЯТИЯ
  • содержание понятия
  • содержание понятия
  • ЧИСТЫЕ ПОНЯТИЯ РАССУДКА
  • ЭЛЕМЕНТАРНЫЕ ПОНЯТИЯ



  • ---
    Разместите, пожалуйста, ссылку на эту страницу на своём веб-сайте:

    Код для вставки на сайт или в блог:       
    Код для вставки в форум (BBCode):       
    Прямая ссылка на эту публикацию:       






    Данный материал НЕ НАРУШАЕТ авторские права никаких физических или юридических лиц.
    Если это не так - свяжитесь с администрацией сайта.
    Материал будет немедленно удален.
    Электронная версия этой публикации предоставляется только в ознакомительных целях.
    Для дальнейшего её использования Вам необходимо будет
    приобрести бумажный (электронный, аудио) вариант у правообладателей.

    На сайте «Глубинная психология: учения и методики» представлены статьи, направления, методики по психологии, психоанализу, психотерапии, психодиагностике, судьбоанализу, психологическому консультированию; игры и упражнения для тренингов; биографии великих людей; притчи и сказки; пословицы и поговорки; а также словари и энциклопедии по психологии, медицине, философии, социологии, религии, педагогике. Все книги (аудиокниги), находящиеся на нашем сайте, Вы можете скачать бесплатно без всяких платных смс и даже без регистрации. Все словарные статьи и труды великих авторов можно читать онлайн.







    Locations of visitors to this page



          <НА ГЛАВНУЮ>      Обратная связь