為什么會出現(xiàn)圖靈機(jī),？這得從羅素悖論講起,。

羅素悖論

有位理發(fā)師放出豪言：他給且只給不為自己刮胡子的人刮胡子。問：這位理發(fā)師該為自己刮胡子嗎,？

如果理發(fā)師為自己刮胡子,，那么按照他的豪言“只給不為自己刮胡子的人刮胡子”他不應(yīng)該為自己刮胡子；但如果他不為自己刮胡子,，同樣按照他的豪言“他給不為自己刮胡子的人刮胡子”他又應(yīng)該為自己刮胡子,。

這個問題就是著名的理發(fā)師悖論,，是哲學(xué)家兼數(shù)學(xué)家的羅素用來比喻羅素悖論的一個通俗說法,，也被叫作集合論悖論，用集合論來描述就是：

集合 S 由一切不屬于自身的元素組成,，那么 S 是否屬于 S 呢,？

在這一悖論提出之前集合論是數(shù)學(xué)理論的重要基礎(chǔ)，結(jié)合集合論,，歷史上的一切數(shù)學(xué)問題都可以完美地等到求證,，當(dāng)時人們已經(jīng)相信整個數(shù)學(xué)大廈已經(jīng)建立起來了，數(shù)學(xué)已經(jīng)迎來了絕對的嚴(yán)格性,。

但羅素悖論出現(xiàn)后,，人們心中的大廈坍塌了，直接導(dǎo)致了歷史上的第三次數(shù)學(xué)危機(jī),。當(dāng)時提出集合論的數(shù)學(xué)家康托爾也被這個悖論逼瘋了,，可憐的康托爾。由此可見羅素這個人在數(shù)學(xué)界的影響,。

哥德爾不完備性定理

當(dāng)時人們好不容易在集合論的基礎(chǔ)上構(gòu)建起了數(shù)學(xué)大廈,，結(jié)果集合論也是不完美的,，連這個基礎(chǔ)都崩潰了。那還能不能找到一個系統(tǒng),，在它的基礎(chǔ)上真正構(gòu)建整個數(shù)學(xué)大廈呢,？

后來有一個數(shù)學(xué)家哥德爾成功證明了一個定理，大意是這樣的：

世界上存在我們既沒辦法證真也沒辦法證偽的命題,。

比如前文說的的集合論,，還有典型的 1+1=2 的問題，我們既不能證明它們是真命題,，也不能證明它是偽命題,。這個定理被稱為哥德爾不完備性定理。我們可能會想,，這種定理也能被證明,？他是怎么證明的？這個我們就不去研究了,，反正哥德爾他就是證明了這樣的一個定理,，過程是很復(fù)雜的。

哥德爾不完備性定理的證明結(jié)束了關(guān)于數(shù)學(xué)基礎(chǔ)的爭論,，宣告了數(shù)學(xué)不是絕對嚴(yán)格性的,，把數(shù)學(xué)徹底形式化這種愿望是不可能實(shí)現(xiàn)的，不存在這樣一個完美的數(shù)學(xué)系統(tǒng),。

哥德爾不完備性定理告訴我們,，不要試圖去尋找一個完美的系統(tǒng)，這不存在的,，這輩子都不可能存在的,。

那么，有了這個結(jié)論,，我們是不是就可以不往下探索了呢,？如果還可以往下探索，我們該探索什么問題,？

計(jì)算模型和圖靈機(jī)

通過哥德爾不完備性定理,，我們知道，有些問題是既不能證真也不能證偽的,，有些問題是可以證真或證偽的,。對于這兩類問題，它們的邊界在哪里,？怎么去判定一個未解的問題是否真的有解,？

為了解答這個問題，我們需要引入一個度量：可計(jì)算問題,。在數(shù)學(xué)中對應(yīng)可計(jì)算函數(shù),，它的定義是這樣的：

設(shè)函數(shù) f 的定義域?yàn)?D,，值域?yàn)?R，如果存在一種算法,，對于 D 中任意給定的 x，都能計(jì)算出 f(x) 的值,，則稱函數(shù) f 是可計(jì)算的,。

這是當(dāng)時諸多數(shù)學(xué)家、邏輯學(xué)家等對判斷一個問題是否可計(jì)算提出的一個思路,。通俗的講就是,，先給定一個模型，如果拿有限的值去套這個模型,，能夠得到期望的結(jié)果,，那就說明這個問題是可計(jì)算的，否則是不可計(jì)算的,。這里用來判斷問題是否可計(jì)算的模型就被稱為：計(jì)算模型,。

那么如何設(shè)計(jì)或找到這樣一個計(jì)算模型呢？這是當(dāng)時人們所面臨的一個重要問題,，一直沒有得到解決,。后來終于有一位數(shù)學(xué)家提出了一個這樣的模型，他就是圖靈,。他提出的這個計(jì)算模型被稱為圖靈模型,，而這個圖靈模型就是圖靈機(jī)。

好了,，到這里我們已經(jīng)知道了歷史背景下為什么會誕生圖靈機(jī),。那么圖靈模型它是一個怎樣的模型？圖靈機(jī)它又是如何工作的呢,？這就是下一篇要講的內(nèi)容,。

最后順帶講一下圖靈這個人，相信很多人都聽過他的故事,，他真的是很牛逼,。他 24 歲就提出了圖靈機(jī)，二戰(zhàn)期間參與了密碼破譯工作,，任密碼破譯總顧問,，后來還提出了著名的“圖靈測試”，逝世前兩年還寫出了第一個國際象棋程序,。圖靈的貢獻(xiàn)對計(jì)算機(jī)領(lǐng)域的發(fā)展有著非常深遠(yuǎn)的影響,，可惜他享年只有 42 歲（1912 年 - 1954 年），如果不是英年早逝的話,，計(jì)算機(jī)的整個發(fā)展史可能就要重寫了,。