dmitgu (dmitgu) wrote,
dmitgu
dmitgu

Category:

4. Предварительное замечание о программе Гильберта для теории алгоритмов.

к Оглавлению


То, что алгоритм-решение M(x) (см. раздел 1 «Задачи из классов NP и P, NP+ и P+») ищет «доказательство» y для «теоремы» x на основе полученной информации об x и о массовой задаче L(x, y) – тоже ведь должно быть формализовано при реализации программы Гильберта и рассмотрено с точки зрения логики – то есть, в некоторой теории.

На самом деле, алгоритм-решение должен получать текст программы алгоритма проверки и быть вида:

ML(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».


Tags: NP≠P дискуссии, ЖЖвЖЖ математика
Subscribe

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 0 comments