Энциклопедия эпистемологии и философии науки - разрешения проблема

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

Первый пример отрицательного решения Р. п. был получен в 1936 г. А. Чёрчем: логика предикатов первого порядка неразрешима, т.е. не существует алгоритма, который по произвольной формуле логики предикатов давал бы ответ, является ли эта формула тождественно истинной (общезначимой). С тех пор задача выяснения, является ли теория разрешимой, стала стандартным вопросом для всякой вновь формулируемой теории. Очень многие естественные теории оказались неразрешимыми, например аксиоматическая арифметика, элементарная теория групп. С другой стороны, имеются многочисленные весьма содержательные теории, которые разрешимы. Таковы, напр., арифметика Пресбургера (арифметика без умножения), теория действительных чисел и элементарная геометрия.

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

А.В. Чагров

Лит.: Чёрч А. Введение в математическую логику. М., I960; Ершов ЮЛ. Проблемы разрешимости и конструктивные модели. М., 1980; Справочная книга по математической логике. Ч. III. Теория рекурсии. М., 1982; Катленд Н. Вычислимость. Введение в теорию рекурсивных функций. М., 1983.

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

И.Т. Касавин

2009