Энциклопедия эпистемологии и философии науки

РАЗРЕШЕНИЯ ПРОБЛЕМА

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

  1. разрешения проблема—РАЗРЕШЕНИЯ ПРОБЛЕМА важное понятие логики. Р. п. данного множества А конструктивных объектов iотносительно некрого объемлющего множества V iконструктивных объектов наз. п...Большая советская энциклопедия
  2. разрешения проблема—важное понятие логики. Р. п. данного множества А emконструктивных объектов См. Конструктивные объекты относительно некоторого объемлющего множества V конструктивных объек...Большая Советская энциклопедия II
  3. разрешения проблема—алгоритмическая проблемаi в крой для заданного множества Атребуется построить алгоритм разрешающий Аотносительно другого множества Вi включающего т. е. такой алгоритм к...Математическая энциклопедия
  4. разрешения проблема—или Разрешимости пробленма аЧ проблема нахождения для данной дедуктивной теории общего метода позволяющего решать может ли отдельное утверждение сфорнмулированное в терми...Словарь логики
  5. разрешения проблема—РАЗРЕШЕНИЯ ПРОБЛЕМА или Разрешимости проблема проблема нахождения для данной дедуктивной теории общего метода позволяющего решать может ли отдельное утверждение сформули...Словарь по логике
  6. разрешения проблема—РАЗРЕШЕНИЯ ПРОБЛЕМА РАЗРЕШЕНИЯ ПРОБЛЕМА возникла в связи с осознанием невозможности провести некоторые построения дозволенными методами. Первыми примерами неразрешимых з...Философская энциклопедия
  7. разрешения проблема—один из наиболее важных видов массовых проблем. Р. п. данного множества А конструктивных объектов относительно некрого объемлющего множества V конструктивных объектов наз...Философская Энциклопедия (в 5 томах)
  8. разрешения проблема—одна из осн. проблем встающих в связи с построением формализованных дедуктивных теорий. Ее положительное или отрицательное решение для каждой конкретной формальной теории...Философский энциклопедический словарь