Этот креатив посвящается теореме Гёделя о недоказуемости непротиворечивости, она же вторая теорема Гёделя о неполноте. Пост предназначается для тех, кто желает разобраться, что это такое, не углубляясь в дебри математической логики. В отличие от некоторых научно-популярных источников, в которых всё настолько упрощено, что получается полная чушь, создающая кучу заблуждений, здесь я буду писать правду, хотя и избегая технических деталей. Возможно, прочтение этого текста поможет читателю избавиться от некоторых заблуждений и лучше осознать область применимости теоремы.
Если первая теорема Гёделя — это почти в чистом виде утверждение об алгоритмической неразрешимости, то вторая — это нечто более связанное с теорией доказательств, поэтому у многих может возникнуть впечатление, что, чтобы в ней разобраться, нужно предварительно осилить толстый и пугающий учебник по матлогике с огромными формализмами. Я же хочу убедить читателя, что это вовсе необязательно, здесь тоже вполне достаточно начальных знаний теории алгоритмов (основы теории алгоритмов можно изучить очень быстро, в отличие от логических формализмов). В этом тексте представлено чисто теоретико-алгоритмическое простое доказательство второй теоремы Гёделя, которое достаточно интуитивно понятно и не выглядит как логический фокус. Знание о первой теореме Гёделя не обязательно (она является частным случаем второй, поэтому представленное ниже доказательство можно применить и к ней).
Читать далее…
