к Оглавлению
4.1 Обоснуем, что всегда можно построить вышеописанный алгоритм «АнтиЭдип» - AntiOed_S() для произвольного алгориттма «Эдип» и аргументов sвида:
Oed(«Sph(…, …, …, …, …)», «-», t, S, s)
4.2. Все описанные в пункте 3 действия легко реализуются при помощи некого алгоритма-генератора в отношении такого алгоритма AntiOed_S(), программный код которого был бы передан для обработки в аргументе X. Тогда легко сгенерировать текст утверждение «AntiOed_S() = 0», другие соответствующие аргументы для запуска «Эдипа» и запустить сам «Эдип», а затем выдать свой результат после того, как «Эдип» выдаст свой (если «Эдип» остановится). Можно схематически (а можно и подробно – но это бездна рутины) написать программу для соответствующего алгоритма-генератора.
4.3. В соответствии с подразделом 5.2 «Теорема о построении алгоритма, применяемого к себе» мы можем из алгоритма-генератора предыдущего пункта сделать алгоритм, который все действия, которые алгоритм-генератор исполняет в отношении программного кода, получаемого в аргументе X – будет исполнять в отношении собственного программного кода. И, таким образом, мы описали метод (алгоритм) построения алгоритма AntiOed_S().
4.4. Если кто-то реально захочет строить AntiOed_S() в соответствии с методикой диагонализации, то пусть обратит внимание, что сначала надо построить алгоритм-генератор с одним аргуменом X. В этом алгоритме-генераторе потребуется задать в соответствующих переменных нужное S, программный код нужного «Эдипа» и программный код «Сфинкса». А уже в отношении этого алгоритма-генератора провести процедуру диагонализации относительно аргумента X. И нужный AntiOed_S() будет построен. Собственно, в названии алгоритма AntiOed_S() отражено и то, что он построен в отношении алгоритма «Эдип» и то, что работа данного «Эдипа» рассматривается тогда, когда числовая часть аргумента размера у него равна S.
4.5. Достаточно очевидно, что алгоритм «Эдип» с аргументами размера S, s не может доказать AntiOed_S() = 0? Если s корректный (s = s1(S)), то AntiOed_S() построен так, чтобы опровергнуть доказательство «Эдипа». Если же s не корректный, то базовый алгоритм проверки у задачи «Сфинкс» по построению должен возвращать 0 (Ноль) – о некорректности доказательства при подобном некорректном аргументе.
5. Перейдём к реализации плана, намеченного в пункте 1.2.
Нам надо, чтобы алгоритм проверки «Сфинкс» сообщал о произвольном алгоритме-решении «Эдип» то, что этот алгоритм «Эдип» (с аргументами размера S и s=s1(S)) не может доказать теорему о результате работы алгоритма «АтниЭдип» (построенным для заданного S). Разумеется, сообщать об алгоритме «Эдип» алгоритм «Сфинкс» будет в том случае, если переданный программный код – это программный код алгоритма, а не какая-то абракодабра.
5.1. Воспользуемся формулой из пункта 2.1 подраздела 6 «Задачи Кука и авторизуемые задачи из класса NP», добавив аргументы размера:
Sph(«Oed(«Sph(…, …, …, …, …)», «-», …, …, …)», t, S, s, y)
Как видим, алгоритм «Сфинкс» получает в первом аргументе программный код алгоритма «Эдип» (произвольного, вообще говоря).
5.2. Если же в аргументе долга вместо корректного алгоритма с подставленным аргументом долга «объективно» передана какая-то абракодабра, то работа Сфинкса сводится к работе базового алгоритма проверки (с аргументом долга «объективно»). И именно результат базовой проверки тогда «Сфинкс» и вернёт в качестве своего результата.
5.3. Если же значение аргумента долга является подходящим под шаблон формулы пункта 5.1, то «Сфинкс» генерирует текст теоремы про результат работы алгоритма «АнтиЭдип», разобранной в подпунктах пункта 3 данного раздела. Алгоритм генерации схематически изложен в пунктах 4 текущего раздела. При этом потребуется использовать значение аргумента S (но не аргумента s – что существенно).
5.4. Сгенерированный текст теоремы сравнивается с тем значением, которое передано в аргументе t. Если тексты не совпадают, то работа алгоритма «Сфинкс» снова сводится к базовому алгоритму проверки – как и в пункте 5.2.
Если же тексты совпадают, то «Сфинкс» возвращает 0 – независимо ни от значения аргумента s, ни от значения аргумента y.
Тут имеется занятный момент отличия от модели машины Тьюринга – в отношении переменной s: она практически никак не используется в работе по «персональной подсказке». И не должна тормозить работу по выдаче «персональной подсказки», а она и не тормозит даже при обращении к «Сфинксу» из «Эдипа», если аргумент s передаётся «по ссылке». В реальном мире программа именно так и будет построена. И, кстати, этот нюанс учтён в способе обращения к «Сфинксу»:
Sph(«Oed(«Sph(…, …, …, …, …)», «-», …, …, …)», t, S, s, y)
Как видим, в значение аргумента долга переменная s не «встроена» и поэтому не становится частью существенной для анализа информации. В некотором смысле аргумент s становится таким же, как и аргумент y здесь – ни на что не влияющим. Впрочем, даже в классических задачах из NP аргумент y не влияет на время работы алгоритма проверки – как только размер аргумента |y| превосходит некий полином от размера аргумента |x|.
Такой ответ «Сфинкса» будет совершенно правильным, потому что если значение аргумента s не соответствует значению аргумента S (если s ≠ s1(S)), то такое сочетание аргументов отвергается и нет никакого доказательства для y, которое могло бы это исправить. Если же аргументы S, s соответствуют друг другу, то «Эдип» не в состоянии найти никакого корректного доказательства для теоремы:
AntiOed_S() = 0
5.5. Разберём теперь время ответа «Сфинкса» при таком обращении к нему:
Sph(«Oed(«Sph(…, …, …, …, …)», «-», …, …, …)», «AntiOed_S() = 0», S, s, y) – при этом результат работы известен – 0 (Ноль).
Как видно из подпунктов пункта 4 данного раздела, генерация текста теоремы «AntiOed_S() = 0» и выдача результата 0 потребует от «Сфинкса» полиномиального количества шагов от вот чего: От размера аргумента долга |«Oed(«Sph(…, …, …, …, …)», «-», …, …, …)»|, от размера аргумента |S| (от количества десятичных цифр в десятичной записи S) и больше ни от чего. Размер теоремы не имеет значения – она же всё равно генерируется и сравнивается затем с тем, что передано в аргументе t.
Размер аргумента долга в данном случае полиномиально зависит от размеров программных текстов Sph(…, …, …, …, …) и Oed(…, …, …, …, …). Но они фиксированы для разбираемых нами подзадач (в отношении заданных «Сфинкса» и «Эдипа») общей задачи. И, таким образом, время работы «Сфинкса» в интересующем нас случае будет ограничено полиномом от размера |S|. То есть, время работы «Сфинкса» в интересующем нас случае не будет превышать некоторого v*|S|^u, где v, u – фиксированные числа.
5.6. Таким образом, мы выполнили план из пункта 1.2: «Сфинкс» выдаёт «персональную подсказку» про алгоритм «Эдип». «Персональная подсказка» - 0 (Ноль), то есть, корректный «Эдип» должен вернуть 0 (Ноль) – «Не могу найти доказательство для утверждения AntiOed_S() = 0».
Выдаётся «персональная подсказка» алгоритмом «Сфинкс» за время, полиномиальное относительно |S| (если зафиксировать размеры «Сфинкса» и «Эдипа»). В то же время «общий» ограничивающий алгоритм – полином относительно размера |s|.
Соотношение между |S| и |s| - как между линейной зависимостью и экспонентой. И, значит, любые полиномы на их базе будут неполиномиально сильно отличаться между собой – полином на базе |S| будет неполиномиально меньше полинома на базе |s|.
