由《羅素的故事》所想到的

一口氣看了圖靈出版社的《羅素的故事》，對(duì)于里面的提到的一些問題還是比較有興趣的，聊聊自己所想到的吧

比如邏輯的本質(zhì)和定義是什么 邏輯的定義：一切新的，決定性的推理，這個(gè)有點(diǎn)像演算系統(tǒng)。本質(zhì)是什么，里面貌似沒有說，我個(gè)人理解邏輯的本質(zhì)就是根據(jù)現(xiàn)有規(guī)則，進(jìn)行演算的過程。

羅素悖論

羅素最重要的發(fā)現(xiàn)，就是我們聽到的的：羅素悖論

什么羅素悖論：我記得少年包青天里面有一個(gè)故事，大概是一個(gè)王爺想懲罰包拯，給包拯出了一個(gè)題目，說如果包拯猜對(duì)了他在想什么，就可以放了他，如果猜錯(cuò)了，就要懲罰他。包拯就說：王爺想懲罰我。最后王爺沒有懲罰包拯，因?yàn)槿绻聦?duì)了，王爺必須放了他，如果猜錯(cuò)了，說明王爺沒有想懲罰包拯。

導(dǎo)致羅素悖論的最大問題就是自指性，個(gè)人感覺定義一個(gè)概念的時(shí)候，用到了這個(gè)概念本身。比如我們?nèi)绾味x無窮大數(shù)字，可以這么定義：比無窮大還大的數(shù)字，但是這個(gè)是不合理的，什么是無窮大還是沒有正確的說明。

關(guān)于羅素悖論，是從集合論推導(dǎo)出來的，集合的定義是這樣的：所有具有共通屬性的事物的集合

那么集合有兩種性質(zhì)：所有的集合的集合本身也是一個(gè)集合，所有數(shù)字的集合不是一個(gè)數(shù)，在第一種情況下，就包含了自指，就會(huì)產(chǎn)生悖論

那我們提出一個(gè)問題：所有不包括自身集合所組成的集合是否包含自身？

可以看出，這個(gè)是沒有答案的，也就是不可證的。如果這個(gè)集合包含自身，那么他就不屬于這樣的集合，如果這個(gè)集合不包含自身，那么他應(yīng)該在這個(gè)集合里面

可以用一個(gè)形象的例子來說明：假設(shè)有這樣一種性質(zhì)的網(wǎng)頁，這種網(wǎng)頁里面的每一個(gè)鏈接所在的域名，都不包含自身所在的域名，比如有一個(gè)網(wǎng)頁  http://www.test.com/index.html 這個(gè)index.html里面定義的所有超鏈接都不包含test.com 域名。 那我想做一個(gè)這種性質(zhì)的網(wǎng)頁，這個(gè)網(wǎng)頁要包含所有這種不包含自身超鏈接的所有網(wǎng)頁，悖論來了，我做的這個(gè)網(wǎng)頁到底應(yīng)不應(yīng)該包含自己的域名？

如果不包含自身，那么就不滿足我自己的定義，因?yàn)槲乙页鏊羞@種性質(zhì)的網(wǎng)頁，我自己本身就具有這種性質(zhì)，如果包含自身，也不滿足我的定義，因?yàn)槲叶x了我要做一個(gè)不包含自身的網(wǎng)頁。

為什么悖論重要

這個(gè)悖論為什么這么重要，其實(shí)說明了一個(gè)重要的問題，基于命題規(guī)則的演算系統(tǒng)，本身是不完備的。也就是在這個(gè)系統(tǒng)里面，存在一個(gè)命題，我們無法證明。

我們初中基礎(chǔ)的歐式幾何就存在這樣的問題，我們來看看歐式幾何的幾個(gè)公里

歐式幾何的五條公設(shè)是：

　　1、任意兩個(gè)點(diǎn)可以通過一條直線連接。

　　2、任意線段能無限延伸成一條直線。 

　　3、給定任意線段，可以以其一個(gè)端點(diǎn)作為圓心，該線段作為半徑作一個(gè)圓。

　　4、所有直角都全等。

　　5、若兩條直線都與第三條直線相交，并且在同一邊的內(nèi)角之和小于兩個(gè)直角和，則這兩條直線在這一邊必定相交。

很多數(shù)學(xué)家都對(duì)第五條公里產(chǎn)生質(zhì)疑，因?yàn)檫@個(gè)太復(fù)雜了，和前面四條基本公里沒有任何聯(lián)系，無法通過前面四個(gè)規(guī)則推導(dǎo)出來，也就是說，在歐式幾何這一套體系里面，肯定存在一個(gè)命題，我們是沒有辦法證明的，也就是他是不完備的。很多數(shù)學(xué)家根據(jù)基本規(guī)則，推導(dǎo)出所有確定性的結(jié)論，這個(gè)是不可能的。

而其他數(shù)學(xué)家，如黎曼，則通過定義了球面集合的幾個(gè)基本公理，也推導(dǎo)出來自包含的非歐式幾何。我們小時(shí)候并不了解這個(gè)演算和推理過程背后的實(shí)質(zhì)以及存在的問題，直到19世紀(jì)與20世紀(jì)一批牛逼的邏輯數(shù)學(xué)家解決了這個(gè)問題。

我們可以把這個(gè)公理當(dāng)做基本規(guī)則，根據(jù)這個(gè)規(guī)則推導(dǎo)出來的所有命題的過程叫做演算，這樣就形成了一個(gè)完整的體系。如果這個(gè)基本規(guī)則是相同的，那么無論通過何種演算過程推導(dǎo)出來的體系，肯定也是一致性的相容的，也就是說過在A體系里面推導(dǎo)出S命題是正確的，那么在B體系里面，根據(jù)相同規(guī)則推導(dǎo)出來的S'命題也是正確的。

和編程的關(guān)系

說了這么多，貌似和編程一點(diǎn)關(guān)系都沒有，但是最近看到 函數(shù)式編程，我突然有點(diǎn)受到啟發(fā)，怎么說了，函數(shù)式編程和這個(gè)演算過程很類似，

函數(shù)時(shí)編程 所定義的 lamda表達(dá)式就是一個(gè)演算系統(tǒng)，和歐式幾何一樣，先定義一套基本的規(guī)則，也就是lamda表達(dá)式，這個(gè)基本規(guī)則，對(duì)任何函數(shù)式編程都是一樣的。后續(xù)的所有計(jì)算結(jié)果都是基于我們所定義的基本規(guī)則進(jìn)行演算的過程。這一套規(guī)則不僅僅可以用來做我們熟悉的編程，還是做任何其他的事情，比如人工智能領(lǐng)域，因?yàn)橐?guī)則和演算過程對(duì)于函數(shù)式編程語言來說，都是可以自我定義的。但是上面我們介紹了，這一套體系里面肯定會(huì)存在有一些命題是無法判定的，那么在函數(shù)式編程里面，就存在停機(jī)判定問題。

停機(jī)問題（halting problem）判斷任意一個(gè)程序是否會(huì)在有限的時(shí)間之內(nèi)結(jié)束運(yùn)行的問題。如果這個(gè)問題可以在有限的時(shí)間之內(nèi)解決，那么就可以有一個(gè)程序判斷其本身是否會(huì)停機(jī)。但是，在程序停止之前，沒有辦法判斷它會(huì)不會(huì)停止。所以這是一個(gè)不可解的問題。

下面來看看問題的證明

假設(shè)存在這種算法，我們用下列偽代碼描述:
function halting(func, input) {
return if_func_will_halt_on_input;
}

我們構(gòu)造另一函數(shù):
function is_halt(func) {
if (halting(func, func)) {
for(;;) //死循環(huán) }
}

接下來,調(diào)用:
is_halt(is_halt)

函數(shù)is_halt以is_halt為輸入時(shí),到底停機(jī)還是不停機(jī)? 其實(shí)就是羅素悖論，由于自指性，所以存在悖論。

在根據(jù)一致性結(jié)論，所有編程語言C，java，匯編，.net，lisp，由于都是在同一套規(guī)則上推導(dǎo)出來的，所以在邏輯上是等價(jià)，也就是說 能夠用C語言實(shí)現(xiàn)的功能，都是可以用其他的語言來實(shí)現(xiàn)。

扯了這么多，這個(gè)也是自己的理解，有一些地方不一定正確，大家就當(dāng)看看了解而已，之所以想寫這個(gè)，只是發(fā)現(xiàn)編程的本質(zhì)真的是數(shù)學(xué)，程序員應(yīng)該多了解一些數(shù)學(xué)知識(shí)，數(shù)學(xué)能夠幫你看到一些本質(zhì)的問題