разрешения проблема


разрешения проблема
        РАЗРЕШЕНИЯ ПРОБЛЕМА — задача поиска алгоритма, решающего массовую проблему, состоящую из однотипных вопросов о конструктивных объектах (словах над фиксированным конечным алфавитом), ответы на которые даются с помощью некоторого алгоритма; этот алгоритм является решением данной Р. п. и называется для данной проблемы разрешающим алгоритмом, или алгоритмом, решающим данную проблему. Примеры: построение таблицы истинности для пропозициональной формулы и проверка главного столбца на отсутствие значения «ложь» есть алгоритм, решающий Р. п. классической логики высказываний; множество простых натуральных чисел (числа записываются, напр., в десятичной системе счисления; число называется простым, если это натуральное число, больше или равное 2, имеющее только два натуральных делителя — самое себя и 1) и соответствующая проблема выяснения простоты натурального числа разрешима с помощью алгоритма перебора возможных делителей. Близкой является проблема разрешимости, отличающаяся от Р. п. тем, что требуется лишь обосновать существование алгоритма, решающего данную проблему. В большинстве случаев положительное решение проблемы разрешимости достигается предъявлением соответствующего алгоритма, т.е. на самом деле решается и Р. п., а отрицательное решение (обоснование отсутствия требуемого алгоритма) является таковым для обоих видов проблем. Бывают случаи, когда проблема разрешимости положительно решена для некоторой задачи, в то время как соответствующая Р. п. остается открытой.
        Первый пример отрицательного решения Р. п. был получен в 1936 г. А. Чёрчем: логика предикатов первого порядка неразрешима, т.е. не существует алгоритма, который по произвольной формуле логики предикатов давал бы ответ, является ли эта формула тождественно истинной (общезначимой). С тех пор задача выяснения, является ли теория разрешимой, стала стандартным вопросом для всякой вновь формулируемой теории. Очень многие естественные теории оказались неразрешимыми, например аксиоматическая арифметика, элементарная теория групп. С другой стороны, имеются многочисленные весьма содержательные теории, которые разрешимы. Таковы, напр., арифметика Пресбургера (арифметика без умножения), теория действительных чисел и элементарная геометрия.
        В последние десятилетия в связи с приложениями к проблемам, имеющим практическое значение, к Р. п. относят и вопросы оптимизации найденных алгоритмов, т.е. требуется не только предоставить разрешающий алгоритм, но и обосновать, что этот алгоритм имеет наименьшую возможную сложность вычисления в том или ином смысле (по затратам времени, памяти и т.п.). С точки зрения этой подпроблемы Р. п. многие теории (или множества конструктивных объектов), для которых Р. п. были положительно решены, оказались практически неразрешимыми или, по крайней мере, найденные алгоритмы не годятся для практического применения. Хрестоматийными примерами являются проблемы выяснения тождественной истинности и выполнимости формул логики высказываний: алгоритм, состоящий в построении таблицы истинности для проверяемой формулы, принципиально дает решение обеих проблем, однако он практически не применим, поскольку требует для своей реализации экспоненциально растущих затрат времени в зависимости от числа переменных в проверяемых формулах.
        А.В. Чагров
        Лит.: Чёрч А. Введение в математическую логику. М., I960; Ершов ЮЛ. Проблемы разрешимости и конструктивные модели. М., 1980; Справочная книга по математической логике. Ч. III. Теория рекурсии. М., 1982; Катленд Н. Вычислимость. Введение в теорию рекурсивных функций. М., 1983.

Энциклопедия эпистемологии и философии науки. М.: «Канон+», РООИ «Реабилитация». . 2009.


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





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

  • “НОВЫЙ ОРГАНОН, ИЛИ ИСТИННЫЕ УКАЗАНИЯ ДЛЯ ИСТОЛКОВАНИЯ ПРИРОДЫ”
  • “О НЕОБХОДИМОСТИ И ВОЗМОЖНОСТИ НОВЫХ НАЧАЛ ДЛЯ ФИЛОСОФИИ”
  • “ФИЛОСОФИЯ ДЛЯ ДЕТЕЙ”
  • «ИСКУССТВО ДЛЯ ИСКУССТВА»
  • «НОВЫЙ ОРГАНОН, ИЛИ ИСТИННЫЕ УКАЗАНИЯ ДЛЯ ИСТОЛКОВАНИЯ ПРИРОДЫ»
  • Город для колесниц
  • ДЛЯ-МЕНЯ-БЫТИЕ
  • ДЛЯ-СЕБЯ-БЫТИЕ
  • Дорога для Рамы
  • жертвенник для курений
  • Загон для овец, овечий хлев
  • ЗАДАЧА (проблема)
  • История как проблема логики
  • Квота для женщин
  • КЛАСС «В СЕБЕ» И КЛАСС «ДЛЯ СЕБЯ»
  • Кондаков И.М. Методика Для Изучения
  • Конференция Для Священнослужителей Разных Вероисповеданий
  • Кувшин Для Умывания
  • НОВЫЙ ОРГАНОН, ИЛИ ИСТИННЫЕ УКАЗАНИЯ ДЛЯ ИСТОЛКОВАНИЯ ПРИРОДЫ
  • Новый органон, или Истинные указания для истолкования природы
  • Опросник Для Диагностики Устойчивых Форм
  • Письменные экзамены для аспирантов (graduate record examination (GREs))
  • РАЗРЕШЕНИЯ ПРОБЛЕМА
  • Разрешения Проблема
  • разрешения проблема (разрешимости проблема)
  • Расстройство эмоций, специфическое для детского и подросткового возраста
  • Такие подростки, как правило, зависимы от своих родителей и для них характерны социальная и психологическая незрелость и социальная изоляция.
  • Тесты для отбора кандидатов (selection tests)
  • ФИЛОСОФИЯ ДЛЯ ДЕТЕЙ
  • ЧЕЛОВЕК ДЛЯ СЕБЯ. ИССЛЕДОВАНИЕ ПСИХОЛОГИЧЕСКИХ ПРОБЛЕМ ЭТИКИ



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

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






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

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







    Locations of visitors to this page



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