dmitgu (dmitgu) wrote,
dmitgu
dmitgu

Category:

5.1. Лемма о диагонализации

к Оглавлению

Диагонализация. Это понятие возникло заметно позже Гильберта, но позволяет более лаконично излагать доказательства многих теорем о неполноте и неразрешимости. В частности – теорем Гёделя.

Очевидно, что всегда можно сделать алгоритм AA(), который сначала выписывает текст алгоритма A(x), а затем запускает алгоритм A(x) с этим текстом в качестве аргумента. Так вот, у этого алгоритма AA() тоже есть текст его «программы», и этот текст может быть получен из текста алгоритма A(x) посредством обработки этого текста неким алгоритмом diag(«A(x)»). Это довольно очевидно и такая возможность берется за исходную посылку. То есть – нам нужны достаточно выразительные теории, которые способны представлять алгоритмы и тогда алгоритм diag(…) – будет среди них. Теория Пеано – относится к таким теориям.

В теории алгоритмов для аналогичных целей используется теорема о неподвижной точке, но там нумерация алгоритмов сплошная и неполиномиальная поэтому, а нам нужна нумерация в духе «тексты алгоритмов». Да, не все тексты будут текстами алгоритмов, но этот случай нас не пугает – тогда такие «алгоритмы» ничего не возвращают и это можно понять.

Поэтому за основу возьмем Лемму о диагонализации из книги «Вычислимость и логика» Дж. Булос, Р. Джеффри. Только там она доказана для предиката, а мы докажем ее для алгоритма. В остальном я практически переписываю доказательство. И еще один момент – там доказательство на основе «представлений», а я оперирую с алгоритмами – логика та же, просто через представления возникает дополнительный «этаж» манипуляций, но мы просто можем считать, что наша теория чуть более выразительна в обозначениях, чем «чистая» теория Пеано и можно оперировать прямо со свойствами алгоритмов. Такая выразительность легко достижима и теоретически обоснована. Смотри:

Э. Мендельсон, «Введение в математическую логику», Наука, М. 1984. Глава 2, раздел 9 «Введение новых функциональных букв и предметных констант». Введение новой функциональной буквы, когда функция однозначно представлена в теории – ничего не меняет в логическом отношении.

Лемма. О диагонализации

Для произвольного алгоритма B(x) найдется алгоритм G(), такой что G = B(«G()»).

Доказательство.

Назовем алгоритмом G() тот алгоритм, который выполняет расчет как B(diag(«B(diag(x))»)).

Собственно, G() отличается от B(diag(«B(diag(x))»)) только тем, что алгоритм G() сначала выписывает аргумент «B(diag(x))», а затем запускает композицию функций B(diag(…)) с этим аргументом. Если у нас прописан порядок подстановки аргумента в алгоритм с одним аргументом и получения на этой основе алгоритма без аргументов, то алгоритмы G() и B(diag(«B(diag(x))»)) – разные обозначения для одного и того же. Но нюансы разных вариантов подстановки аргументов в алгоритм будут рассмотрены в пункте 2.3 раздела 6 «Задачи Кука и авторизуемые задачи из класса NP». Текст алгоритма G() получается вот так:

diag(«B(diag(x))»).

Ведь алгоритм diag(…) построен именно так, чтобы возвращать текст подобных алгоритмов.

Теперь перейдём к доказательству Леммы.

1. По свойствам diag(…): «G()» = diag(«B(diag(x))»)

2. По построению G(): G() = B(diag(«B(diag(x))»))

3. Из п. 1 подстановкой частей равенства в B(x):

B(«G()») = B(diag(«B(diag(x))»))

4. Из пп. 2 и 3: BG()») = G()

Лемма доказана

Как запомнить эту формулу: B(diagB(diag(x))»))?

Изначально Гёдель решал вопрос о применении предиката к самому себе и формула B(diag(…)) была как раз способом применить предикат / алгоритм  к тексту такого алгоритма, который работает со своим собственным текстом. Но в качестве такового алгоритма подставлялся текст … самого алгоритма B(diag(х)) и поэтому получается выражение B(diagB(diag(x))»)).

Смысл этого выражения в том, что предикат / алгоритм B(…) применяется к самому себе. А вложенность diag(x) двойная, потому что сначала надо применять B(…) к произвольному предикату / алгоритму с аргументом x, в котором передаётся собственный текст предиката / алгоритма, а затем на место «произвольного x» в B(diag(x)) ставится сам «B(diag(х))» - и в нём уже есть diag(х). Два этапа подстановки – для произвольного и конкретизация произвольного в данный предикат / алгоритм – порождают композицию с двумя алгоритмами диагонализации.

Впрочем, сам Гёдель термин «диагонализация» не использовал, насколько известно, но смысл его действий был именно такой.


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