Алгоритмически неразрешимые проблемы.

Массовые проблемы, для которых не существует эффективных методов разрешения, называются алгоритмически неразрешимыми проблемами.

В интуитивном смысле массовая (алгоритмическая) проблема – это бесконечный класс родственных единичных конкретных проблем, правильный ответ для каждой из которых получается применением алгоритма.

Фактически произвольную массовую проблему можно сформулировать как проблему распознавания некоторого свойства Р элементов бесконечного множества М; при этом единичные проблемы. составляющие массовую проблему, связываются с элементами множества М, и каждая из них состоит в том, что требует узнать, обладает или нет свойством Р соответствующий элемент множества М. Поэтому задача ставится так: найти алгоритм, применимый к любому элементу множества М и для каждого данного хМ дает «1» или «0» в зависимости от того, обладает или нет элемент х свойством Р. Массовая проблема называется неразрешимой, если такого алгоритма нет.

Очевидно, принципиально неразрешимыми должны быть алгоритмы получения объектов, которые парадоксальны, или решения проблем, из которых вытекало бы (если бы они были разрешимы) существование объектов.

Понятие алгоритмической неразрешимости уточняется с привлечением математических понятий машины Тьюринга, рекурсивных функций, нормальных алгоритмов и других.

Известны два способа доказательства неразрешимости: прямой и косвенный, использующий сводимость к данной проблеме другой массовой проблеме, неразрешимость которой была доказана раньше.

Напоминание:

В настоящее время алгоритмические проблемы формируются как проблемы решения вопроса о существовании алгоритма для решения данной бесконечной серии однотипных задач и нахождения такого алгоритма в случае, если он существует.

Теоремы алгоритмически разрешимых и неразрешимых проблем. Теоремы Геделя.

1. Теорема о неполноте

Эта теорема Геделя обычно рассматривается как следующие два утверждения:

1. «В любой непротиворечивой формальной теории, содержащей формальную арифметику, найдется формально неразрешимое суждение, т.е. такая замкнутая формула А, что ни А, ни ┐А не являются выводимыми в этой теории».

2. «Для любой непротиворечивой формальной теории, содержащей формальную арифметику, формула А, выражающая непротиворечивость теории, недоказуема в теории».

2. Теорема о полноте

Эта теорема является утверждением о полноте классического И.П:

«Всякая предикатная формула, истинная во всех моделях выводима (по формальным правилам классического исчисления предикатов)».

Примечание:

1. Согласно теореме Геделя о неполноте арифметика и теория чисел оказываются неаксиоматизируемыми теориями (множество всех истинных высказываний арифметики не перечислимо). Это означает, что для достаточно богатых математических теорий не существует адекватных формализаций, а также невозможность исследования метасвойств теории средствами самой формальной теории.

2. Теорема Геделя о полноте утверждает перечислимость множества всех истинных высказываний логики предикатов.

3. Согласно теореме Черча классическое исчисление предикатов неразрешимо.

В этом плане, не смотря на полноту И.П. разрешающей процедуры, связанной

с вычислением значений истинности предикатных формул, построить не удается из-за бесконечности предметной области (это приводит в общем случае к бесконечным таблицам истинности).

4. Исчисление высказываний разрешимо и полно. Разрешающий алгоритм для всех формул F И.В. заключается в вычислении значений F на всех наборах значений её переменных. В виду полноты И.В. F является его теоремой, если и только если она истинна на всех своих наборах.