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