Трилогия использования парадокса лжеца

Введение

Мы знаем, тройка математиков:
Курт Гёдель, Алан Тьюринг,
С ними Георг Кантор — за  отца,
Применили очень сильный трюк,
В теоремы взяли парадокс лжеца.
Парадокс помог Георгу
Мощность множества сравнить
С мощностью подмножеств тех,
Что записались в его лист:
Прийдя к нему пророчит лжец
«Мощность всех подмножеств
Больше целого, Отец!»
Курт Гёдель спрятал парадокс,
Неполноту системы доказуя.
Он просто изменил в нем слог:
И вместо «ложь» он взял «недоказуемо».
Сумел он сделать этот трюк,
Используя свои три инструмента:
Нумерация — как партитура,
Главная его архитектура.
Построен предикат — ещё сильнее,
Для доказуемости формул и решений,
А третий трюк — есть подстановка,
Для парадокса точная настройка!
Такое мог придумать математик,
Нутром почувствовав задачу и удачу.
Алан Тьюринг Курта повторил,
Подстановку в коде совершил,
Для компьютерной программы,
Чтоб остановку предсказала
Для компьютера она,
Или в цикл ворвётся снова,
Бесконечный, как всегда.
Но к Алану пришёл лжец и сказал:
«Алан, это твой конец!
Не найти тебе программу,
Чтоб пророчила финал».

Часть I. Пролог у доски (Теорема Кантора)

В Большой физической, на Пирогова в НГУ
Сидят все группы от мехмата — первый курс.
Вот у доски стоит профессор Ляпунов,
И Алексей Андреевич начать нам лекцию готов.
А тема лекции о мощности подмножеств тех,
Которые находятся во множестве — для всех.
«Мощность всех подмножеств несравнима с целым,
Она больше — докажу у доски я с мелом!»
От каждой точки множества проводим мы прямую
К подмножеству, где есть она, находим мы такую.
У нас получатся варианты, один из них где есть прямая,
Второй вариант где нет прямой, знать точка эта никакая.
Коль не нашли подмножество — знать точка та плохая,
А если есть — хорошая она у нас такая.
Теперь организуем подмножество плохих,
Не можем провести прямую от множества для них.
И все здесь опирается на парадокс обычный,
И имя точке из плохих любое — непривычно.
Если плохая точка — хорошая она,
Хорошая же точка плохою быть должна!
Так Георг Кантор — гений девятнадцатого века —
Использовал “парадокс лжеца” для умного человека.
Сказал Ляпунов: «Множеств бесконечных массу
Нельзя уравнять одной прямой, друзья, ни разу
Студенты притихли, парадокс уловив едва,
А в воздухе запахли грядущие тридцатые года...


Часть II. Крушение программы (Теоремы Гёделя)

Стремился мэтр Давид Гильберт
Систему Т из аксиом увидеть —
Чтоб без противоречий, полной стала.
Но Гёделя статья наперекор восстала.
В ней миру Курт представил теоремы две,
И обе теоремы — о неполноте!
Из первой теоремы мы узнаем сразу:
Система Т не все докажет истины и фразы.
Пример: формулу G не доказать, в том суть,
Ее в сей теореме построил Гёдель Курт
Придумал Гёдель код, чтоб утверждения свести
К числам очень ловко, нумерацию ввести
Кодировку взял такую, чтобы аккуратно,
И ясно как вернуться к утверждению обратно.
Гёдель создает текст А(х)-шаблон,
Где место для пароля оставляет он.
Там пропуск был: «Впиши сюда число —
И предикат проверит, что за ним пришло».
Курт в функцию А(х) вписал
Свободную х-переменную.
Сама А(х) свой код имеет,
В нём номер гёделевский веет.
Гёдель настроил предикат,
Который вставить в х он рад.
А предикат у Курта прост:
«Утверждение с х-числом
Недоказуемо в системе аксиом».
Но мы хотим G истинное доказать,
Для утверждения G не трудно код узнать.
Допустим, этот код есть «q».
Что дальше? Я вам расскажу:
Курт дальше подстановку применил —
В А(х) х на q-число сменилось!
И имя формулы А(q) в G изменилось.
Здесь Гёдель как бы зеркало поставил,
Чтоб утверждение G смогло
Себя найти, глядя в стекло,
И рассмеяться, говоря:
«Меня не доказать, это петля!»
Ведь G есть номер утверждения,
С которым говорим мы. Верно?
G может быть иль истинно иль ложно.
Когда б G было ложью,
То по его высказыванию можно,
Сказать, что доказать его не сложно,
Но в аксиомах истинных в системе
Мы доказать лишь истинну сумеем.
И значит истинно G, оно не ложно.
И потому здесь доказать G невозможно.
И Курта Гёделя Мир понял в тот час:
Не всё подвластно доказательству.
Есть истины, пока что выше нас,
Но и сейчас доступны пониманию.



Вторая ж теорема скажет нам ретиво:
«Не доказать внутри свою непротиворечивость
Теми законами, что есть в системе,
Хоть расширяй её объём всё время».
Система Т честна (непротиворечива),
Там нет абсурдов двух, что некрасиво:
Формулу А и НЕ-А (отрицание)
Не доказать одновременно в заседании.
Противоречие в системе — как нарыв,
Рождающий он дедуктивный взрыв!
При взрыве доказуемо любое утверждение —
И ложь, и истина появятся в мгновение.
Доказывaя здесь вторую теорему,
Мы понимаем — мы у Гильберта в системе.
И значит в ней свои есть правила, законы.
Допустим, что система, минуя все заслоны,
Сумела доказать свою непротиворечивость.
Con(T) = «Система Т непротиворечива».
Значит, находясь в системе Гильберта,
Доказательство утверждения G видим мы.
Тогда получается внутри системы Т,
То есть Т доказывает Con(T), а внутри
По правилам её, без всякой лжи,
Собралась строчка: «из Con(T) следует G».
Автомат Гильберта строчку доказал,
Сам Гёдель этот вывод предсказал.
Но если обе строчки робот соберёт,
То Modus Ponen вывод G нам принесет!
Но первая теорема говорит в ответ:;
Для непротиворечивой Т такого права нет.;
Пришли мы к противоречию опять —;
И Con(T) внутри системы нам не доказать.


Часть III. Петля в железе (Проблема остановки Тьюринга)

Тьюринг Алан создал машину-самореференцию.
Что же это за машина? Продолжаем лекцию.
Этот математик вдруг предположил:
Существует алгоритм, иль программа, он решил.
Имя дал он алгоритму, буквой H решил назвать,
И способность обозначил: Н все должен предсказать.
Предсказание простое: должен Н определить,
Остановится ль программа с именем, ну скажем, Р,
Иль будет Р без остановки, если не остановить.
Р здесь тоже алгоритм, иль программой назови.
Х есть вход в программу Н — Тьюринг так решил назвать.
Теперь программу эту Р мы будем мягко в вход толкать.
Что дальше, хочешь ты узнать? Хочу тебе я рассказать.
Дальше Тьюринг применил метод аргумента главного.
Но какого? Он решил и взял диагонального!
Этот метод сильный очень, Cantor Georg его создал,
Он великий математик, теорию множеств он нам дал.
Алан Тьюринг метод взял, теорему доказал.
Что ж взял Тьюринг в этот раз? Продолжаю свой рассказ:
Алан программу D создал, в неё он Н как модуль вставил.
Коль Н предскажет: «Р спит крепко!», то D гулять пойдёт на ветку.
Если ж Р пойдёт гулять, D уляжется в кровать.
Остановку алгоритмов заменил я словом спать,
Если цикл бесконечный — слово можно взять гулять.
Тьюринг Алан сам предложил:«Я бы Р на D вменил,
Сразу можно посмотреть, как изменится ответ!»
Если D улегся спать — значит, должен он гулять!
Если ж D пошёл гулять — значит, должен лечь в кровать!
Вывод Алан у нас простой: нет программы Н такой.
Парадокс ее убрал. Это ложь. Он так сказал.
Значит, есть задачи в мире, хоть стреляйся — не решить их,
Коль компьютер применить. А вручную — может быть!!!

Так трижды Лжец прошёл сквозь вековые вехи:
От канторовских множеств до компьютерных систем.
И там, где роботы свои ломают шестерни,
Нам остаётся интуиция и вырастают гении!