計(jì)算機(jī)起源的數(shù)學(xué)思想

來源于：算法與數(shù)學(xué)之美

人類的歷史可以看做一部關(guān)于解放的歷史。也有這樣的說法，懶惰是人類進(jìn)步的動(dòng)力。為了偷懶，人類不斷的做著各種努力，發(fā)明了各種機(jī)器工具，將自己從繁重的勞動(dòng)解放出來，另一方面，每一次大的進(jìn)步，都需要解放思想，同時(shí)也帶來了全人類思想的大解放。在這樣的歷程中，計(jì)算機(jī)的出現(xiàn)無疑將人類從很多繁重的作業(yè)中解放了出來。與此同時(shí)，有些人開始思考能否制造出可以像人類一樣進(jìn)行思考的機(jī)器，以將人類從創(chuàng)造性的勞動(dòng)和邏輯思考中解放出來，交給機(jī)器去完成。

>>>>

雖然計(jì)算機(jī)的出現(xiàn)，不到百年，然而為了它的出現(xiàn)，所進(jìn)行的探索和研究，早已經(jīng)歷經(jīng)數(shù)百年的歷史。當(dāng)然準(zhǔn)確的說，這些探索和研究在當(dāng)時(shí)實(shí)際并不是為了計(jì)算機(jī)產(chǎn)生而進(jìn)行的，絕大多數(shù)只是做了一個(gè)無意的鋪墊。或許我們并不熟悉這樣的一個(gè)過程，老實(shí)說現(xiàn)代的大學(xué)教育中也很少提及計(jì)算機(jī)出現(xiàn)之前的那些歷史。實(shí)際上，了解這樣的一個(gè)過程，更有助于我們理解一個(gè)事物是如何產(chǎn)生出來，它背后的科學(xué)原理又是如何，讓我們可以透過復(fù)雜的電路外表，接觸到最本質(zhì)的東西。可以讓我們除了對(duì)科學(xué)家們的工作表示贊嘆之外，也可以深入他們當(dāng)初的思想過程，近距離地進(jìn)行跨越時(shí)間和空間的溝通。這對(duì)于我們自己應(yīng)該如何思考問題，創(chuàng)造性地提出自己的想法也是有所幫助的。

我們已經(jīng)了解到這樣的一些人物，喬治.布爾,康托，哥德爾，圖靈，馮諾依曼。而我們的離散數(shù)學(xué)的教學(xué)中，本身太注重于知識(shí)本身的學(xué)習(xí)，而忽略了知識(shí)是如何被發(fā)現(xiàn)產(chǎn)生出來，以及不同的知識(shí)之間曾經(jīng)的淵源和啟發(fā)關(guān)系。而對(duì)于啟迪思想來說，后者顯然更為有力。

萊布尼茨之夢(mèng)

早在17世紀(jì)的萊布尼茨就有一個(gè)偉大的構(gòu)想，他希望可以將人類的思維像代數(shù)運(yùn)算那樣符號(hào)化，規(guī)則化，從而讓笨的人通過掌握這樣的規(guī)則變得聰明，更進(jìn)一步的制造出可以進(jìn)行思維運(yùn)算的機(jī)器，將人類從思考中解放。從萊布尼茨為微積分所確定的依然在今天被沿用的符號(hào)中，我們可以看出他對(duì)符號(hào)具有良好的感覺，通過選擇良好的符號(hào)，可以大大的簡(jiǎn)化運(yùn)算的復(fù)雜性，甚至將這樣的運(yùn)算變成一種天然的過程。除了構(gòu)想之外，萊布尼茨本身為了發(fā)展一種邏輯演算也進(jìn)行了很多嘗試，他得到的一些結(jié)果已經(jīng)具有后來布爾的邏輯代數(shù)的雛形。

布爾的邏輯代數(shù)

19世紀(jì)的布爾，將邏輯代數(shù)化，發(fā)展出了邏輯代數(shù)成為后來計(jì)算機(jī)內(nèi)部運(yùn)算的邏輯基礎(chǔ)。

在早期的研究中，布爾就已經(jīng)認(rèn)識(shí)到符號(hào)的力量，代數(shù)的力量正源于代表著量和運(yùn)算的符號(hào)在幾條基本規(guī)則的支配下體現(xiàn)出來的。后來，他開始思考能否將邏輯推理也像代數(shù)那樣用符號(hào)和幾條基本規(guī)則就可以完全表達(dá)。

他開始思考我們通常所說的某物具有某種性質(zhì)，可以用一個(gè)類來表示，比如白的是x，綿羊是y，那么白綿羊就可以用xy來表示，這樣日常生活中的概念開始具有代數(shù)的形式，用現(xiàn)代的術(shù)語來說上面的xy表示的正是交集。

他又繼續(xù)思考，xx表示什么呢，他發(fā)現(xiàn)xx與我們普通的代數(shù)運(yùn)算不同xx依然表示的是x。xx=x實(shí)際上成為布爾的邏輯代數(shù)的一個(gè)基本規(guī)則。

繼續(xù)考慮下去，如果xx=x在普通的代數(shù)中意味著什么呢？xx=x，意味著x=1或者0.可以看到如果xx=x作為邏輯代數(shù)的基本規(guī)則，放在普通代數(shù)中意味著x=0或者1，那么邏輯代數(shù)是否意味著是01的普通代數(shù)呢。于是布爾得到一個(gè)基本原理，如果僅僅限于01，邏輯代數(shù)就變成了普通代數(shù)。關(guān)于這一點(diǎn)的思考，對(duì)于二進(jìn)制運(yùn)算的在邏輯代數(shù)中的主導(dǎo)作用具有很大的啟發(fā)意義。

如果限于01，那么01在我們的邏輯代數(shù)中代表的意思又是什么呢。我們之前看到可以用x表示某個(gè)類，對(duì)應(yīng)地那么0可以解釋成沒有任何東西屬于它的類，1可以解釋成包含所有對(duì)象的全體。同時(shí)布爾又開始考慮普通代數(shù)中的+-在邏輯代數(shù)中的意義，x+y可以表示具有x和y兩種屬性的對(duì)象集合，x-y表示具有x屬性同時(shí)不具有y屬性的對(duì)象集合。

考慮了這樣的一些意義之后，接下來再看xx=x=> x-xx = 0 => x(1-x) = 0
現(xiàn)在我們以邏輯代數(shù)的觀點(diǎn)看這個(gè)式子，它體現(xiàn)了這樣一個(gè)含義：沒有任何東西可以同時(shí)屬于又不屬于某個(gè)類。這點(diǎn)讓布爾十分振奮，因?yàn)檫@剛好體現(xiàn)了亞里士多德的排中律，這就使他確信自己找對(duì)了路子。

繼續(xù)下去，布爾發(fā)現(xiàn)三段論也可以用他的邏輯代數(shù)來表達(dá)。

所有x都是y x=xy(x中的任何東西也屬于y，就等于說沒有任何東西是屬于x而不屬于y的，也就是說x(1-y)=0)
所有y都是z y=yz

------------ ?
所有x都是z x=xz
x=xy
y=yz => x = xy = x(yz) = (xy)z = xz

最后，"如果x，那么y。"可以用x(1-y)=0來表示,可以這樣理解這個(gè)式子意味著如果x=1，那么y=1。在這里一方面我們可以把"如果x，那么"理解為等同于前面的這樣一句話"所有的x都是y",當(dāng)然這兩者有一個(gè)區(qū)別，現(xiàn)在的x，y表示的是命題，而原來的x，y表示的則是類概念。以今天的觀點(diǎn)來看，前者是命題演算，后者是謂詞演算。

但是如果從另一個(gè)方面，重新考慮這句話，比如x=1表示命題x為真，x=0表示命題x為假，xy=1表示x且y，只有x，y均為1，xy=1，如果x=0或y=0，xy=0，這點(diǎn)又與普通代數(shù)相一致。從這個(gè)方向思考下去，就可以看到今天的布爾代數(shù)的基本面貌了，上面的這個(gè)定義正是與運(yùn)算。

布爾的邏輯體系，不僅包含了亞里士多德的邏輯體系，而且還超越了它，但是仍有無法表達(dá)的情形：所有失敗的學(xué)生或者是糊涂的或者是懶惰的。

今天的布爾代數(shù)

回到今天，我們?cè)倏床紶栐侔堰壿嬣D(zhuǎn)變成代數(shù)的過程中，所產(chǎn)生的邏輯代數(shù)在今天的計(jì)算機(jī)中扮演著什么樣的作用。布爾代數(shù)只有1和0兩個(gè)元素，not and or三種運(yùn)算，用幾張真值表就可以表達(dá)清楚。

AND | 1 0

-----------------------

1 | 1 0

0 | 0 0

這張表說明如果 AND 運(yùn)算的兩個(gè)元素有一個(gè)是?0，則運(yùn)算結(jié)果總是?0。如果兩個(gè)元素都是 1，運(yùn)算結(jié)果是 1。例如，“太陽從西邊升起”這個(gè)判斷是假的(0),“水可以流動(dòng)”這個(gè)判斷是真的（1），那么，“太陽從西邊升起并且水可以流動(dòng)”就是假的（0）。

OR | 1 0

-----------------------

1 | 1 1

0 | 1 0

這張表說明如果OR運(yùn)算的兩個(gè)元素有一個(gè)是 1，則運(yùn)算結(jié)果總是 1。如果兩個(gè)元素都是?0，運(yùn)算結(jié)果是?0。比如說，“張三是比賽第一名”這個(gè)結(jié)論是假的（0），“李四是比賽第一名”是真的（1），那么“張三或者李四是第一名”就是真的（1）。

NOT |

--------------

1 | 0

0 | 1

這張表說明 NOT 運(yùn)算把 1 變成?0，把?0?變成 1。比如，如果“象牙是白的”是真的（1），那么“象牙不是白的”必定是假的（0）。

如此簡(jiǎn)單的運(yùn)算，實(shí)際上當(dāng)時(shí)的布爾也不會(huì)想到它會(huì)被運(yùn)用到計(jì)算機(jī)中，直到1938 年香農(nóng)在他的碩士論文中指出用布爾代數(shù)來實(shí)現(xiàn)開關(guān)電路，使得布爾代數(shù)成為數(shù)字電路的基礎(chǔ)。所有的數(shù)學(xué)和邏輯運(yùn)算，加、減、乘、除、乘方、開方等等，全部能轉(zhuǎn)換成二值的布爾運(yùn)算。

用計(jì)算的力量改變世界是每一個(gè)程序員的夢(mèng)想，YaK團(tuán)隊(duì)抱著對(duì)教育的敬仰和熱忱，開發(fā)了有趣的YaK編程工具以及配套的系統(tǒng)化教學(xué)課程。讓孩子可以用編程去學(xué)習(xí)和理解上帝的語言：數(shù)學(xué)。

前言：人類的歷史可以看做一部關(guān)于解放的歷史。也有這樣的說法，懶惰是人類進(jìn)步的動(dòng)力。為了偷懶，人類不斷的做著各種努力，發(fā)明了各種機(jī)器工具，將自己從繁重的勞動(dòng)解放出來，另一方面，每一次大的進(jìn)步，都需要解放思想，同時(shí)也帶來了全人類思想的大解放。在這樣的歷程中，計(jì)算機(jī)的出現(xiàn)無疑將人類從很多繁重的作業(yè)中解放了出來。與此同時(shí)，有些人開始思考能否制造出可以像人類一樣進(jìn)行思考的機(jī)器，以將人類從創(chuàng)造性的勞動(dòng)和邏輯思考中解放出來，交給機(jī)器去完成。

前面我們看到計(jì)算起源的數(shù)學(xué)思想有萊布尼茨，布爾代數(shù)。接下來我們看到其他的數(shù)學(xué)思想在計(jì)算中的運(yùn)用。

弗雷格的突破與絕望

弗雷格的一生主要發(fā)表了這樣三本著作：《概念演算--一種模仿算術(shù)語言構(gòu)造的純思維的符號(hào)語言》（1879）、《算術(shù)的基礎(chǔ)--對(duì)數(shù)概念的邏輯數(shù)學(xué)研究》（1884）《算術(shù)的基本規(guī)律》（l卷 1893，2卷1903）。

其中概念演算，將普通數(shù)學(xué)中的一切演繹推理都包含在內(nèi)，成為第一個(gè)完備的邏輯體系。布爾以普通代數(shù)為基礎(chǔ)，用代數(shù)符號(hào)來表示邏輯關(guān)系。與此相反，弗雷格想以他的邏輯為基礎(chǔ)而把代數(shù)構(gòu)造出來。實(shí)際上這成為日后一個(gè)重要的學(xué)派"邏輯主義",在他們看來邏輯與數(shù)學(xué)的關(guān)系就像一門學(xué)科的基本部分和高等部分之間的關(guān)系。

弗雷格的邏輯體系，表現(xiàn)在今天就是我們數(shù)理邏輯中的命題演算和謂詞演算(用數(shù)學(xué)的方法研究關(guān)于推理、證明等問題的學(xué)科就叫做數(shù)理邏輯。也叫做符號(hào)邏輯)。弗雷格第一次用精確的句法構(gòu)造出形式化的人工語言，使得邏輯推理表示為機(jī)械演算即所謂的推理規(guī)則成為可能。從這個(gè)觀點(diǎn)看，概念文字是我們今天使用的計(jì)算機(jī)程序設(shè)計(jì)語言的前身。

弗雷格希望可以自然數(shù)提出一種純粹邏輯的理論，從而證明算術(shù)，微積分乃至一切數(shù)學(xué)都可以看成邏輯的一個(gè)分支。于是弗雷格便希望可以用純邏輯的術(shù)語來定義自然數(shù)，然后再用他的邏輯導(dǎo)出它們的性質(zhì)。例如3這個(gè)數(shù)將被解釋為邏輯的一部分。弗雷格的思想是把3定義為所有元素?cái)?shù)為3的集合的集合。實(shí)際上這就是《算術(shù)的基礎(chǔ)--對(duì)數(shù)概念的邏輯數(shù)學(xué)研究》這部著作的主要內(nèi)容。

然而正是這樣的一些工作，1902年，年輕的伯特蘭.羅素?fù)?jù)此提出那個(gè)著名的羅素悖論。弗雷格的算術(shù)使用了集合的集合這樣一種概念。羅素指出，用集合的集合進(jìn)行推理很容易導(dǎo)致矛盾。羅素的悖論可以這樣描述：如果一個(gè)集合是它自身的一個(gè)成員，那么就把集合成為異常的，否則它就是正常的。那么由所有正常集合組成的集合是正常還是異常的呢？

如果是正常的，那么它應(yīng)該包含自身，這樣它就應(yīng)該是異常的。如果是異常的，那么它就不會(huì)包含自身，這樣它就應(yīng)該是正常的。無論哪個(gè)結(jié)果都導(dǎo)致了矛盾。實(shí)際上羅素構(gòu)造這個(gè)悖論的方法，與之后哥德爾，圖靈構(gòu)造不可判定命題卻有著神似的地方。然而這一矛盾卻表明弗雷格構(gòu)造的算術(shù)體系所基于的那些前提是靠不住的，并給弗雷格帶來了巨大的打擊。

雖然弗雷格的邏輯已經(jīng)很完備，但仍然具有一些局限性。他的規(guī)則并沒有提供判定某個(gè)結(jié)論能否從給定的前提中推導(dǎo)出來的計(jì)算步驟。另外能否找到一種計(jì)算方法，它能夠說明在弗雷格的邏輯中某一推理是正確的呢？其結(jié)果是這樣一則證明：沒有這樣的一般方法存在。然而正是在證明這樣一條否定性的結(jié)論過程中，阿蘭圖靈發(fā)現(xiàn)原則上可以設(shè)計(jì)出一種通用機(jī)，它可以執(zhí)行任何可能的計(jì)算。

弗雷格的研究開啟語言哲學(xué)的大門，后來人們?cè)趯ふ易C明邏輯推理正確性的過程中，圖靈發(fā)現(xiàn)了通用機(jī)，也就是今天計(jì)算機(jī)的數(shù)學(xué)模型。

康托爾，對(duì)無限的探索

康托爾進(jìn)入無限的世界，開始無限的數(shù)目的研究。他發(fā)現(xiàn)自然數(shù)與實(shí)數(shù)具有不同的基數(shù)，以及由此提出的連續(xù)統(tǒng)假設(shè)，即實(shí)數(shù)和自然數(shù)之間不存在具有其他基數(shù)的集合。這也是1900年，希爾伯特提出的23個(gè)問題中的第一問題。這個(gè)問題直到今天并未完全解決，1938年哥德爾和1963年保羅科恩的重大發(fā)現(xiàn)表明，如果連續(xù)統(tǒng)假設(shè)問題可以被解決，就必須超越普通數(shù)學(xué)的方法。

對(duì)于我們普通人來說，最有用的大概是康托爾在證明實(shí)數(shù)與自然數(shù)基數(shù)不同的過程中所采用的對(duì)角線方法，這種方法是1891年，康托爾在一篇4頁的論文中發(fā)表的。而對(duì)角線方法，在以后的故事中仍然會(huì)被用到，它將會(huì)被哥德爾用來解決一致性問題時(shí)構(gòu)造系統(tǒng)內(nèi)不可證命題，然后阿蘭.圖靈又再次使用了哥德爾的方法構(gòu)造出了不可判定命題。而關(guān)于連續(xù)統(tǒng)假設(shè)的研究也引發(fā)了關(guān)于圖靈機(jī)的構(gòu)想。現(xiàn)在我們可以看到康托爾的工作與計(jì)算機(jī)的起源在這里產(chǎn)生了聯(lián)系。

關(guān)于對(duì)角線方法，我們從自然數(shù)集來看，我們可以發(fā)現(xiàn)自然數(shù)與自然數(shù)的子集組成的集合之間具有不同的基數(shù)，假設(shè)我們把自然數(shù)與不同的自然數(shù)子集建立一個(gè)對(duì)應(yīng)關(guān)系，1: M1 2: M2....，采用對(duì)角線方法，我們總是可以構(gòu)造出一個(gè)新的自然數(shù)集，它沒有任何自然數(shù)與之對(duì)應(yīng)，我們這樣產(chǎn)生這個(gè)新的自然數(shù)集：如果i屬于Mi,那么排除i，否則包含i，容易看到這樣產(chǎn)生的一個(gè)集合不同于任何的Mi。可見由一切自然數(shù)集組成的集合的基數(shù)要大于自然數(shù)的基數(shù)。

實(shí)際上康托爾并不是第一個(gè)關(guān)注到無限的數(shù)目特殊性的人，早在17世紀(jì)，萊布尼茨就發(fā)現(xiàn)偶數(shù)和自然數(shù)是一一對(duì)應(yīng)的，正如他所說：對(duì)于任何一個(gè)數(shù)，都存在一個(gè)與之對(duì)應(yīng)的偶數(shù)，那就是它的二倍。因此所有數(shù)的數(shù)目并不比偶數(shù)的數(shù)目更多，也就是說整體沒有部分大。但是他得出了這樣一個(gè)結(jié)論：所有自然數(shù)的數(shù)目這一概念是不一致的，討論一個(gè)無限集中元素的數(shù)目是沒有意義的。但是康托了選擇了另一條路，他承認(rèn)某些無限集將與它的一個(gè)子集具有相同的元素?cái)?shù)目。正是基于這樣一個(gè)大膽的選擇，他才創(chuàng)立了關(guān)于無限的新理論。

當(dāng)康托爾提出這些觀點(diǎn)之后，立刻引來了各方面的責(zé)難。與弗雷格類似，人們發(fā)現(xiàn)用康托爾的超限數(shù)進(jìn)行不加限制的推理會(huì)導(dǎo)致荒謬的結(jié)果。比如如果存在一個(gè)由所有基數(shù)組成的集合，那么它的基數(shù)該是多少呢？它必須比所有基數(shù)都大，但一個(gè)基數(shù)又怎么可能比所有基數(shù)都大呢？后來羅素又指出這樣的一個(gè)問題：是否存在一個(gè)所有集合的集合？如果存在，那么倘若把對(duì)角線方法應(yīng)用于它，會(huì)出現(xiàn)什么結(jié)果？這樣我們會(huì)得到一個(gè)不同于所有那些已經(jīng)擁有標(biāo)簽的集合的集合。正是在考慮這種情況時(shí)，羅素發(fā)現(xiàn)他那個(gè)關(guān)于由一切不是自身的集合組成的集合的著名悖論，也就是他向弗雷格傳達(dá)的那個(gè)悖論。這里我們看到，弗雷格和康托爾之間被羅素悖論聯(lián)系起來。而關(guān)于這個(gè)悖論的討論和思考，則引發(fā)了數(shù)學(xué)史上的第三次危機(jī)。

大衛(wèi)希爾伯特

希爾伯特是20世紀(jì)的數(shù)學(xué)領(lǐng)袖，1900年他在數(shù)學(xué)家大會(huì)上指出的23個(gè)問題，其中第二個(gè)便是關(guān)于算術(shù)一致性的問題。即關(guān)於一個(gè)公理系統(tǒng)相容性的問題，也就是判定一個(gè)公理系統(tǒng)內(nèi)的所命題是彼此相容無矛盾的，希爾伯特希望能以嚴(yán)謹(jǐn)?shù)姆绞絹碜C明任意公理系統(tǒng)內(nèi)命題的相容性。

希爾伯特綱領(lǐng)所提出的主要問題就是算術(shù)一致性問題。為了解決這個(gè)問題，希爾伯特發(fā)展出了元數(shù)學(xué)，一致性證明將在元數(shù)學(xué)內(nèi)部完成。1928年，希爾伯特和他的學(xué)生阿克曼出版了一本邏輯課本，書中提出了關(guān)于弗雷格<<概念文字>>的基本邏輯(后來被稱為一階邏輯)兩個(gè)主要問題，一個(gè)就是，證明一階邏輯的完備性，即任何一個(gè)從外部看來有效的公式都可以只用課本里提出規(guī)則從系統(tǒng)內(nèi)部導(dǎo)出。第二個(gè)問題以希爾伯特的判定問題而聞名，即對(duì)于一個(gè)一階邏輯的公式，如果找到一種方法，可以在定義明確有限步驟內(nèi)判定這個(gè)公式是有效的。這兩個(gè)問題分別為哥德爾和圖靈解決，而在解決第二個(gè)問題的過程中，圖靈提出了圖靈機(jī)的概念。

后來在1928年的國際數(shù)學(xué)家大會(huì)上，希爾伯特又提出一個(gè)關(guān)于形式系統(tǒng)的問題，這個(gè)系統(tǒng)建立在把一階邏輯應(yīng)用于現(xiàn)在被稱為皮亞諾算術(shù)或者PA的自然數(shù)公理系統(tǒng)的基礎(chǔ)之上。希爾伯特希望可以證明PA是完備的，也就是說任何一個(gè)可以在PA中表出的命題或者可以在PA中被證明為真，或者可以被證明為假。兩年后，這個(gè)問題被一個(gè)叫哥德爾的年輕人解決了，但答案卻完全不像希爾伯特料想的那樣。

哥德爾完備性定理

希爾伯特在20世紀(jì)20年代介紹了他的元數(shù)學(xué)綱領(lǐng)：一致性有待證明的公理將被包含在一個(gè)形式邏輯系統(tǒng)之內(nèi)，而證明僅僅是有限數(shù)目的符號(hào)的一種排列而已。當(dāng)希爾伯特開始思考希爾伯特綱領(lǐng)時(shí)，希爾伯特的學(xué)生阿克曼和馮諾依曼似乎正在朝著用有限性方法證明PA的一致性的方向大步邁進(jìn)。他們二人都已經(jīng)為PA的一個(gè)有限的子系統(tǒng)找到了這樣的證明，成功似乎指日可待。

這樣哥德爾開始試圖將算術(shù)一致性還原為PA的一致性，然而就是在這樣的努力中失敗了。哥德爾開始思考這些問題時(shí)，他重新思考了從外部而不是從內(nèi)部考察一個(gè)系統(tǒng)的意思。從外部看，這些系統(tǒng)包含著符號(hào)串之間的關(guān)系。從內(nèi)部看，這些系統(tǒng)能夠表達(dá)關(guān)于不同數(shù)學(xué)對(duì)象的命題。哥德爾通過給符號(hào)串用自然數(shù)編碼，將外部帶到了內(nèi)部。

哥德爾發(fā)現(xiàn)存在這樣的命題，它們從系統(tǒng)外部看是真命題，但無法在系統(tǒng)內(nèi)部得到證明。于是他得出了一個(gè)非凡結(jié)論：一種有意義的數(shù)學(xué)真理的觀念不僅是存在的，而且其范圍還超出了任何給定的形式系統(tǒng)的證明能力。在1931年，他發(fā)表的論文<<論?<數(shù)學(xué)原理>及有關(guān)系統(tǒng)的形式不可判定命題>>中，他選擇對(duì)形式系統(tǒng)PM給出了他的結(jié)果，從而說明即使強(qiáng)邏輯系統(tǒng)也不可能把全部數(shù)學(xué)真理包含在內(nèi)。

在哥德爾的證明中，關(guān)鍵的一步在于他證明了：一個(gè)自然數(shù)作為PM中可證命題的一個(gè)代碼，這一性質(zhì)本身可以在PM中表示出來。根據(jù)這一事實(shí)，哥德爾可以在PM中構(gòu)造出一些命題，這些命題可以被看做表達(dá)了這樣一個(gè)斷言，即某些命題在PM中是不可證的。也就是說他可以構(gòu)造出一個(gè)命題A，該命題經(jīng)譯碼后可以斷言某一命題B在PM中是不可證的。現(xiàn)在，在沒有獲知密碼的人看來，命題A不過是一串符號(hào)而已，但是通過代碼，神秘性就消失了：A表示這樣一個(gè)命題，即某個(gè)符號(hào)串B表示在PM中一個(gè)不可證的命題。A和B通常是不同的命題，哥德爾問，它們是否有可能是相同的呢？事實(shí)上它們可以是相同的，哥德爾可以利用對(duì)角線方法證明這個(gè)結(jié)論。

運(yùn)用這些技巧，我們可以使被斷言為不可證的命題和做出這一斷言的命題是同一個(gè)命題。換句話說哥德爾發(fā)現(xiàn)了如果獲得這樣一個(gè)非凡的命題，我們將它稱之外U，具有如下性質(zhì)：

U說某個(gè)特殊命題在PM中不可證。
那個(gè)特殊的命題就是U本身。
因此，U說"U在PM中不可證"

如果我們承認(rèn)PM中證明的任何命題都是真的，那么我們發(fā)現(xiàn)U是真的，但它在PM中不可證。

U是真的。假定它是假的，那么它表述的內(nèi)容就是假的，因此它就是不是不可證的，而一定是可證的，從而是真的，這與開始假定U是假的矛盾，所以它一定是真的。因?yàn)樗钦娴模运硎龅膬?nèi)容為真，所以它在PM中不可證。

我們把U稱為不可判定命題，當(dāng)然這種不可判斷性只與系統(tǒng)內(nèi)部的可證性，從我們外部的觀點(diǎn)來看U是真的。

另一方面，在PM內(nèi)部，我們可以證明：如果PM是一致的，那么U。因此正是PM是一致的這一個(gè)假定，才使U在PM內(nèi)部得不到證明。既然我們知道U在PM內(nèi)部是不可證的，我們就必須得出結(jié)論說，PM的一致性在PM中不可證。而希爾伯特的主要目的就在于：用于被認(rèn)為構(gòu)成PM的一個(gè)非常有限的子集的有限性方法來證明像PM這樣的系統(tǒng)的一致性。然而哥德爾證明了，即使就PM的全部能力而言，它也不足以證明自身的一致性。于是希爾伯特綱領(lǐng)走到了盡頭。

圖靈和圖靈機(jī)

在哥德尓1930年的博士論文中證明了弗雷格的規(guī)則是完備的，這樣就回答了希爾伯特1928年提出的第一個(gè)問題。而第二個(gè)問題即判定問題，在哥德爾的工作發(fā)表之后，人們很難想象存在這樣的判定算法，于是阿蘭圖靈開始思考如果證明這樣的算法是不存在的。

圖靈采取了這樣的一條道路，他首先分析了人的計(jì)算過程。通過丟掉非本質(zhì)的細(xì)節(jié)，將這些計(jì)算活動(dòng)局限在少數(shù)幾種極為簡(jiǎn)單的基本操作上。然后圖靈說明人可以被一個(gè)能夠執(zhí)行這些基本操作的機(jī)器所替代。然后只要證明僅僅執(zhí)行那些基本操作的機(jī)器不可能判定一個(gè)給定的結(jié)論是否可以用弗雷格的規(guī)則從給定的前提中導(dǎo)出，這樣他就能夠下結(jié)論說，判定問題的算法是不存在的。

作為副產(chǎn)品，他對(duì)計(jì)算過程的分析，產(chǎn)生了通用計(jì)算機(jī)的一個(gè)數(shù)學(xué)模型。

他觀察到：在計(jì)算的每一個(gè)階段，只有少數(shù)符號(hào)受到了注意。每一個(gè)階段所采取的行動(dòng)僅僅取決于受到注意的那些符號(hào)以及當(dāng)前的心靈狀態(tài)。

然后他做出了如下抽象：計(jì)算通過在一條被劃分成方格的紙帶上寫下符號(hào)來進(jìn)行。執(zhí)行計(jì)算的人在每一步都只注意其中一個(gè)方格的符號(hào)。她的下一步將僅僅取決于這個(gè)符號(hào)和她的心靈狀態(tài)。她的下一步是這樣的：她在當(dāng)前注意的方格里寫下一個(gè)符號(hào)，然后將注意力轉(zhuǎn)向它左邊或者右邊的相鄰符號(hào)。

現(xiàn)在可以很容易看出，做這項(xiàng)工作的人可以用一個(gè)機(jī)器替代，紙帶在機(jī)器上來回移動(dòng)。關(guān)鍵之處在于圖靈對(duì)于計(jì)算概念的分析，通過某種算法程序可計(jì)算的任何東西都可以通過一臺(tái)圖靈機(jī)來計(jì)算。因此如果我們可以證明某些任務(wù)無法用圖靈機(jī)完成，那么我們就可以說沒有任何算法可以完成這項(xiàng)任務(wù)。這就是圖靈證明判定問題不存在算法的方法。

實(shí)際上一臺(tái)圖靈機(jī)可以用這樣的一個(gè)五元組來表示：當(dāng)機(jī)器處于狀態(tài)R，注視紙帶上的符號(hào)a時(shí)，它將用b來代替a，向右移動(dòng)一個(gè)方格，然后轉(zhuǎn)到狀態(tài)S。而一個(gè)具體的算法便可以由這些五元組表示的狀態(tài)轉(zhuǎn)換的集合組成的圖靈機(jī)來表示出來。R a:b -> S 或者R a:b <- S

圖靈將對(duì)角線方法應(yīng)用于這種情況，得到了圖靈機(jī)不能解決的問題，由此推出了判定問題的不可解性。與哥德尓類似，圖靈采用了對(duì)角線方法也對(duì)圖靈機(jī)通過自然數(shù)進(jìn)行了編碼。

圖靈機(jī)本身可以是自然數(shù)編碼表示，這樣它也作為自身的輸入。實(shí)際上有些輸入會(huì)使圖靈機(jī)停止下來，另一些則不會(huì)。這樣一臺(tái)圖靈機(jī)就具有一些停機(jī)集合。如果我們考慮把一臺(tái)圖靈機(jī)的停機(jī)集合組成了一個(gè)包裹，并且認(rèn)為那臺(tái)機(jī)器的碼數(shù)就是這個(gè)包裹的標(biāo)簽。對(duì)角線方法允許我們構(gòu)造出一個(gè)與圖靈機(jī)的任何停機(jī)集合都不同的自然數(shù)集合，我們稱之為D。方法是這樣的，我們考慮把圖靈機(jī)的編碼作為自身的輸入，如果它的編碼數(shù)不屬于自身的停機(jī)集合，那么我們就把它加入D。而集合D則不是任何圖靈機(jī)的停機(jī)集合。

然后考慮這樣一個(gè)問題：
找到一種算法，判定一個(gè)給定的自然數(shù)是否屬于集合D。

這就是一個(gè)不可解問題的例子。首先如果存在這樣的一個(gè)算法，我們就能找到這樣的一個(gè)圖靈機(jī)，但是我可以改造一下這個(gè)圖靈機(jī)，把以下兩個(gè)五元組加入到這個(gè)圖靈機(jī)：F 0:口-> F 和 F 口:口-> F。對(duì)于這個(gè)新的改進(jìn)的圖靈機(jī)來說，如果輸入的數(shù)屬于D那么那么機(jī)器就會(huì)像以前一樣運(yùn)轉(zhuǎn)，并輸出1而告終，如果輸入的數(shù)不屬于D，那這臺(tái)機(jī)器將永遠(yuǎn)向右移動(dòng)。這樣我們就找到了一臺(tái)圖靈機(jī)它的停機(jī)集合剛好就是D。于是與我們的對(duì)角線方法矛盾。所以并不存在這樣的一個(gè)算法。由此可知判斷問題在算法上是不可解的。

為了驗(yàn)證自己工作的有效性，圖靈又提出了通用機(jī)模型，通用機(jī)包含了圖靈機(jī)代碼以及待處理的數(shù)據(jù)。而這剛好對(duì)應(yīng)著我們今天的機(jī)器，程序與數(shù)據(jù)的概念。也為存儲(chǔ)程序計(jì)算機(jī)提供了一個(gè)模型。正是圖靈在證明判定問題的不可解性是，對(duì)計(jì)算概念的分析以及對(duì)通用機(jī)的發(fā)現(xiàn)促使了計(jì)算機(jī)的產(chǎn)生。

1945年圖靈又發(fā)表了他那篇著名的ACE(自動(dòng)計(jì)算機(jī))報(bào)告。這是對(duì)計(jì)算機(jī)的一次完整的描述，一直到邏輯電路圖。也就是在這時(shí)馮諾依曼提出了他著名的"關(guān)于EDVAC的報(bào)告草案"，它實(shí)際上主張將要建造的EDVAC作為圖靈通用機(jī)的一個(gè)物理模型實(shí)現(xiàn)出來。在這個(gè)報(bào)告里，提出了存儲(chǔ)程序的概念，也就是沿用至今的馮諾依曼結(jié)構(gòu)，實(shí)際上它的革命性不在于存儲(chǔ)程序而是通用性，存儲(chǔ)程序只是達(dá)到這一目的的一種手段。

1950年，圖靈又發(fā)表了他的經(jīng)典論文，計(jì)算機(jī)與智能，提出了著名的圖靈測(cè)試來測(cè)試計(jì)算機(jī)是否具有智能。1954年6月7日，圖靈咬了一個(gè)浸過氰化物的蘋果，結(jié)束了自己的生命。而他的通用機(jī)思想?yún)s延續(xù)到今天。

—THE END—

編輯?∑Gemini

來源：MathAndAlgorithm