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


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

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


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





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

  • АЛГОРИТМ
  • алгоритм
  • АЛГОРИТМ
  • Алгоритм
  • алгоритм
  • ГОЛОС И ФЕНОМЕН: ВВЕДЕНИЕ В ПРОБЛЕМУ ЗНАКОВ В ФЕНОМЕНОЛОГИИ ГУССЕРЛЯ
  • ДЕМАРКАЦИИ ПРОБЛЕМА
  • демаркации проблема
  • ЕВРОПЕЙСКАЯ ФИЛОСОФИЯ ведет начало с греков, которые не только овладели с помощью уже существовавшего до них мышления новыми предметами
  • ЗАДАЧА (проблема)
  • История как проблема логики
  • ЛОЖНАЯ ПРОБЛЕМА
  • МАССОВАЯ ПРОБЛЕМА
  • Пороговая Проблема
  • ПРОБЛЕМА
  • ПРОБЛЕМА
  • Проблема
  • проблема
  • ПРОБЛЕМА
  • проблема
  • психодиагностическая проблема
  • психофизическая проблема
  • ПСИХОФИЗИЧЕСКАЯ ПРОБЛЕМА
  • РАЗРЕШЕНИЯ ПРОБЛЕМА
  • Разрешения Проблема
  • разрешения проблема (разрешимости проблема)
  • РАЗРЕШЕНИЯ ПРОБЛЕМЫ
  • ТРИЕДИНСТВА ПРОБЛЕМА
  • ЭКОЛОГИЧЕСКАЯ ПРОБЛЕМА
  • Является ли знанием истинное и обоснованное мнение?



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

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






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

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







    Locations of visitors to this page



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