久久99国产精品尤物-国产高清色播视频免费看-男生肌肌往女人桶爽视频-精品国产-91PORNY九色|www.jqdstudio.net

|  站內(nèi)搜索:
沒有數(shù)學(xué)何來(lái)計(jì)算機(jī):論計(jì)算機(jī)起源的數(shù)學(xué)思想
點(diǎn)擊:  作者:佚名    來(lái)源:人工智能學(xué)家  發(fā)布時(shí)間:2020-06-20 11:10:06

 

來(lái)源:無(wú)數(shù)學(xué)  無(wú)計(jì)算機(jī)

 

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

 

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

 

 

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

 

萊布尼茨之夢(mèng)

 

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

 

 

布爾的邏輯代數(shù)

 

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

 

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

 

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

 

他又繼續(xù)思考,xx表示什么呢,他發(fā)現(xiàn)xx與我們普通的代數(shù)運(yùn)算不同xx依然表示的是xxx=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可以表示具有xy兩種屬性的對(duì)象集合,x-y表示具有x屬性同時(shí)不具有y屬性的對(duì)象集合。

 

考慮了這樣的一些意義之后,接下來(lái)再看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ù)來(lái)表達(dá)。

 

所有x都是y x=xy(x中的任何東西也屬于y,就等于說(shuō)沒有任何東西是屬于x而不屬于y的,也就是說(shuō)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來(lái)表示,可以這樣理解這個(gè)式子意味著如果x=1,那么y=1。在這里一方面我們可以把"如果x,那么"理解為等同于前面的這樣一句話"所有的x都是y",當(dāng)然這兩者有一個(gè)區(qū)別,現(xiàn)在的xy表示的是命題,而原來(lái)的xy表示的則是類概念。以今天的觀點(diǎn)來(lái)看,前者是命題演算,后者是謂詞演算。但是如果從另一個(gè)方面,重新考慮這句話,比如x=1表示命題x為真,x=0表示命題x為假,xy=1表示xy,只有xy均為1xy=1,如果x=0y=0xy=0,這點(diǎn)又與普通代數(shù)相一致。從這個(gè)方向思考下去,就可以看到今天的布爾代數(shù)的基本面貌了,上面的這個(gè)定義正是與運(yùn)算。

 

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

 

 

今天的布爾代數(shù)

 

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

 

AND | 1 0-----------------------1 | 1 00 | 0 0

 

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

 

OR | 1 0-----------------------1 | 1 10 | 1 0

 

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

 

NOT |--------------1 | 00 | 1

 

這張表說(shuō)明 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ù)來(lái)實(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í)和理解上帝的語(yǔ)言:數(shù)學(xué)。

 

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

 

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

 

弗雷格的突破與絕望

 

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

 

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

 

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

 

弗雷格希望可以自然數(shù)提出一種純粹邏輯的理論,從而證明算術(shù),微積分乃至一切數(shù)學(xué)都可以看成邏輯的一個(gè)分支。于是弗雷格便希望可以用純邏輯的術(shù)語(yǔ)來(lái)定義自然數(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)該是正常的。無(wú)論哪個(gè)結(jié)果都導(dǎo)致了矛盾。實(shí)際上羅素構(gòu)造這個(gè)悖論的方法,與之后哥德爾,圖靈構(gòu)造不可判定命題卻有著神似的地方。然而這一矛盾卻表明弗雷格構(gòu)造的算術(shù)體系所基于的那些前提是靠不住的,并給弗雷格帶來(lái)了巨大的打擊。

 

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

 

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

 

康托爾,對(duì)無(wú)限的探索

 

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

 

對(duì)于我們普通人來(lái)說(shuō),最有用的大概是康托爾在證明實(shí)數(shù)與自然數(shù)基數(shù)不同的過(guò)程中所采用的對(duì)角線方法,這種方法是1891年,康托爾在一篇4頁(yè)的論文中發(fā)表的。而對(duì)角線方法,在以后的故事中仍然會(huì)被用到,它將會(huì)被哥德爾用來(lái)解決一致性問(wèn)題時(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ù)集來(lái)看,我們可以發(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)注到無(wú)限的數(shù)目特殊性的人,早在17世紀(jì),萊布尼茨就發(fā)現(xiàn)偶數(shù)和自然數(shù)是一一對(duì)應(yīng)的,正如他所說(shuō):對(duì)于任何一個(gè)數(shù),都存在一個(gè)與之對(duì)應(yīng)的偶數(shù),那就是它的二倍。因此所有數(shù)的數(shù)目并不比偶數(shù)的數(shù)目更多,也就是說(shuō)整體沒有部分大。但是他得出了這樣一個(gè)結(jié)論:所有自然數(shù)的數(shù)目這一概念是不一致的,討論一個(gè)無(wú)限集中元素的數(shù)目是沒有意義的。但是康托了選擇了另一條路,他承認(rèn)某些無(wú)限集將與它的一個(gè)子集具有相同的元素?cái)?shù)目。正是基于這樣一個(gè)大膽的選擇,他才創(chuàng)立了關(guān)于無(wú)限的新理論。

 

當(dāng)康托爾提出這些觀點(diǎn)之后,立刻引來(lái)了各方面的責(zé)難。與弗雷格類似,人們發(fā)現(xiàn)用康托爾的超限數(shù)進(jìn)行不加限制的推理會(huì)導(dǎo)致荒謬的結(jié)果。比如如果存在一個(gè)由所有基數(shù)組成的集合,那么它的基數(shù)該是多少呢?它必須比所有基數(shù)都大,但一個(gè)基數(shù)又怎么可能比所有基數(shù)都大呢?后來(lái)羅素又指出這樣的一個(gè)問(wèn)題:是否存在一個(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)系起來(lái)。而關(guān)于這個(gè)悖論的討論和思考,則引發(fā)了數(shù)學(xué)史上的第三次危機(jī)。

 

大衛(wèi)希爾伯特

 

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

 

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

 

后來(lái)在1928年的國(guó)際數(shù)學(xué)家大會(huì)上,希爾伯特又提出一個(gè)關(guān)于形式系統(tǒng)的問(wèn)題,這個(gè)系統(tǒng)建立在把一階邏輯應(yīng)用于現(xiàn)在被稱為皮亞諾算術(shù)或者PA的自然數(shù)公理系統(tǒng)的基礎(chǔ)之上。希爾伯特希望可以證明PA是完備的,也就是說(shuō)任何一個(gè)可以在PA中表出的命題或者可以在PA中被證明為真,或者可以被證明為假。兩年后,這個(gè)問(wèn)題被一個(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的一致性,然而就是在這樣的努力中失敗了。哥德爾開始思考這些問(wèn)題時(shí),他重新思考了從外部而不是從內(nèi)部考察一個(gè)系統(tǒng)的意思。從外部看,這些系統(tǒng)包含著符號(hào)串之間的關(guān)系。從內(nèi)部看,這些系統(tǒng)能夠表達(dá)關(guān)于不同數(shù)學(xué)對(duì)象的命題。哥德爾通過(guò)給符號(hào)串用自然數(shù)編碼,將外部帶到了內(nèi)部。

 

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

 

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

 

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

 

U說(shuō)某個(gè)特殊命題在PM中不可證。

那個(gè)特殊的命題就是U本身。

因此,U說(shuō)"UPM中不可證"

 

如果我們承認(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)來(lái)看U是真的。

 

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

 

圖靈和圖靈機(jī)

 

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

 

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

 

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

 

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

 

然后他做出了如下抽象:計(jì)算通過(guò)在一條被劃分成方格的紙帶上寫下符號(hào)來(lái)進(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ī)器上來(lái)回移動(dòng)。關(guān)鍵之處在于圖靈對(duì)于計(jì)算概念的分析,通過(guò)某種算法程序可計(jì)算的任何東西都可以通過(guò)一臺(tái)圖靈機(jī)來(lái)計(jì)算。因此如果我們可以證明某些任務(wù)無(wú)法用圖靈機(jī)完成,那么我們就可以說(shuō)沒有任何算法可以完成這項(xiàng)任務(wù)。這就是圖靈證明判定問(wèn)題不存在算法的方法。

 

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

 

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

 

圖靈機(jī)本身可以是自然數(shù)編碼表示,這樣它也作為自身的輸入。實(shí)際上有些輸入會(huì)使圖靈機(jī)停止下來(lái),另一些則不會(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è)問(wèn)題:

 

找到一種算法,判定一個(gè)給定的自然數(shù)是否屬于集合D

 

這就是一個(gè)不可解問(wèn)題的例子。首先如果存在這樣的一個(gè)算法,我們就能找到這樣的一個(gè)圖靈機(jī),但是我可以改造一下這個(gè)圖靈機(jī),把以下兩個(gè)五元組加入到這個(gè)圖靈機(jī):F 0:-> F F :-> F。對(duì)于這個(gè)新的改進(jìn)的圖靈機(jī)來(lái)說(shuō),如果輸入的數(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è)算法。由此可知判斷問(wèn)題在算法上是不可解的。

 

為了驗(yàn)證自己工作的有效性,圖靈又提出了通用機(jī)模型,通用機(jī)包含了圖靈機(jī)代碼以及待處理的數(shù)據(jù)。而這剛好對(duì)應(yīng)著我們今天的機(jī)器,程序與數(shù)據(jù)的概念。也為存儲(chǔ)程序計(jì)算機(jī)提供了一個(gè)模型。正是圖靈在證明判定問(wèn)題的不可解性是,對(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)出來(lái)。在這個(gè)報(bào)告里,提出了存儲(chǔ)程序的概念,也就是沿用至今的馮諾依曼結(jié)構(gòu),實(shí)際上它的革命性不在于存儲(chǔ)程序而是通用性,存儲(chǔ)程序只是達(dá)到這一目的的一種手段。1950年,圖靈又發(fā)表了他的經(jīng)典論文,計(jì)算機(jī)與智能,提出了著名的圖靈測(cè)試來(lái)測(cè)試計(jì)算機(jī)是否具有智能。195467日,圖靈咬了一個(gè)浸過(guò)氰化物的蘋果,結(jié)束了自己的生命。而他的通用機(jī)思想?yún)s延續(xù)到今天。

 

總結(jié)

 

實(shí)際這些文章是在我看過(guò)了,<<邏輯的引擎>>之后,對(duì)里面設(shè)計(jì)的數(shù)學(xué)問(wèn)題的一個(gè)總結(jié),剔除了關(guān)于科學(xué)家們生平逸事的內(nèi)容。而是專注于那些純粹的思想是怎樣的,以及怎樣產(chǎn)生發(fā)展和被解決的。而這樣的一些思想,逐步的稱為計(jì)算機(jī)科學(xué)背后的基礎(chǔ)。從這里,或許可以稍微理解這些偉大的人物和思想,是如何于計(jì)算機(jī)的起源產(chǎn)生關(guān)系的。

責(zé)任編輯:向太陽(yáng)
特別申明:

1、本文只代表作者個(gè)人觀點(diǎn),不代表本站觀點(diǎn),僅供大家學(xué)習(xí)參考;

2、本站屬于非營(yíng)利性網(wǎng)站,如涉及版權(quán)和名譽(yù)問(wèn)題,請(qǐng)及時(shí)與本站聯(lián)系,我們將及時(shí)做相應(yīng)處理;

3、歡迎各位網(wǎng)友光臨閱覽,文明上網(wǎng),依法守規(guī),IP可查。

熱點(diǎn)排行
  • 一周
  • 一月
  • 半年
  • 建言點(diǎn)贊
  • 一周
  • 一月
  • 半年
  • 周新城:中央黨校教授董德剛,不懂馬列卻狠批馬列!
    -->

    圖片新聞

    友情鏈接
    備案/許可證編號(hào):京ICP備15015626號(hào)-1 昆侖策研究院 版權(quán)所有 舉報(bào)郵箱:kunlunce@yeah.net