眾所周知，天才的羅素是個(gè)奇葩，他是數(shù)學(xué)出身居然憑借邏輯特長獲得了諾貝爾文學(xué)獎(jiǎng)，而這個(gè)天才提出的“羅素悖論”更是被稱為“數(shù)學(xué)的一場(chǎng)嚴(yán)重危機(jī)”。

• 羅素悖論

注意：以下內(nèi)容過于干貨，非戰(zhàn)斗人員請(qǐng)?zhí)^直接看“理發(fā)師悖論”

羅素悖論，簡(jiǎn)單來說就是對(duì)一個(gè)集合而言，有兩種不同的類別，一種是集合的全體元素里包含有集合自己。比如集合T定義為“全體非正方形物體組成的集合”，由于T本身是一個(gè)集合，不是正方形，所以T自己也應(yīng)該作為一個(gè)元素包含在T中，這類集合叫做本身集合。另一種集合在其所有元素中不包含集合自身。這樣的集合最為常見，例如全體整數(shù)組成的集合，全體女人組成的集合等等都不允許集合自身成為元素。此類集合叫做非本身集合。

如果假定S是自身的一個(gè)元素，則根據(jù)分類規(guī)定S是一個(gè)本身集合，而剛剛說過S的定義是全體非本身集合的集合，既然S是本身集合，所以S應(yīng)該不是自身元素。這就出現(xiàn)了矛盾。這個(gè)兩難問題便是羅素悖論。

怎么樣？看完之后是不是覺得自己現(xiàn)在一頭霧水，有沒有一種大佬果然是大佬的拜服感？！

其實(shí)，羅素悖論還有一個(gè)簡(jiǎn)單通俗的描述方式：理發(fā)師悖論。

• 理發(fā)師悖論

在一座小島上有位理發(fā)師, 有一天他做出一項(xiàng)規(guī)定: 他給島上所有不自己理發(fā)的人理發(fā)，并且只給那些不給自己理發(fā)的人理發(fā)。

最初, 這個(gè)規(guī)定并沒什么問題, 后來, 隨著這個(gè)理發(fā)師自己的頭發(fā)越來越長, 他發(fā)現(xiàn)自己陷入了一個(gè)兩難的境地: 他該不該給自己理發(fā)?

如果他不為自己理發(fā)，按照他自定義的規(guī)則，他屬于自己的服務(wù)客戶范圍，因此可以給自己理發(fā)；

如果他選擇為自己理發(fā)，同樣按照規(guī)則，他便不屬于自己的服務(wù)對(duì)象，因此他又不能給自己理發(fā)。

綜合以上兩種情況, “他為自己理發(fā)”當(dāng)且僅當(dāng)“他不為自己理發(fā)”, 這成為了一個(gè)悖論。面對(duì)這個(gè)困惑的理發(fā)師究竟應(yīng)該何去何從呢？To be or not to be, that is a question!

羅素悖論在很多領(lǐng)域有都普遍存在, 在計(jì)算機(jī)領(lǐng)域就有一個(gè)非常出名的例子——圖靈停機(jī)問題。

• 圖靈停機(jī)問題

寫過程序的人一定知道一種痛苦，就是程序?qū)懞瞄_始運(yùn)行后等了半天毫無反應(yīng)，既沒有報(bào)錯(cuò)，又沒有停止，讓人不知所措。出現(xiàn)這種情況，一般有兩種成因。一是程序運(yùn)行的時(shí)間的確比較耗時(shí)，而編程人員又忘記編制任何運(yùn)行中的動(dòng)態(tài)提示功能，導(dǎo)致機(jī)器好像毫無反應(yīng)。如果是這種情況，很好解決，只要增加運(yùn)行中的屏幕提示，比如打印某個(gè)變量的狀態(tài)或計(jì)算某種進(jìn)度即可。但另一種情況會(huì)比較麻煩，就是程序執(zhí)行陷入了死循環(huán)，永不停止。如果是這樣，那么就必須跟蹤查找死循環(huán)發(fā)生的位置并修改相應(yīng)程序代碼。

因此程序員們都期望能夠有理論大牛發(fā)明一個(gè)判斷程序來提前預(yù)報(bào)死循環(huán)是否會(huì)在程序中出現(xiàn)。把一段即將運(yùn)行的代碼作為字符串序列輸入到該判斷程序中，判斷程序直接通過某種算法分析被輸入程序的結(jié)構(gòu)，并給出預(yù)報(bào)結(jié)果：該程序可以或不可以在有限時(shí)間內(nèi)完成計(jì)算停止。這就是有名的停機(jī)判定問題。

這里說的有限時(shí)間是一種純理論概念，一個(gè)算法即使所需執(zhí)行時(shí)間要200億年，超過宇宙的壽命，它在理論上也被認(rèn)為是可停機(jī)的，也就是說“有限時(shí)間”無論是1秒還是100億年，只要有終止的時(shí)候就可以稱之為“在有限時(shí)間內(nèi)結(jié)束運(yùn)行”。

不失一般性, 假設(shè)我們想要測(cè)試的代碼是一個(gè)函數(shù)

其中 t 是一個(gè)字符串, 我們可以用一個(gè)字符串表示任意輸入, 包括 int, double, 及復(fù)合數(shù)據(jù)類型; 當(dāng) f 不需要輸入時(shí), t 是一個(gè)空字符串。停機(jī)問題是指對(duì)給定任意的一個(gè)函數(shù) f 和輸入 t, 判斷f對(duì)t是否會(huì)永遠(yuǎn)運(yùn)行下去; 如果程序的運(yùn)行時(shí)間是有限長的, 我們稱 f 對(duì) t 停機(jī)。

遺憾的是, 不存在這樣的一個(gè)工具使得其能判斷任意 f 的停機(jī)問題, 即停機(jī)問題不可判定。

以下我們用反證法證明這個(gè)斷言。假設(shè)存在這樣的一個(gè)函數(shù)可用于判斷停機(jī)問題：

其中 f_code 是我們要進(jìn)行測(cè)試的函數(shù) f 的 ASCII 源代碼, 我們可以認(rèn)為對(duì) f_code 進(jìn)行編譯得到了函數(shù) f。?當(dāng) f 對(duì) t 停機(jī)時(shí), halts(f_code, t) 返回 true; 當(dāng) f 對(duì) t 不停機(jī), halts(f_code, t) 返回 false。

我們構(gòu)造這樣一個(gè)函數(shù)：

即當(dāng) f 對(duì) f_code 停機(jī)時(shí), 我們讓 modified_halts 不停機(jī); 當(dāng) f 對(duì) f_code 不停機(jī)時(shí), modified_code 停機(jī)。

假設(shè) modified_halts 這個(gè)函數(shù)的 ASCII 源代碼是 modified_halts_code, 如果我們把 modified_halts_code 作為 modified_halts 的輸入會(huì)是什么情況?

若modified_halts對(duì)modified_halts_code停機(jī), 說明halts(modified_halts_code, modified_halts_code)返回false, 說明modified_halts對(duì)modified_halts_code不停機(jī);

若modified_halts對(duì)modified_halts_code不停機(jī), 說明halts(modified_halts_code, modified_halts_code)返回true, 說明modified_halts對(duì)modified_halts_code停機(jī)。

綜合以上兩種情況, "modified_halts 對(duì) modified_halts_code 停機(jī)"當(dāng)且僅當(dāng) "modified_halts 對(duì) modified_halts_code 不停機(jī)", 這是一個(gè)矛盾, 說明不存在這樣一個(gè) halts 函數(shù)可用于判斷任意函數(shù)的可停機(jī)性。

以上這個(gè)證明利用的就是理發(fā)師悖論, modified_halts 函數(shù)就像是那位小島上的理發(fā)師,?他對(duì)并且只對(duì)那些不停機(jī)的函數(shù)停機(jī)。當(dāng) modified_halts 函數(shù)面對(duì)他自己的函數(shù)代碼時(shí),?就像理發(fā)師該不該給他自己剪頭發(fā)一樣, 將陷入兩難境地。

其實(shí)無論是停機(jī)問題，還是羅素悖論，亦或是理發(fā)師悖論，其本質(zhì)上都是不可解問題，都屬于數(shù)學(xué)中的內(nèi)容。而數(shù)學(xué)在程序員編程的過程里一直都扮演著極為重要的作用。

• 程序員的數(shù)學(xué)