我們永遠(yuǎn)也無法確切了解萬事萬物，總有些真命題是我們無法證明的，沒人能確切知道這些命題是什么（孿生素?cái)?shù)猜想）？

在任何能夠進(jìn)行基本算術(shù)的數(shù)學(xué)系統(tǒng)中，總會存在一些無法證明的真命題。（約翰康威 生命游戲）

• 圖案的最終命運(yùn)無法判定（不存在哪個(gè)算法能保證在有限時(shí)間內(nèi)判定圖案的結(jié)果）
• 不能保證是永久循環(huán)還是某輪終止

很多系統(tǒng)都是不可判定的（王氏磚、量子物理、機(jī)票訂票系統(tǒng)、萬智牌）

格奧爾格康托爾（georg cantor）:集合論

自然數(shù)的集合（可數(shù)無窮） ＜ 0到1之間的實(shí)數(shù)集合（不可數(shù)無窮）

歐幾里得 【非歐幾何（羅巴切夫斯基 高斯）】

微積分的核心：極限的定義是有瑕疵的

直覺論者

形式主義者 （大衛(wèi)希爾伯特）

1901年 伯特蘭羅素：如果集合能包含任何事物，那它也能包含其他集合，甚至包含本身。

導(dǎo)致有個(gè)集合R，它包含了所有【不包含它們本身的集合】，如果R不包含自身，那它就應(yīng)該包含自身。如果R包含自身，那按照R的定義，它就不能包含自身。

【自指】悖論 ：理發(fā)師

修正：不把【所有集合所組成的集合】稱作一個(gè)集合，不把【所有不包含其本身的集合組成的集體】稱作一個(gè)集合

證明系統(tǒng)始于公理

公理：默認(rèn)正確的陳述句（兩點(diǎn)確定一直線）

定理：

希爾伯特對于數(shù)學(xué)有三大問題：

1. 數(shù)學(xué)是否是完備的（complete）（真命題是否都有辦法證明、是否都存在證明？）
2. 數(shù)學(xué)是否是一致的（consistent）（是否不會產(chǎn)生悖論）
3. 數(shù)學(xué)是否是可判定的（decidable）（有無算法能對任意一條陳述句判斷其是否符合公理）

庫爾特哥德爾

• 完備性的答案：不存在完備的形式系統(tǒng)（不完備性定理）（命題為真不意味命題可證）
• 第二條不完備定理

這個(gè)數(shù)學(xué)系統(tǒng)有一個(gè)不可證的真命題，數(shù)學(xué)系統(tǒng)不具有完備性——哥德爾不完備性定理。任何一個(gè)蘊(yùn)含了基礎(chǔ)算術(shù)公理的基本數(shù)學(xué)系統(tǒng)，總是存在無法寫出證明的真命題。

自指悖論：Jim是我的敵人，Jim又是他自己最大的敵人。敵人的敵人是朋友，Jim實(shí)際上也是我的朋友。jim是自己最大的敵人，朋友的敵人是我的敵人，jim也是我的敵人。

（命題為真 不意味 命題可證）沒法證明的真命題

哥德爾不完備性定理第二：數(shù)學(xué)里任一自洽的形式系統(tǒng)都無法證明其本身的自洽性。

我們期望的最理想數(shù)學(xué)系統(tǒng)：只能是一個(gè) 自洽 但 不完備 的系統(tǒng)。并且這樣的系統(tǒng)也無法證明本身自洽，你所用的系統(tǒng)將來總會冒出矛盾之處，揭示其本身的不自洽。

可判定性（是否有算法，對于任一陳述句，都能判定它能否從公理推出來）

艾倫圖靈

停機(jī)表明程序運(yùn)行至終止?fàn)顟B(tài)

對于給定的輸入紙帶，有沒有辦法事先預(yù)測程序能否停機(jī)？

停機(jī)問題 可判定性問題

假設(shè)機(jī)器h:能判定任意圖靈機(jī)對于任一特定輸入是否會停機(jī)

h+：有個(gè)部件只要收到輸出結(jié)果為停機(jī)就會跑死循環(huán)，輸出結(jié)果不停機(jī)就會立刻停機(jī)。

輸入H+代碼：如果h結(jié)論是H+永不停機(jī)，那么h+會立刻停機(jī)。如果h覺得h+會停機(jī)，那么h+就會陷入死循環(huán)。

唯一合理的解釋是：根本不存在h這樣的機(jī)器。沒有通用的辦法能判定圖靈機(jī)對于給定的輸入是否會停機(jī)。

不存在一個(gè)算法能對每一個(gè)命題正確判定其是否由公理推出。（不可判定問題）