<kbd id="afajh"><form id="afajh"></form></kbd>
<strong id="afajh"><dl id="afajh"></dl></strong>
    2. 

    <del id="afajh"><form id="afajh"></form></del>
    

    5. 

        1. <th id="afajh"><progress id="afajh"></progress></th>

          <b id="afajh"><abbr id="afajh"></abbr></b>
          <th id="afajh"><progress id="afajh"></progress></th>
          誰才是百年計算機的數(shù)學(xué)靈魂：萊布尼茨、圖靈還是希爾伯特？
          共
                8436字，需瀏覽
                    17分鐘
                
           ·
          2020-11-17 20:06
          
                    

                    

                    
                    
                    

          ??新智元報道??
          來源：算法與數(shù)學(xué)之美
          編輯：SF
          【新智元導(dǎo)讀】這些探索和研究在當時實際并不是為了計算機產(chǎn)生而進行的，絕大多數(shù)只是做了一個無意的鋪墊。

          雖然計算機的出現(xiàn)，不到百年，然而為了它的出現(xiàn)，所進行的探索和研究，早已經(jīng)歷經(jīng)數(shù)百年的歷史。

          當然準確的說，這些探索和研究在當時實際并不是為了計算機產(chǎn)生而進行的，絕大多數(shù)只是做了一個無意的鋪墊。

          或許我們并不熟悉這樣的一個過程，老實說現(xiàn)代的大學(xué)教育中也很少提及計算機出現(xiàn)之前的那些歷史。

          實際上，了解這樣的一個過程，更有助于我們理解一個事物是如何產(chǎn)生出來，它背后的科學(xué)原理又是如何，讓我們可以透過復(fù)雜的電路外表，接觸到最本質(zhì)的東西，可以讓我們除了對科學(xué)家們的工作表示贊嘆之外，也可以深入他們當初的思想過程，近距離地進行跨越時間和空間的溝通。

          這對于我們自己應(yīng)該如何思考問題，創(chuàng)造性地提出自己的想法也是有所幫助的。


          我們已經(jīng)了解到這樣的一些人物，喬治.布爾,康托，哥德爾，圖靈，馮諾依曼。

          而我們的離散數(shù)學(xué)的教學(xué)中，本身太注重于知識本身的學(xué)習(xí)，而忽略了知識是如何被發(fā)現(xiàn)產(chǎn)生出來，以及不同的知識之間曾經(jīng)的淵源和啟發(fā)關(guān)系。

          而對于啟迪思想來說，后者顯然更為有力。


          萊布尼茨之夢

          早在17世紀的萊布尼茨就有一個偉大的構(gòu)想，他希望可以將人類的思維像代數(shù)運算那樣符號化，規(guī)則化，從而讓笨的人通過掌握這樣的規(guī)則變得聰明，更進一步的制造出可以進行思維運算的機器，將人類從思考中解放。

          從萊布尼茨為微積分所確定的依然在今天被沿用的符號中，我們可以看出他對符號具有良好的感覺，通過選擇良好的符號，可以大大的簡化運算的復(fù)雜性，甚至將這樣的運算變成一種天然的過程。

          除了構(gòu)想之外，萊布尼茨本身為了發(fā)展一種邏輯演算也進行了很多嘗試，他得到的一些結(jié)果已經(jīng)具有后來布爾的邏輯代數(shù)的雛形。



          布爾的邏輯代數(shù)

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

          在早期的研究中，布爾就已經(jīng)認識到符號的力量，代數(shù)的力量正源于代表著量和運算的符號在幾條基本規(guī)則的支配下體現(xiàn)出來的。

          后來，他開始思考能否將邏輯推理也像代數(shù)那樣用符號和幾條基本規(guī)則就可以完全表達。


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

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

          繼續(xù)考慮下去，如果xx=x在普通的代數(shù)中意味著什么呢？

          xx=x，意味著x=1或者0.可以看到如果xx=x作為邏輯代數(shù)的基本規(guī)則，放在普通代數(shù)中意味著x=0或者1，那么邏輯代數(shù)是否意味著是01的普通代數(shù)呢。

          于是布爾得到一個基本原理，如果僅僅限于01，邏輯代數(shù)就變成了普通代數(shù)。關(guān)于這一點的思考，對于二進制運算的在邏輯代數(shù)中的主導(dǎo)作用具有很大的啟發(fā)意義。

          如果限于01，那么01在我們的邏輯代數(shù)中代表的意思又是什么呢。

          我們之前看到可以用x表示某個類，對應(yīng)地那么0可以解釋成沒有任何東西屬于它的類，1可以解釋成包含所有對象的全體。

          同時布爾又開始考慮普通代數(shù)中的+-在邏輯代數(shù)中的意義，x+y可以表示具有x和y兩種屬性的對象集合，x-y表示具有x屬性同時不具有y屬性的對象集合。

          考慮了這樣的一些意義之后，接下來再看xx=x=> x-xx = 0 => x(1-x) = 0

          現(xiàn)在我們以邏輯代數(shù)的觀點看這個式子，它體現(xiàn)了這樣一個含義：          沒有任何東西可以同時屬于又不屬于某個類。

          這點讓布爾十分振奮，因為這剛好體現(xiàn)了亞里士多德的排中律，這就使他確信自己找對了路子。

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


          所有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來表示,可以這樣理解這個式子意味著如果x=1，那么y=1。

          在這里一方面我們可以把"如果x，那么"理解為等同于前面的這樣一句話"所有的x都是y",當然這兩者有一個區(qū)別，現(xiàn)在的x，y表示的是命題，而原來的x，y表示的則是類概念。

          以今天的觀點來看，前者是命題演算，后者是謂詞演算。

          但是如果從另一個方面，重新考慮這句話，比如x=1表示命題x為真，x=0表示命題x為假，xy=1表示x且y，只有x，y均為1，xy=1，如果x=0或y=0，xy=0，這點又與普通代數(shù)相一致。

          從這個方向思考下去，就可以看到今天的布爾代數(shù)的基本面貌了，上面的這個定義正是與運算。

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


          今天的布爾代數(shù)

          回到今天，我們再看布爾再把邏輯轉(zhuǎn)變成代數(shù)的過程中，所產(chǎn)生的邏輯代數(shù)在今天的計算機中扮演著什么樣的作用。

          布爾代數(shù)只有1和0兩個元素，not and or三種運算，用幾張真值表就可以表達清楚。

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

          這張表說明如果 AND 運算的兩個元素有一個是?0，則運算結(jié)果總是?0。如果兩個元素都是 1，運算結(jié)果是 1。

          例如，“太陽從西邊升起”這個判斷是假的(0),“水可以流動”這個判斷是真的（1），那么，“太陽從西邊升起并且水可以流動”就是假的（0）。

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

          這張表說明如果OR運算的兩個元素有一個是 1，則運算結(jié)果總是 1。如果兩個元素都是?0，運算結(jié)果是?0。

          比如說，“張三是比賽第一名”這個結(jié)論是假的（0），“李四是比賽第一名”是真的（1），那么“張三或者李四是第一名”就是真的（1）。

          NOT |
          --------------
          1 | 0
          0 | 1

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

          如此簡單的運算，實際上當時的布爾也不會想到它會被運用到計算機中，直到1938 年香農(nóng)在他的碩士論文中指出用布爾代數(shù)來實現(xiàn)開關(guān)電路，使得布爾代數(shù)成為數(shù)字電路的基礎(chǔ)。

          所有的數(shù)學(xué)和邏輯運算，加、減、乘、除、乘方、開方等等，全部能轉(zhuǎn)換成二值的布爾運算。

          用計算的力量改變世界是每一個程序員的夢想，YaK團隊抱著對教育的敬仰和熱忱，開發(fā)了有趣的YaK編程工具以及配套的系統(tǒng)化教學(xué)課程。

          讓孩子可以用編程去學(xué)習(xí)和理解上帝的語言：數(shù)學(xué)。

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


          弗雷格的突破與絕望

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

          其中概念演算，將普通數(shù)學(xué)中的一切演繹推理都包含在內(nèi)，成為第一個完備的邏輯體系。布爾以普通代數(shù)為基礎(chǔ)，用代數(shù)符號來表示邏輯關(guān)系。

          與此相反，弗雷格想以他的邏輯為基礎(chǔ)而把代數(shù)構(gòu)造出來。

          實際上這成為日后一個重要的學(xué)派"邏輯主義",在他們看來邏輯與數(shù)學(xué)的關(guān)系就像一門學(xué)科的基本部分和高等部分之間的關(guān)系。

          弗雷格的邏輯體系，表現(xiàn)在今天就是我們數(shù)理邏輯中的命題演算和謂詞演算(用數(shù)學(xué)的方法研究關(guān)于推理、證明等問題的學(xué)科就叫做數(shù)理邏輯。也叫做符號邏輯)。

          弗雷格第一次用精確的句法構(gòu)造出形式化的人工語言，使得邏輯推理表示為機械演算即所謂的推理規(guī)則成為可能。從這個觀點看，概念文字是我們今天使用的計算機程序設(shè)計語言的前身。

          弗雷格希望可以自然數(shù)提出一種純粹邏輯的理論，從而證明算術(shù)，微積分乃至一切數(shù)學(xué)都可以看成邏輯的一個分支。

          于是弗雷格便希望可以用純邏輯的術(shù)語來定義自然數(shù)，然后再用他的邏輯導(dǎo)出它們的性質(zhì)。例如3這個數(shù)將被解釋為邏輯的一部分。

          弗雷格的思想是把3定義為所有元素數(shù)為3的集合的集合。實際上這就是《算術(shù)的基礎(chǔ)--對數(shù)概念的邏輯數(shù)學(xué)研究》這部著作的主要內(nèi)容。

          然而正是這樣的一些工作，1902年，年輕的伯特蘭.羅素據(jù)此提出那個著名的羅素悖論。弗雷格的算術(shù)使用了集合的集合這樣一種概念。

          羅素指出，用集合的集合進行推理很容易導(dǎo)致矛盾。

          羅素的悖論可以這樣描述：如果一個集合是它自身的一個成員，那么就把集合成為異常的，否則它就是正常的。那么由所有正常集合組成的集合是正常還是異常的呢？

          如果是正常的，那么它應(yīng)該包含自身，這樣它就應(yīng)該是異常的。如果是異常的，那么它就不會包含自身，這樣它就應(yīng)該是正常的。

          無論哪個結(jié)果都導(dǎo)致了矛盾。實際上羅素構(gòu)造這個悖論的方法，與之后哥德爾，圖靈構(gòu)造不可判定命題卻有著神似的地方。

          然而這一矛盾卻表明弗雷格構(gòu)造的算術(shù)體系所基于的那些前提是靠不住的，并給弗雷格帶來了巨大的打擊。

          雖然弗雷格的邏輯已經(jīng)很完備，但仍然具有一些局限性。他的規(guī)則并沒有提供判定某個結(jié)論能否從給定的前提中推導(dǎo)出來的計算步驟。另外能否找到一種計算方法，它能夠說明在弗雷格的邏輯中某一推理是正確的呢？

          其結(jié)果是這樣一則證明：沒有這樣的一般方法存在。然而正是在證明這樣一條否定性的結(jié)論過程中，阿蘭圖靈發(fā)現(xiàn)原則上可以設(shè)計出一種通用機，它可以執(zhí)行任何可能的計算。

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


          康托爾，對無限的探索

          康托爾進入無限的世界，開始無限的數(shù)目的研究。

          他發(fā)現(xiàn)自然數(shù)與實數(shù)具有不同的基數(shù)，以及由此提出的連續(xù)統(tǒng)假設(shè)，即實數(shù)和自然數(shù)之間不存在具有其他基數(shù)的集合。

          這也是1900年，希爾伯特提出的23個問題中的第一問題。

          這個問題直到今天并未完全解決，1938年哥德爾和1963年保羅科恩的重大發(fā)現(xiàn)表明，如果連續(xù)統(tǒng)假設(shè)問題可以被解決，就必須超越普通數(shù)學(xué)的方法。

          對于我們普通人來說，最有用的大概是康托爾在證明實數(shù)與自然數(shù)基數(shù)不同的過程中所采用的對角線方法，這種方法是1891年，康托爾在一篇4頁的論文中發(fā)表的。

          而對角線方法，在以后的故事中仍然會被用到，它將會被哥德爾用來解決一致性問題時構(gòu)造系統(tǒng)內(nèi)不可證命題，然后阿蘭.圖靈又再次使用了哥德爾的方法構(gòu)造出了不可判定命題。

          而關(guān)于連續(xù)統(tǒng)假設(shè)的研究也引發(fā)了關(guān)于圖靈機的構(gòu)想。

          現(xiàn)在我們可以看到康托爾的工作與計算機的起源在這里產(chǎn)生了聯(lián)系。

          關(guān)于對角線方法，我們從自然數(shù)集來看，我們可以發(fā)現(xiàn)自然數(shù)與自然數(shù)的子集組成的集合之間具有不同的基數(shù)。

          假設(shè)我們把自然數(shù)與不同的自然數(shù)子集建立一個對應(yīng)關(guān)系，1: M1 2: M2....，采用對角線方法，我們總是可以構(gòu)造出一個新的自然數(shù)集。

          它沒有任何自然數(shù)與之對應(yīng)，我們這樣產(chǎn)生這個新的自然數(shù)集：如果i屬于Mi,那么排除i，否則包含i，容易看到這樣產(chǎn)生的一個集合不同于任何的Mi。

          可見由一切自然數(shù)集組成的集合的基數(shù)要大于自然數(shù)的基數(shù)。

          實際上康托爾并不是第一個關(guān)注到無限的數(shù)目特殊性的人，早在17世紀，萊布尼茨就發(fā)現(xiàn)偶數(shù)和自然數(shù)是一一對應(yīng)的，正如他所說：對于任何一個數(shù)，都存在一個與之對應(yīng)的偶數(shù)，那就是它的二倍。

          因此所有數(shù)的數(shù)目并不比偶數(shù)的數(shù)目更多，也就是說整體沒有部分大。但是他得出了這樣一個結(jié)論：所有自然數(shù)的數(shù)目這一概念是不一致的，討論一個無限集中元素的數(shù)目是沒有意義的。

          但是康托了選擇了另一條路，他承認某些無限集將與它的一個子集具有相同的元素數(shù)目。

          正是基于這樣一個大膽的選擇，他才創(chuàng)立了關(guān)于無限的新理論。

          當康托爾提出這些觀點之后，立刻引來了各方面的責(zé)難。與弗雷格類似，人們發(fā)現(xiàn)用康托爾的超限數(shù)進行不加限制的推理會導(dǎo)致荒謬的結(jié)果。

          比如如果存在一個由所有基數(shù)組成的集合，那么它的基數(shù)該是多少呢？它必須比所有基數(shù)都大，但一個基數(shù)又怎么可能比所有基數(shù)都大呢？

          后來羅素又指出這樣的一個問題：是否存在一個所有集合的集合？如果存在，那么倘若把對角線方法應(yīng)用于它，會出現(xiàn)什么結(jié)果？

          這樣我們會得到一個不同于所有那些已經(jīng)擁有標簽的集合的集合。正是在考慮這種情況時，羅素發(fā)現(xiàn)他那個關(guān)于由一切不是自身的集合組成的集合的著名悖論，也就是他向弗雷格傳達的那個悖論。

          這里我們看到，弗雷格和康托爾之間被羅素悖論聯(lián)系起來。而關(guān)于這個悖論的討論和思考，則引發(fā)了數(shù)學(xué)史上的第三次危機。



          大衛(wèi)希爾伯特

          希爾伯特是20世紀的數(shù)學(xué)領(lǐng)袖，1900年他在數(shù)學(xué)家大會上指出的23個問題，其中第二個便是關(guān)于算術(shù)一致性的問題。

          希爾伯特綱領(lǐng)所提出的主要問題就是算術(shù)一致性問題。為了解決這個問題，希爾伯特發(fā)展出了元數(shù)學(xué)，一致性證明將在元數(shù)學(xué)內(nèi)部完成。

          1928年，希爾伯特和他的學(xué)生阿克曼出版了一本邏輯課本，書中提出了關(guān)于弗雷格<<概念文字>>的基本邏輯(后來被稱為一階邏輯)兩個主要問題，一個就是，證明一階邏輯的完備性，即任何一個從外部看來有效的公式都可以只用課本里提出規(guī)則從系統(tǒng)內(nèi)部導(dǎo)出。

          第二個問題以希爾伯特的判定問題而聞名，即對于一個一階邏輯的公式，如果找到一種方法，可以在定義明確有限步驟內(nèi)判定這個公式是有效的。
          這兩個問題分別為哥德爾和圖靈解決，而在解決第二個問題的過程中，圖靈提出了圖靈機的概念。

          后來在1928年的國際數(shù)學(xué)家大會上，希爾伯特又提出一個關(guān)于形式系統(tǒng)的問題，這個系統(tǒng)建立在把一階邏輯應(yīng)用于現(xiàn)在被稱為皮亞諾算術(shù)或者PA的自然數(shù)公理系統(tǒng)的基礎(chǔ)之上。

          希爾伯特希望可以證明PA是完備的，也就是說任何一個可以在PA中表出的命題或者可以在PA中被證明為真，或者可以被證明為假。兩年后，這個問題被一個叫哥德爾的年輕人解決了，但答案卻完全不像希爾伯特料想的那樣。


          哥德爾完備性定理

          希爾伯特在20世紀20年代介紹了他的元數(shù)學(xué)綱領(lǐng)：一致性有待證明的公理將被包含在一個形式邏輯系統(tǒng)之內(nèi)，而證明僅僅是有限數(shù)目的符號的一種排列而已。

          當希爾伯特開始思考希爾伯特綱領(lǐng)時，希爾伯特的學(xué)生阿克曼和馮諾依曼似乎正在朝著用有限性方法證明PA的一致性的方向大步邁進。

          他們二人都已經(jīng)為PA的一個有限的子系統(tǒng)找到了這樣的證明，成功似乎指日可待。

          這樣哥德爾開始試圖將算術(shù)一致性還原為PA的一致性，然而就是在這樣的努力中失敗了。哥德爾開始思考這些問題時，他重新思考了從外部而不是從內(nèi)部考察一個系統(tǒng)的意思。

          從外部看，這些系統(tǒng)包含著符號串之間的關(guān)系。從內(nèi)部看，這些系統(tǒng)能夠表達關(guān)于不同數(shù)學(xué)對象的命題。哥德爾通過給符號串用自然數(shù)編碼，將外部帶到了內(nèi)部。

          哥德爾發(fā)現(xiàn)存在這樣的命題，它們從系統(tǒng)外部看是真命題，但無法在系統(tǒng)內(nèi)部得到證明。于是他得出了一個非凡結(jié)論：一種有意義的數(shù)學(xué)真理的觀念不僅是存在的，而且其范圍還超出了任何給定的形式系統(tǒng)的證明能力。

          在1931年，他發(fā)表的論文<<論?<數(shù)學(xué)原理>及有關(guān)系統(tǒng)的形式不可判定命題>>中，他選擇對形式系統(tǒng)PM給出了他的結(jié)果，從而說明即使強邏輯系統(tǒng)也不可能把全部數(shù)學(xué)真理包含在內(nèi)。

          在哥德爾的證明中，關(guān)鍵的一步在于他證明了：一個自然數(shù)作為PM中可證命題的一個代碼，這一性質(zhì)本身可以在PM中表示出來。

          根據(jù)這一事實，哥德爾可以在PM中構(gòu)造出一些命題，這些命題可以被看做表達了這樣一個斷言，即某些命題在PM中是不可證的。也就是說他可以構(gòu)造出一個命題A，該命題經(jīng)譯碼后可以斷言某一命題B在PM中是不可證的。

          現(xiàn)在，在沒有獲知密碼的人看來，命題A不過是一串符號而已，但是通過代碼，神秘性就消失了：A表示這樣一個命題，即某個符號串B表示在PM中一個不可證的命題。A和B通常是不同的命題，哥德爾問，它們是否有可能是相同的呢？

          事實上它們可以是相同的，哥德爾可以利用對角線方法證明這個結(jié)論。

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

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

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

          U是真的。假定它是假的，那么它表述的內(nèi)容就是假的，因此它就是不是不可證的，而一定是可證的，從而是真的，這與開始假定U是假的矛盾，所以它一定是真的。因為它是真的，所以它表述的內(nèi)容為真，所以它在PM中不可證。

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

          另一方面，在PM內(nèi)部，我們可以證明：如果PM是一致的，那么U。因此正是PM是一致的這一個假定，才使U在PM內(nèi)部得不到證明。既然我們知道U在PM內(nèi)部是不可證的，我們就必須得出結(jié)論說，PM的一致性在PM中不可證。

          而希爾伯特的主要目的就在于：用于被認為構(gòu)成PM的一個非常有限的子集的有限性方法來證明像PM這樣的系統(tǒng)的一致性。然而哥德爾證明了，即使就PM的全部能力而言，它也不足以證明自身的一致性。于是希爾伯特綱領(lǐng)走到了盡頭。

          圖靈和圖靈機

          在哥德尓1930年的博士論文中證明了弗雷格的規(guī)則是完備的，這樣就回答了希爾伯特1928年提出的第一個問題。

          而第二個問題即判定問題，在哥德爾的工作發(fā)表之后，人們很難想象存在這樣的判定算法，于是阿蘭圖靈開始思考如果證明這樣的算法是不存在的。

          圖靈采取了這樣的一條道路，他首先分析了人的計算過程。通過丟掉非本質(zhì)的細節(jié)，將這些計算活動局限在少數(shù)幾種極為簡單的基本操作上。

          然后圖靈說明人可以被一個能夠執(zhí)行這些基本操作的機器所替代。然后只要證明僅僅執(zhí)行那些基本操作的機器不可能判定一個給定的結(jié)論是否可以用弗雷格的規(guī)則從給定的前提中導(dǎo)出，這樣他就能夠下結(jié)論說，判定問題的算法是不存在的。

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

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

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

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

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

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

          圖靈機本身可以是自然數(shù)編碼表示，這樣它也作為自身的輸入。實際上有些輸入會使圖靈機停止下來，另一些則不會。

          這樣一臺圖靈機就具有一些停機集合。如果我們考慮把一臺圖靈機的停機集合組成了一個包裹，并且認為那臺機器的碼數(shù)就是這個包裹的標簽。對角線方法允許我們構(gòu)造出一個與圖靈機的任何停機集合都不同的自然數(shù)集合，我們稱之為D。

          方法是這樣的，我們考慮把圖靈機的編碼作為自身的輸入，如果它的編碼數(shù)不屬于自身的停機集合，那么我們就把它加入D。而集合D則不是任何圖靈機的停機集合。

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

          這就是一個不可解問題的例子。首先如果存在這樣的一個算法，我們就能找到這樣的一個圖靈機，但是我可以改造一下這個圖靈機，把以下兩個五元組加入到這個圖靈機：F 0:口-> F 和 F 口:口-> F。

          對于這個新的改進的圖靈機來說，如果輸入的數(shù)屬于D那么那么機器就會像以前一樣運轉(zhuǎn)，并輸出1而告終，如果輸入的數(shù)不屬于D，那這臺機器將永遠向右移動。這樣我們就找到了一臺圖靈機它的停機集合剛好就是D。

          于是與我們的對角線方法矛盾。所以并不存在這樣的一個算法。由此可知判斷問題在算法上是不可解的。

          為了驗證自己工作的有效性，圖靈又提出了通用機模型，通用機包含了圖靈機代碼以及待處理的數(shù)據(jù)。

          而這剛好對應(yīng)著我們今天的機器，程序與數(shù)據(jù)的概念。也為存儲程序計算機提供了一個模型。正是圖靈在證明判定問題的不可解性是，對計算概念的分析以及對通用機的發(fā)現(xiàn)促使了計算機的產(chǎn)生。

          1945年圖靈又發(fā)表了他那篇著名的ACE(自動計算機)報告。這是對計算機的一次完整的描述，一直到邏輯電路圖。也就是在這時馮諾依曼提出了他著名的"關(guān)于EDVAC的報告草案"，它實際上主張將要建造的EDVAC作為圖靈通用機的一個物理模型實現(xiàn)出來。

          在這個報告里，提出了存儲程序的概念，也就是沿用至今的馮諾依曼結(jié)構(gòu)，實際上它的革命性不在于存儲程序而是通用性，存儲程序只是達到這一目的的一種手段。

          1950年，圖靈又發(fā)表了他的經(jīng)典論文，計算機與智能，提出了著名的圖靈測試來測試計算機是否具有智能。

          1954年6月7日，圖靈咬了一個浸過氰化物的蘋果，結(jié)束了自己的生命，而他的通用機思想?yún)s延續(xù)到今天。





          
                
          瀏覽
                    34
          點贊
    
          評論
    
          收藏
    
          分享
        
          手機掃一掃分享
          分享
    
          
        舉報
    
          評論
          圖片
          表情
          推薦
        
          點贊
    
          評論
    
          收藏
    
          分享
        
          手機掃一掃分享
          分享
    
          
        舉報
    
          

          <kbd id="afajh"><form id="afajh"></form></kbd>
          <strong id="afajh"><dl id="afajh"></dl></strong>
            2. 

            <del id="afajh"><form id="afajh"></form></del>
            

            5. 

                1. <th id="afajh"><progress id="afajh"></progress></th>

                  <b id="afajh"><abbr id="afajh"></abbr></b>
                  <th id="afajh"><progress id="afajh"></progress></th>
                  

中文字幕无码在线
|
大香蕉精品在线观看
|
久久大鸡巴再线观看
|
午夜看黄
|
波多野结衣无码一区二区
|