к Оглавлению
То, что алгоритм-решение M(x) (см. раздел 1 «Задачи из классов NP и P, NP+ и P+») ищет «доказательство» y для «теоремы» x на основе полученной информации об x и о массовой задаче L(x, y) – тоже ведь должно быть формализовано при реализации программы Гильберта и рассмотрено с точки зрения логики – то есть, в некоторой теории.
На самом деле, алгоритм-решение должен получать текст программы алгоритма проверки и быть вида:
M(«L(x, y)», x).
Где «L(x, y)» обозначает текст программы алгоритма проверки (на каком-то языке программирования), а не сам алгоритм. Именно такое обозначение для текста программ мы будем использовать и в дальнейшем.
Но немного отложим уточнение, что имеется аргумент, содержащий текст программы алгоритма проверки. Будем пока считать, что алгоритм проверки зафиксирован и не меняется, поэтому не представлен как аргумент у M(x).
В качестве аналога возьмём эпоху логических открытий, когда стоял вопрос о полноте теории Пеано и о возможности найти в ней доказательство для любого утверждения или его отрицания про натуральные числа. И тогда само доказательство стало объектом рассмотрения – и уже теоремы о доказательствах выявили неполноту теорий.
Теперь же мы рассматриваем возможность алгоритмов-решений полиномиально быстро (относительно размера некоторых своих аргументов) находить решения для задач L(x, y) из класса NP. А искомый нами алгоритм M(x) за конечное время определяет, имеется ли такое y, что L(x, y) = 1.
Метод Гильберта состоял в применении математического формализма теории к теории. Метод данного исследования состоит в применении алгоритма-проверки к алгоритму-решению. А алгоритм проверки построен на базе теории, способной представлять утверждения про алгоритмы - включая заданный алгоритм-решение. Притом «специальный вопрос» (и соответствующая задача) «сопротивляется» заданному алгоритму-решению в его поиске ответа. Этот приём «изучаемый объект поступает вопреки прогнозам наблюдателя» удачно использовал Гёдель, и мы тоже воспользуемся им.
И, применяя выбранный алгоритм-решение к подобной теории (точнее, к соответствующему алгоритму-проверке), мы выясним, что алгоритм-решение не может найти «специальный» ответ про неё. И эта невозможность известна сразу, то есть - полиномиально быстро.
И у нас есть одна из таких задач, способных представлять алгоритмы и логические утверждения о них – это проверка доказательств в теории Пеано и в расширенной теории Пеано. Ведь теория Пеано может выразить любой алгоритм-решение. Так нет ли тут возможности поставить перед алгоритмом-решением (любым) непреодолимые для него задачи? И показать невозможность для алгоритма-решения M(x) (любого) всегда давать правильные ответы про задачу из класса NP.
Невозможность дать правильный ответ проявится вот как: Некое утверждение x имеет соответствующее доказательство y при правильном своём ответе M(x) = z (именно z, который не обязательно равен y) и при данных x , y будет L(x, y) = 1, но при этом корректный алгоритм-решение M(x) не может найти данный y, а возвращает отличный от него результат z, при котором L(x, z) = 0. Сочетание «корректности» работы M(x) = z с тем, что L(x, z) = 0, когда имеется y, при котором L(x, y) = 1 кажется невозможным, но мы увидим обратное – алгоритм вернёт результат «не могу найти доказательство» и он действительно не может – поэтому ответ корректный. Но и подходящее для нашей задачи доказательство будет существовать – поэтому ответ алгоритма – неполный (алгоритм не сможет найти существующий ответ).
Приведённые в предыдущем абзаце «чудеса» станут возможны после разделения «теоремы» х на несколько частей – с появлением дополнительных параметров для рассмотрения. И тогда появится возможность учесть одну хорошо известную нам в обычной жизни зависимость, которая никак не была формализована в математике ранее. К этому вопросу мы вскоре вернемся – в разделе 6 «Задачи Кука и авторизуемые задачи из класса NP».
