dmitgu (dmitgu) wrote,
dmitgu
dmitgu

Category:

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

к Оглавлению

С помощью леммы о диагонализации легко доказать, что множество теорем теории «неопределимо». То есть, что нет такого предиката B(…), что при подстановке в качестве аргумента текста теоремы t будет доказано B(t), если у теоремы есть доказательство в теории, или будет доказано ~B(t) в противном случае. Простое доказательство «неопределимости» можно посмотреть в упомянутой «Вычислимость и логика» Дж. Булос, Р. Джеффри. Мы же разберём аналогичный по природе пример:

Нет такого алгоритма C(…), который при подстановке в качестве аргумента программного текста некоторого алгоритма a выдавал бы 1, когда алгоритм с текстом a выдаёт 1, а в противном случае выдавал бы 0.

Для доказательства построим

G() = Anti(CG()»)) – из Леммы о диагонализации

Где диагонализацию проводим по алгоритму Anti(C(…))

Что мы, фактически делаем? Мы запускаем алгоритм C(…), передав ему в качестве аргумента текст алгоритма G(), а когда C(…) возвращает результат, то алгоритм Anti(…) меняет его на «противоположный» и возвращает в качестве своего результата, опровергая результат CG()»). Алгоритм Anti(…) построен так:

Anti(1) = 0; А если X ≠ 1, то Anti(X) = 1

Построенный процедурой диагонализации алгоритм G() действительно исполняет Anti(..) по результатам работы C(…) – так как это часть программы G(), код которой и был передан C(…). Это я пытаюсь наглядно пояснить смысл равенства G() = Anti(CG()»)).

Гипотезами нашего доказательства будут:

1. остановка CG()») с результатом и 2. Соответствие результата CG()») результату работы G(). При этом в соответствии с гипотезой 1 результат работы G() – будет (он остановится), так как он определён как G() = Anti(CG()»)), справа композиция, в которой CG()») останавливается в соответствии с гипотезой 1, а за этим остановится и Anti(…).

Перепишем гипотезы в виде формул:

1. CG()») = x, где x = 0 или x = 1 и 2. C(«G()») = Anti(Anti(G()))

Здесь конструкция Anti(AntiC(G())) сводит работу G() к 1 и 0, но без «наоборот», потому что тут композиция двух Anti(…). И гипотеза CG()») = Anti(Anti(G())) как раз выражает, что алгоритм C(…) способен сообщить о работе произвольного алгоритма, но нас интересует только G().

Теперь выведем противоречие из приведенных гипотез:

G() = Anti(CG()»)) – из Леммы о диагонализации

Anti(CG()»)) = Anti(Anti(Anti(G()))) – из 2ой гипотезы, применив Anti(…) к обеим частям равенства

G() = Anti(Anti(Anti(G()))) – из 2ух предыдущих и транзитивности равенства

Anti(Anti(G())) = Anti(Anti(Anti(Anti(Anti(G()))))) – из предыдущего, применив Anti(Anti(…)) к обеим частям

CG()») = Anti(Anti(Anti(CG()»)))) – из предыдущего, заменяя Anti(Anti(G())) в обеих частях по 2ой гипотезе

CG()») = Anti(CG()»)) из предыдущего и свойств Anti(…)

CG()») ≠ Anti(CG()»)) из свойств Anti(…) и С(«G()») – когда есть остановка и результат (0 или 1) у С(«G()») в соответствии с 1ой гипотезой

Две последние формулы образуют противоречие, так как CG()») ≠ Anti(CG()»)) является другим способом записать формулу ~(CG()») = Anti(CG()»))).

Значит, гипотезы не верны, и теорема доказана.

Приведенное доказательство раскрывает природу трудностей (непреодолимых) при построении «универсального решения»: На любое «универсальное решение» есть более сложный алгоритм, который использует это «универсальное решение» против него самого. И причина неопределимости множества теорем теории – точно такая же.


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