Теоремі Геделя про неповноту , Однією з найвідоміших теорем математичної логіки, пощастило і не пощастило одночасно. У цьому вона схожа на спеціальну теорію відносності Ейнштейна. З одного боку, майже всі про них щось чули. З іншого - в народній інтерпретації теорія Ейнштейна, як відомо, «говорить, що все в світі відносно». А теорема Геделя про неповноту (далі просто ТГН), в приблизно настільки ж вільної фолк-формулюванні, «доводить, що є речі, незбагненні для людського розуму». І ось одні намагаються пристосувати її в якості аргументу проти матеріалізму , А інші, навпаки, доводять з її допомогою, що бога немає . Забавно не тільки те, що обидві сторони не можуть виявитися правими одночасно, але і те, що ні ті, ні інші не спромагаються розібратися, що ж, власне, ця теорема стверджує.
Отже, що ж? Нижче я спробую «на пальцях» розповісти про це. Виклад моє буде, зрозуміло нестрогим і інтуїтивним, але я попрошу математиків не судити мене строго. Можливо, що для нематематика (до яких, взагалі-то, ставлюся і я), в розказаному нижче буде щось нове і корисне.
Математична логіка - наука дійсно досить складна, а головне - не дуже звична. Вона вимагає акуратних і строгих маневрів, при яких важливо не переплутати реально доведене з тим, що «і так зрозуміло». Проте, я сподіваюся, що для розуміння наступного нижче «начерку докази ТГН» читачеві знадобиться тільки знання шкільної математики / інформатики, навички логічного мислення і 15-20 хвилин часу.
Дещо спрощуючи, ТГН стверджує, що в досить складних мовах існують недоведені висловлювання. Але в цій фразі майже кожне слово потребує пояснення.
Почнемо з того, що спробуємо розібратися, що таке доказ. Візьмемо якусь шкільну задачку з математики. Наприклад, нехай потрібно довести вірність наступної нехитрої формули: « 
»(Нагадаю, що символ 
читається «для будь-якого» і називається «квантор загальності»). Довести її можна, тотожне перетворюючи, скажімо, так:
- ІСТИНА
Перехід від однієї формули до іншої відбувається за деякими відомими правилами. Перехід від 4-й формули до 5-ї стався, скажімо, тому, що будь-яке число дорівнює самому собі - така аксіома арифметики. А вся процедура доведення, таким чином, переводить формулу в логічне значення ІСТИНА. Результатом могла бути і брехня - якби ми спростовували якусь формулу. В такому випадку ми б довели її заперечення. Можна собі уявити програму (і такі програми дійсно написані ), Які б доводили подібні (і більш складні) висловлювання без участі людини.
Викладемо те ж саме трохи більше формально. Нехай у нас є безліч, що складається з рядків символів якогось алфавіту, і існують правила, за якими з цих рядків можна виділити підмножина 
так званих висловлювань - тобто граматично осмислених фраз, кожна з яких є істинною або помилкова. Можна сказати, що існує функція 
, Що зіставляє висловлювань з одне з двох значень: ІСТИНА або БРЕХНЯ (тобто відображає їх в булево безліч 
з двох елементів).
Назвемо таку пару - безліч висловлювань і функція з в - «мовою висловлювань». Зауважимо, що в повсякденному сенсі поняття мови дещо ширше. Наприклад, фраза російської мови «А ну йди сюди!» Не істинна і не помилкова, тобто висловлюванням, з точки зору математичної логіки, не є.
Для подальшого нам знадобиться поняття алгоритму. Наводити тут формальне його визначення я не буду - це завело б нас досить далеко в сторону. Обмежуся неформальним: «алгоритм» - ця послідовність однозначних інструкцій ( «програма»), яка за кінцеве число кроків переводить вихідні дані в результат. Виділене курсивом принципово важливо - якщо на якихось початкових даних програма зациклюється, то алгоритму вона не описує. Для простоти і в застосуванні до нашого випадку читач може вважати, що алгоритм - це програма, написана на будь-яке відоме йому мові програмування, яка для будь-яких вхідних даних із заданого класу гарантовано завершує свою роботу з видачею булевого результату.
Запитаємо себе: для будь-якої чи функції існує «доводить алгоритм» (або, коротше, «дедуктіка»), еквівалентний цієї функції, тобто переводить кожне висловлювання саме в той логічне значення, що і вона? Лаконічніше той же питання можна сформулювати так: чи всяка функція над безліччю висловлювань обчислюваності ? Як ви вже здогадалися, з справедливості ТГН слід, що ні, не всяка - існують невичіслімие функції такого типу. Іншими словами, не всяке вірне висловлювання можна довести.
Дуже може бути, що це твердження викличе у вас внутрішній протест. Пов'язано це з кількома обставинами. По-перше, коли нас вчать шкільної математики, то іноді виникає хибне враження майже повної тотожності фраз «теорема 
вірна »і« можна довести або перевірити теорему ». Але, якщо вдуматися, це зовсім не очевидно. Деякі теореми доводяться досить просто (наприклад, перебором невеликого числа варіантів), а деякі - дуже складно. Згадаймо, наприклад, знамениту Велику теорему Ферма :
доказ якої знайшли тільки через три з половиною століття після першої формулювання (і воно далеко не елементарно). Слід розрізняти істинність висловлювання і його доказовою. Нізвідки не випливає, що не існує справжніх, але недоведені (і не перевіряються в повній мірі) висловлювань.
Другий інтуїтивний аргумент проти ТГН тонший. Припустимо, у нас є якесь недовідне (в рамках даної дедуктікі) висловлювання. Що заважає нам прийняти його в якості нової аксіоми? Тим самим ми трохи ускладнити нашу систему доказів, але це не страшно. Цей аргумент був би абсолютно вірний, якби недовідних висловлювань було кінцеве число. На практиці ж може статися наступне - після постулирования нової аксіоми ви натрапите на нове недовідне висловлювання. Приймете його в якості ще аксіоми - натрапите на третє. І так до нескінченності. Кажуть, що дедуктіка залишиться неповною. Ми можемо також прийняти силові заходи, щоб доводить алгоритм закінчувався через кінцеве число кроків з якимось результатом для будь-якого висловлювання мови. Але при цьому він почне брехати - приводити до істини для невірних висловлювань, або до брехні - для вірних. У таких випадках кажуть, що дедуктіка суперечлива. Таким чином, ще одна формулювання ТГН звучить так: «Існують мови висловлювань, для яких неможлива повна несуперечлива дедуктіка» - звідси і назва теореми.
Іноді називають «теоремою Геделя» твердження про те, що будь-яка теорія містить проблеми, які не можуть бути вирішені в рамках самої теорії і вимагають її узагальнення. В якомусь сенсі це вірно, хоча таке формулювання швидше затуманює питання, ніж прояснює його.
Зауважу також, що якби йшлося про звичних функціях, які відображають безліч дійсних чисел в нього ж, то «невичіслімость» функції нікого б не здивувала (тільки не треба плутати «обчислюваної функції» і «Обчислюваних числа» - це різні речі). Будь-якому школяреві відомо, що, скажімо, в разі функції 
вам повинно сильно повезти з аргументом, щоб процес обчислення точного десяткового подання значення цієї функції закінчився за кінцеве число кроків. А швидше за все ви будете обчислювати її за допомогою нескінченної низки, і це обчислення ніколи не приведе до точного результату, хоча може підійти до нього як завгодно близько - просто тому, що значення синуса більшості аргументів ірраціонально. ТГН просто говорить нам про те, що навіть серед функцій, аргументами якої є рядки, а значеннями - нуль або одиниця, невичіслімие функції, хоча і зовсім по іншому влаштовані, теж бувають.
Для подальшого опишемо «мова формальної арифметики». Розглянемо клас рядків тексту кінцевої довжини, що складаються з арабських цифр, змінних (букв латинського алфавіту), які беруть натуральні значення, прогалин, знаків арифметичних дій, рівності і нерівності, кванторів 
( «Існує») і ( «Для будь-якого») і, можливо, якихось ще символів (точну їх кількість і склад для нас не важливі). Зрозуміло, що не всі такі рядки осмислені (наприклад, « 
»- це нісенітниця). Підмножина осмислених висловлювань з цього класу (тобто рядків, які істинні або помилкові з точки зору звичайної арифметики) і буде нашим безліччю висловлювань.
Приклади висловлювань формальної арифметики:
і т.д. Тепер назвемо «формулою з вільним параметром» (ФСП) рядок, яка стає висловлюванням, якщо в якості цього параметра підставити в неї натуральне число. Приклади ФСП (з параметром 
):
і т.д. Іншими словами, ФСП еквівалентні функціям натурального аргументу з булевими значенням.
Позначимо множину всіх ФСП буквою 
. Зрозуміло, що його можна впорядкувати (наприклад, спочатку випишемо впорядковані за алфавітом однобуквені формули, за ними - дволітерні і т.д .; за яким саме алфавітом відбуватиметься упорядкування, нам не принципово). Таким чином, будь-який ФСП відповідає її номер 
в упорядкованому списку, і ми будемо позначати її 
.
Перейдемо тепер до начерку докази ТГН в такому формулюванні:
- Для мови висловлювань формальної арифметики не існує повної несуперечливої дедуктікі.
Доводити будемо від противного.
Отже, припустимо, що така дедуктіка існує. Наведемо наступний допоміжний алгоритм 
, Що ставить у відповідність натуральному числу логічне значення наступним чином:
- знаходимо -у формулу в списку .
- Підставляємо в неї число в якості аргументу.
- Застосовуємо до отриманого висловом наш доводить алгоритм (за нашим припущенням, він існує), який переводить його в істину або БРЕХНЯ.
- Застосовуємо логічне заперечення до отриманого результату.
Простіше кажучи, алгоритм призводить до значення ІСТИНА тоді і тільки тоді, коли результат підстановки в ФСП її власного номера в нашому списку дає хибне висловлювання.
Тут ми підходимо до єдиного місця, в якому я попрошу читача повірити мені на слово.
Очевидно, що, при зробленому вище припущенні, будь ФСП з можна зіставити алгоритм, який містить на вході натуральне число, а на виході - логічне значення. Менш очевидно зворотне твердження:
Доказ цієї леми зажадало б, як мінімум, формального, а не інтуїтивного, визначення поняття алгоритму. Однак, якщо трохи подумати, то вона досить правдоподібна. Справді, алгоритми записуються на алгоритмічних мовах, серед яких є такі екзотичні, як, наприклад, Brainfuck , Що складається з восьми односимвольних слів, на якому, проте, можна реалізувати будь-який алгоритм. Дивно було б, якби описаний нами більш багата мова формул формальної арифметики виявився б біднішою - хоча, без сумніву, для звичайного програмування він не дуже підходить.
Пройшовши це слизьке місце, ми швидко добираємося до кінця.
Отже, вище ми описали алгоритм . Згідно лемі, в яку я попросив вас повірити, існує еквівалентна йому ФСП. Вона має якийсь номер в списку - скажімо, 
. Запитаємо себе, чому дорівнює 
? Нехай це ІСТИНА. Тоді, з побудови алгоритму (А значить, і еквівалентної йому функції 
), Це означає, що результат підстановки числа в функцію - БРЕХНЯ. Аналогічно перевіряється і зворотне: з 
БРЕХНЯ слід ІСТИНА. Ми прийшли до протиріччя, а значить, вихідне припущення невірно. Таким чином, для формальної арифметики не існує повної несуперечливої дедуктікі. Що й потрібно було довести.
Тут доречно згадати Епіменіда (Див. Портрет в заголовку), який, як відомо, заявив, що всі крітяни - брехуни, сам будучи критянином. У більш лаконічною формулюванні його висловлювання (відоме як «Парадокс брехуна» ) Можна сформулювати так: «Я брешу». Саме такий вислів, саме превозглашающее свою хибність, ми і використовували для доказу.
На закінчення я хочу зауважити, що нічого особливого дивного ТГН не затверджує. Зрештою, все давно звикли, що не всі числа представимо у вигляді відносини двох цілих (пам'ятаєте, у цього твердження є дуже витончене Доведення , Якому більше двох тисяч років?). І корінням полиномов з раціональними коефіцієнтами є теж не все числа . А тепер ось з'ясувалося, що не всі функції натурального аргументу обчислюваності.
Наведений начерк докази ставився до формальної арифметики, але неважко зрозуміти, що ТГН застосовна і до багатьох інших мов висловлювань. Зрозуміло, не всякі мови такі. Наприклад, визначимо мову наступним чином:
- «Будь-яка фраза китайської мови є вірним висловом, якщо вона міститься в Цитатник товариша Мао Дзе Дуна, і невірна, якщо не міститься».
Тоді відповідний повний і несуперечливий доводить алгоритм (його можна назвати «догматичної дедуктікой») виглядає приблизно так:
- «Гортає цитатника товариша Мао Дзе Дуна, поки не знайдеш шукане висловлювання. Якщо воно знайдено, то воно вірно, а якщо цитатника закінчився, а висловлювання, не знайдено, то воно невірно ».
Тут нас рятує те, що будь-який цитатник, очевидно, кінцевий, тому процес «доведення» неминуче закінчиться. Таким чином, до мови догматичних висловлювань ТГН непридатна. Але ж ми говорили про складні мовами, правда?
Отже, що ж?Що заважає нам прийняти його в якості нової аксіоми?
Але ж ми говорили про складні мовами, правда?