Теорема на Гьодел за непълнота

Теоремата на Гьодел за непълнота описва математически невъзможността за изразяване на цялата истина за дадена предметна област с формални средства (тази формулировка е известна като първа теорема на Гьодел за непълнота).

По-точно:

Нека имаме някаква безкрайна област G от обекти и зависимости между тях и се опитваме да създадем формална теория T, описваща тази област.

Нашата теория T ще позволява с крайни синтактични конструкции (формули, аксиоми, теореми, доказателства) да описваме верните факти за областта G.

Теоремата на Гьодел гласи:

Под достатъчно богата се разбира теория, която изразява понятия като алгоритъм или изчислимост в някаква форма.

Доказателството на теоремата е конструктивно – построява се специален обект, наричан Гьоделево твърдение, което нито може да се докаже, нито да се опровергае от формалната теория T, но е вярно в областта G.

История 
Австрийският математик Курт Гьодел формулира и доказва теоремите си през 1931 г. Доказателството му използва техниката на самопозоваване (self-reference), известна още и като диагонален процес на Кантор. Същата математическа техника причинява и известния парадокс на Ръсел в наивната теория на множествата.

Първите доказателства се отнасят до формални аналози на аритметиката, задавана чрез аксиоми на Пеано.

През 1936 г. Алън Тюринг опростява определението на понятието формален метод, свеждайки го до Машина на Тюринг. Той формулира и първите алгоритмично нерешими задачи, като отбелязва връзката им с теоремата на Гьодел. Доказателствата му също използват самопозоваване (за компютърни програми по-точният термин е самоизследване).

Компютърна интерпретация 
Гьоделевото твърдение е подобно на самоизписваща се програма, по-точно то описва поведението на самоизследваща се компютърна програма P, реализираща следния алгоритъм:

 Създай собствения си текст в променливата A на паметта.
 Създай в променливата B формула от теорията T, съответна на твърдението: Програмата, записана в A спира.
 Търси доказателство в теорията T на някоя от формулите B или ¬B.
 ако намериш доказателство за B, започни безкраен цикъл.
 ако намериш доказателство за ¬B, спри.

Формулата (P се зацикля) е Гьоделево твърдение. То е вярно в нормалния свят на компютърните програми, тъй като единственото поведение на програмата P, което не създава абсурдна ситуация, е тя да търси в т. 3. на алгоритъма доказателство за верността на някоя от двете формули (P спира) и (P се зацикля), без да го намира никога.

Конструкцията на програмата P гарантира, че формулата (P се зацикля) е недоказуема в T, т.е. теорията не е пълна (не съдържа като теореми всички верни твърдения). Думата верни употребяваме в смисъл съдържателно (семантично) верни факти в изследваната област G.

Всички усилия да създадем пълна формална теория за област на изследване, чиято сложност е достатъчна да изрази понятието алгоритъм, са напразни. Можем да добавяме нови аксиоми, но конструкцията на Гьоделево твърдение ще ни даде нова недоказуема формула. Ако добавим всички верни твърдения за G като нови аксиоми ще получим теория, в която нямаме ефективен метод за разпознаване на аксиомите.

Втора теорема 
Прецизиране на доказателството на първата теорема на Гьодел за непълнота, по-точно провеждането му във формалната теория T, дава като резултат втората теорема на Гьодел за непълнота известна още като теорема на Гьодел за непротиворечивост:

Втората теорема обезсмисля усилията да се изгради единна, сигурна и надеждна математическа теория, която да се използва без уговорки като основа или инструмент в останалите науки.

Философска интерпретация 
Теоремата на Гьодел (в двете ѝ форми) налага силни ограничения върху формалните математически теории и върху методите на научно изследване изобщо. Прието е научното изследване да се разглежда като комбинация от експериментални методи и теоретични конструкции, като последните използват за основа математически теории.

След като формалните математически теории са съществено семантично непълни (такъв е смисълът на първата теорема) и тяхната непротиворечивост е недоказуема (по втората теорема), възниква изкушението да се обсъждат алтернативни пътища.

Не е наличен друг инструмент за теоретични заключения. Формалните теории са единственият приемлив от гледна точка на представата ни за научен метод инструмент за логично извеждане на следствия от начални предпоставки.

По-разумно е да се примирим с факта, че обитаваме реалност, в която действат закони, които ни ограничават както по отношение на физическите закони (примерно невъзможността физически обект да се движи по-бързо от светлината), така и по отношение на методите ни за натрупване на знания.

Вижте също 
 Математика
 Основи на математиката
 Логика

Литература 
 K. Gödel: Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I . Monatshefte für Mathematik und Physik, 38 (1931), pp. 173 – 198. Translated in van Heijenoort: From Frege to Gödel. Harvard University Press, 1971.
 B. Rosser: Extensions of some theorems of Gödel and Church. Journal of Symbolic Logic, 1 (1936), N1, pp. 87 – 91
 Hao Wang: A Logical Journey: From Gödel to Philosophy Bradford Books (10 януари 1997) ISBN 0-262-23189-1
 Kārlis Podnieks: Around Goedel's Theorem
 D. Hofstadter: Gödel, Escher, Bach: An Eternal Golden Braid, 1979, ISBN 0-465-02685-0. (1999 reprint: ISBN 0-465-02656-7).
 Ernest Nagel, James Roy Newman, Douglas R. Hofstadter: Gödel's Proof, revised edition (2002). ISBN 0-8147-5816-9.
 Hilbert's second problem (English translation)
 Norbert Domeisen, Logik der Antinomien. Bern etc.: Peter Lang. 142 S. 1990. (ISBN 3-261-04214-1), Zentralblatt MATH 
 Rudy Rucker: Infinity and the Mind, 1982, Princeton University Press (ISBN 978-0-691-00172-2, преиздадена през 2004: ISBN 978-0-691-12127-7)

Гьодел
Математическа логика
Епистемология