新智元報導
來源：算法與數學之美
編輯：SF
【新智元導讀】這些探索和研究在當時實際並不是為了計算機產生而進行的，絕大多數只是做了一個無意的鋪墊。
雖然計算機的出現，不到百年，然而為了它的出現，所進行的探索和研究，早已經歷經數百年的歷史。
當然準確的說，這些探索和研究在當時實際並不是為了計算機產生而進行的，絕大多數只是做了一個無意的鋪墊。
或許我們並不熟悉這樣的一個過程，老實說現代的大學教育中也很少提及計算機出現之前的那些歷史。
實際上，了解這樣的一個過程，更有助於我們理解一個事物是如何產生出來，它背後的科學原理又是如何，讓我們可以透過複雜的電路外表，接觸到最本質的東西，可以讓我們除了對科學家們的工作表示讚嘆之外，也可以深入他們當初的思想過程，近距離地進行跨越時間和空間的溝通。
這對於我們自己應該如何思考問題，創造性地提出自己的想法也是有所幫助的。
我們已經了解到這樣的一些人物，喬治.布爾,康託，哥德爾，圖靈，馮諾依曼。
而我們的離散數學的教學中，本身太注重於知識本身的學習，而忽略了知識是如何被發現產生出來，以及不同的知識之間曾經的淵源和啟發關係。
而對於啟迪思想來說，後者顯然更為有力。
萊布尼茨之夢
早在17世紀的萊布尼茨就有一個偉大的構想，他希望可以將人類的思維像代數運算那樣符號化，規則化，從而讓笨的人通過掌握這樣的規則變得聰明，更進一步的製造出可以進行思維運算的機器，將人類從思考中解放。
從萊布尼茨為微積分所確定的依然在今天被沿用的符號中，我們可以看出他對符號具有良好的感覺，通過選擇良好的符號，可以大大的簡化運算的複雜性，甚至將這樣的運算變成一種天然的過程。
除了構想之外，萊布尼茨本身為了發展一種邏輯演算也進行了很多嘗試，他得到的一些結果已經具有後來布爾的邏輯代數的雛形。
布爾的邏輯代數
19世紀的布爾，將邏輯代數化，發展出了邏輯代數成為後來計算機內部運算的邏輯基礎。
在早期的研究中，布爾就已經認識到符號的力量，代數的力量正源於代表著量和運算的符號在幾條基本規則的支配下體現出來的。
後來，他開始思考能否將邏輯推理也像代數那樣用符號和幾條基本規則就可以完全表達。
他開始思考我們通常所說的某物具有某種性質，可以用一個類來表示，比如白的是x，綿羊是y，那麼白綿羊就可以用xy來表示，這樣日常生活中的概念開始具有代數的形式，用現代的術語來說上面的xy表示的正是交集。
他又繼續思考，xx表示什麼呢，他發現xx與我們普通的代數運算不同xx依然表示的是x。xx=x實際上成為布爾的邏輯代數的一個基本規則。
繼續考慮下去，如果xx=x在普通的代數中意味著什麼呢？
xx=x，意味著x=1或者0.可以看到如果xx=x作為邏輯代數的基本規則，放在普通代數中意味著x=0或者1，那麼邏輯代數是否意味著是01的普通代數呢。
於是布爾得到一個基本原理，如果僅僅限於01，邏輯代數就變成了普通代數。關於這一點的思考，對於二進位運算的在邏輯代數中的主導作用具有很大的啟發意義。
如果限於01，那麼01在我們的邏輯代數中代表的意思又是什麼呢。
我們之前看到可以用x表示某個類，對應地那麼0可以解釋成沒有任何東西屬於它的類，1可以解釋成包含所有對象的全體。
同時布爾又開始考慮普通代數中的+-在邏輯代數中的意義，x+y可以表示具有x和y兩種屬性的對象集合，x-y表示具有x屬性同時不具有y屬性的對象集合。
考慮了這樣的一些意義之後，接下來再看xx=x=> x-xx = 0 => x(1-x) = 0
現在我們以邏輯代數的觀點看這個式子，它體現了這樣一個含義：沒有任何東西可以同時屬於又不屬於某個類。
這點讓布爾十分振奮，因為這剛好體現了亞里斯多德的排中律，這就使他確信自己找對了路子。
繼續下去，布爾發現三段論也可以用他的邏輯代數來表達。
所有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",當然這兩者有一個區別，現在的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，這點又與普通代數相一致。
從這個方向思考下去，就可以看到今天的布爾代數的基本面貌了，上面的這個定義正是與運算。
布爾的邏輯體系，不僅包含了亞里斯多德的邏輯體系，而且還超越了它，但是仍有無法表達的情形：所有失敗的學生或者是糊塗的或者是懶惰的。
今天的布爾代數
回到今天，我們再看布爾再把邏輯轉變成代數的過程中，所產生的邏輯代數在今天的計算機中扮演著什麼樣的作用。
布爾代數只有1和0兩個元素，not and or三種運算，用幾張真值表就可以表達清楚。
AND | 1 0
---
1 | 1 0
0 | 0 0
這張表說明如果 AND 運算的兩個元素有一個是 0，則運算結果總是 0。如果兩個元素都是 1，運算結果是 1。
例如，「太陽從西邊升起」這個判斷是假的(0),「水可以流動」這個判斷是真的（1），那麼，「太陽從西邊升起並且水可以流動」就是假的（0）。
OR | 1 0
---
1 | 1 1
0 | 1 0
這張表說明如果OR運算的兩個元素有一個是 1，則運算結果總是 1。如果兩個元素都是 0，運算結果是 0。
比如說，「張三是比賽第一名」這個結論是假的（0），「李四是比賽第一名」是真的（1），那麼「張三或者李四是第一名」就是真的（1）。
NOT |
----
1 | 0
0 | 1
這張表說明 NOT 運算把 1 變成 0，把 0 變成 1。比如，如果「象牙是白的」是真的（1），那麼「象牙不是白的」必定是假的（0）。
如此簡單的運算，實際上當時的布爾也不會想到它會被運用到計算機中，直到1938 年香農在他的碩士論文中指出用布爾代數來實現開關電路，使得布爾代數成為數字電路的基礎。
所有的數學和邏輯運算，加、減、乘、除、乘方、開方等等，全部能轉換成二值的布爾運算。
用計算的力量改變世界是每一個程式設計師的夢想，YaK團隊抱著對教育的敬仰和熱忱，開發了有趣的YaK編程工具以及配套的系統化教學課程。
讓孩子可以用編程去學習和理解上帝的語言：數學。
前面我們看到計算起源的數學思想有萊布尼茨，布爾代數。接下來我們看到其他的數學思想在計算中的運用。
弗雷格的突破與絕望
弗雷格的一生主要發表了這樣三本著作：《概念演算--一種模仿算術語言構造的純思維的符號語言》（1879）、《算術的基礎--對數概念的邏輯數學研究》（1884）《算術的基本規律》（l卷 1893，2卷1903）。
其中概念演算，將普通數學中的一切演繹推理都包含在內，成為第一個完備的邏輯體系。布爾以普通代數為基礎，用代數符號來表示邏輯關係。
與此相反，弗雷格想以他的邏輯為基礎而把代數構造出來。
實際上這成為日後一個重要的學派"邏輯主義",在他們看來邏輯與數學的關係就像一門學科的基本部分和高等部分之間的關係。
弗雷格的邏輯體系，表現在今天就是我們數理邏輯中的命題演算和謂詞演算(用數學的方法研究關於推理、證明等問題的學科就叫做數理邏輯。也叫做符號邏輯)。
弗雷格第一次用精確的句法構造出形式化的人工語言，使得邏輯推理表示為機械演算即所謂的推理規則成為可能。從這個觀點看，概念文字是我們今天使用的電腦程式設計語言的前身。
弗雷格希望可以自然數提出一種純粹邏輯的理論，從而證明算術，微積分乃至一切數學都可以看成邏輯的一個分支。
於是弗雷格便希望可以用純邏輯的術語來定義自然數，然後再用他的邏輯導出它們的性質。例如3這個數將被解釋為邏輯的一部分。
弗雷格的思想是把3定義為所有元素數為3的集合的集合。實際上這就是《算術的基礎--對數概念的邏輯數學研究》這部著作的主要內容。
然而正是這樣的一些工作，1902年，年輕的伯特蘭.羅素據此提出那個著名的羅素悖論。弗雷格的算術使用了集合的集合這樣一種概念。
羅素指出，用集合的集合進行推理很容易導致矛盾。
羅素的悖論可以這樣描述：如果一個集合是它自身的一個成員，那麼就把集合成為異常的，否則它就是正常的。那麼由所有正常集合組成的集合是正常還是異常的呢？
如果是正常的，那麼它應該包含自身，這樣它就應該是異常的。如果是異常的，那麼它就不會包含自身，這樣它就應該是正常的。
無論哪個結果都導致了矛盾。實際上羅素構造這個悖論的方法，與之後哥德爾，圖靈構造不可判定命題卻有著神似的地方。
然而這一矛盾卻表明弗雷格構造的算術體系所基於的那些前提是靠不住的，並給弗雷格帶來了巨大的打擊。
雖然弗雷格的邏輯已經很完備，但仍然具有一些局限性。他的規則並沒有提供判定某個結論能否從給定的前提中推導出來的計算步驟。另外能否找到一種計算方法，它能夠說明在弗雷格的邏輯中某一推理是正確的呢？
其結果是這樣一則證明：沒有這樣的一般方法存在。然而正是在證明這樣一條否定性的結論過程中，阿蘭圖靈發現原則上可以設計出一種通用機，它可以執行任何可能的計算。
弗雷格的研究開啟語言哲學的大門，後來人們在尋找證明邏輯推理正確性的過程中，圖靈發現了通用機，也就是今天計算機的數學模型。
康託爾，對無限的探索
康託爾進入無限的世界，開始無限的數目的研究。
他發現自然數與實數具有不同的基數，以及由此提出的連續統假設，即實數和自然數之間不存在具有其他基數的集合。
這也是1900年，希爾伯特提出的23個問題中的第一問題。
這個問題直到今天並未完全解決，1938年哥德爾和1963年保羅科恩的重大發現表明，如果連續統假設問題可以被解決，就必須超越普通數學的方法。
對於我們普通人來說，最有用的大概是康託爾在證明實數與自然數基數不同的過程中所採用的對角線方法，這種方法是1891年，康託爾在一篇4頁的論文中發表的。
而對角線方法，在以後的故事中仍然會被用到，它將會被哥德爾用來解決一致性問題時構造系統內不可證命題，然後阿蘭.圖靈又再次使用了哥德爾的方法構造出了不可判定命題。
而關於連續統假設的研究也引發了關於圖靈機的構想。
現在我們可以看到康託爾的工作與計算機的起源在這裡產生了聯繫。
關於對角線方法，我們從自然數集來看，我們可以發現自然數與自然數的子集組成的集合之間具有不同的基數。
假設我們把自然數與不同的自然數子集建立一個對應關係，1: M1 2: M2....，採用對角線方法，我們總是可以構造出一個新的自然數集。
它沒有任何自然數與之對應，我們這樣產生這個新的自然數集：如果i屬於Mi,那麼排除i，否則包含i，容易看到這樣產生的一個集合不同於任何的Mi。
可見由一切自然數集組成的集合的基數要大於自然數的基數。
實際上康託爾並不是第一個關注到無限的數目特殊性的人，早在17世紀，萊布尼茨就發現偶數和自然數是一一對應的，正如他所說：對於任何一個數，都存在一個與之對應的偶數，那就是它的二倍。
因此所有數的數目並不比偶數的數目更多，也就是說整體沒有部分大。但是他得出了這樣一個結論：所有自然數的數目這一概念是不一致的，討論一個無限集中元素的數目是沒有意義的。
但是康託了選擇了另一條路，他承認某些無限集將與它的一個子集具有相同的元素數目。
正是基於這樣一個大膽的選擇，他才創立了關於無限的新理論。
當康託爾提出這些觀點之後，立刻引來了各方面的責難。與弗雷格類似，人們發現用康託爾的超限數進行不加限制的推理會導致荒謬的結果。
比如如果存在一個由所有基數組成的集合，那麼它的基數該是多少呢？它必須比所有基數都大，但一個基數又怎麼可能比所有基數都大呢？
後來羅素又指出這樣的一個問題：是否存在一個所有集合的集合？如果存在，那麼倘若把對角線方法應用於它，會出現什麼結果？
這樣我們會得到一個不同於所有那些已經擁有標籤的集合的集合。正是在考慮這種情況時，羅素發現他那個關於由一切不是自身的集合組成的集合的著名悖論，也就是他向弗雷格傳達的那個悖論。
這裡我們看到，弗雷格和康託爾之間被羅素悖論聯繫起來。而關於這個悖論的討論和思考，則引發了數學史上的第三次危機。
大衛希爾伯特
希爾伯特是20世紀的數學領袖，1900年他在數學家大會上指出的23個問題，其中第二個便是關於算術一致性的問題。
希爾伯特綱領所提出的主要問題就是算術一致性問題。為了解決這個問題，希爾伯特發展出了元數學，一致性證明將在元數學內部完成。
1928年，希爾伯特和他的學生阿克曼出版了一本邏輯課本，書中提出了關於弗雷格的基本邏輯(後來被稱為一階邏輯)兩個主要問題，一個就是，證明一階邏輯的完備性，即任何一個從外部看來有效的公式都可以只用課本裡提出規則從系統內部導出。
第二個問題以希爾伯特的判定問題而聞名，即對於一個一階邏輯的公式，如果找到一種方法，可以在定義明確有限步驟內判定這個公式是有效的。
這兩個問題分別為哥德爾和圖靈解決，而在解決第二個問題的過程中，圖靈提出了圖靈機的概念。
後來在1928年的國際數學家大會上，希爾伯特又提出一個關於形式系統的問題，這個系統建立在把一階邏輯應用於現在被稱為皮亞諾算術或者PA的自然數公理系統的基礎之上。
希爾伯特希望可以證明PA是完備的，也就是說任何一個可以在PA中表出的命題或者可以在PA中被證明為真，或者可以被證明為假。兩年後，這個問題被一個叫哥德爾的年輕人解決了，但答案卻完全不像希爾伯特料想的那樣。
哥德爾完備性定理
希爾伯特在20世紀20年代介紹了他的元數學綱領：一致性有待證明的公理將被包含在一個形式邏輯系統之內，而證明僅僅是有限數目的符號的一種排列而已。
當希爾伯特開始思考希爾伯特綱領時，希爾伯特的學生阿克曼和馮諾依曼似乎正在朝著用有限性方法證明PA的一致性的方向大步邁進。
他們二人都已經為PA的一個有限的子系統找到了這樣的證明，成功似乎指日可待。
這樣哥德爾開始試圖將算術一致性還原為PA的一致性，然而就是在這樣的努力中失敗了。哥德爾開始思考這些問題時，他重新思考了從外部而不是從內部考察一個系統的意思。
從外部看，這些系統包含著符號串之間的關係。從內部看，這些系統能夠表達關於不同數學對象的命題。哥德爾通過給符號串用自然數編碼，將外部帶到了內部。
哥德爾發現存在這樣的命題，它們從系統外部看是真命題，但無法在系統內部得到證明。於是他得出了一個非凡結論：一種有意義的數學真理的觀念不僅是存在的，而且其範圍還超出了任何給定的形式系統的證明能力。
在1931年，他發表的論文中，他選擇對形式系統PM給出了他的結果，從而說明即使強邏輯系統也不可能把全部數學真理包含在內。
在哥德爾的證明中，關鍵的一步在於他證明了：一個自然數作為PM中可證命題的一個代碼，這一性質本身可以在PM中表示出來。
根據這一事實，哥德爾可以在PM中構造出一些命題，這些命題可以被看做表達了這樣一個斷言，即某些命題在PM中是不可證的。也就是說他可以構造出一個命題A，該命題經解碼後可以斷言某一命題B在PM中是不可證的。
現在，在沒有獲知密碼的人看來，命題A不過是一串符號而已，但是通過代碼，神秘性就消失了：A表示這樣一個命題，即某個符號串B表示在PM中一個不可證的命題。A和B通常是不同的命題，哥德爾問，它們是否有可能是相同的呢？
事實上它們可以是相同的，哥德爾可以利用對角線方法證明這個結論。
運用這些技巧，我們可以使被斷言為不可證的命題和做出這一斷言的命題是同一個命題。換句話說哥德爾發現了如果獲得這樣一個非凡的命題，我們將它稱之外U，具有如下性質：
U說某個特殊命題在PM中不可證。
那個特殊的命題就是U本身。
因此，U說"U在PM中不可證"
如果我們承認PM中證明的任何命題都是真的，那麼我們發現U是真的，但它在PM中不可證。
U是真的。假定它是假的，那麼它表述的內容就是假的，因此它就是不是不可證的，而一定是可證的，從而是真的，這與開始假定U是假的矛盾，所以它一定是真的。因為它是真的，所以它表述的內容為真，所以它在PM中不可證。
我們把U稱為不可判定命題，當然這種不可判斷性只與系統內部的可證性，從我們外部的觀點來看U是真的。
另一方面，在PM內部，我們可以證明：如果PM是一致的，那麼U。因此正是PM是一致的這一個假定，才使U在PM內部得不到證明。既然我們知道U在PM內部是不可證的，我們就必須得出結論說，PM的一致性在PM中不可證。
而希爾伯特的主要目的就在於：用於被認為構成PM的一個非常有限的子集的有限性方法來證明像PM這樣的系統的一致性。然而哥德爾證明了，即使就PM的全部能力而言，它也不足以證明自身的一致性。於是希爾伯特綱領走到了盡頭。
圖靈和圖靈機
在哥德尓1930年的博士論文中證明了弗雷格的規則是完備的，這樣就回答了希爾伯特1928年提出的第一個問題。
而第二個問題即判定問題，在哥德爾的工作發表之後，人們很難想像存在這樣的判定算法，於是阿蘭圖靈開始思考如果證明這樣的算法是不存在的。
圖靈採取了這樣的一條道路，他首先分析了人的計算過程。通過丟掉非本質的細節，將這些計算活動局限在少數幾種極為簡單的基本操作上。
然後圖靈說明人可以被一個能夠執行這些基本操作的機器所替代。然後只要證明僅僅執行那些基本操作的機器不可能判定一個給定的結論是否可以用弗雷格的規則從給定的前提中導出，這樣他就能夠下結論說，判定問題的算法是不存在的。
作為副產品，他對計算過程的分析，產生了通用計算機的一個數學模型。
他觀察到：在計算的每一個階段，只有少數符號受到了注意。每一個階段所採取的行動僅僅取決於受到注意的那些符號以及當前的心靈狀態。
然後他做出了如下抽象：計算通過在一條被劃分成方格的紙帶上寫下符號來進行。執行計算的人在每一步都只注意其中一個方格的符號。她的下一步將僅僅取決於這個符號和她的心靈狀態。她的下一步是這樣的：她在當前注意的方格裡寫下一個符號，然後將注意力轉向它左邊或者右邊的相鄰符號。
現在可以很容易看出，做這項工作的人可以用一個機器替代，紙帶在機器上來回移動。關鍵之處在於圖靈對於計算概念的分析，通過某種算法程序可計算的任何東西都可以通過一臺圖靈機來計算。因此如果我們可以證明某些任務無法用圖靈機完成，那麼我們就可以說沒有任何算法可以完成這項任務。這就是圖靈證明判定問題不存在算法的方法。
實際上一臺圖靈機可以用這樣的一個五元組來表示：當機器處於狀態R，注視紙帶上的符號a時，它將用b來代替a，向右移動一個方格，然後轉到狀態S。而一個具體的算法便可以由這些五元組表示的狀態轉換的集合組成的圖靈機來表示出來。R a:b -> S 或者R a:b
圖靈將對角線方法應用於這種情況，得到了圖靈機不能解決的問題，由此推出了判定問題的不可解性。與哥德尓類似，圖靈採用了對角線方法也對圖靈機通過自然數進行了編碼。
圖靈機本身可以是自然數編碼表示，這樣它也作為自身的輸入。實際上有些輸入會使圖靈機停止下來，另一些則不會。
這樣一臺圖靈機就具有一些停機集合。如果我們考慮把一臺圖靈機的停機集合組成了一個包裹，並且認為那臺機器的碼數就是這個包裹的標籤。對角線方法允許我們構造出一個與圖靈機的任何停機集合都不同的自然數集合，我們稱之為D。
方法是這樣的，我們考慮把圖靈機的編碼作為自身的輸入，如果它的編碼數不屬於自身的停機集合，那麼我們就把它加入D。而集合D則不是任何圖靈機的停機集合。
然後考慮這樣一個問題：
找到一種算法，判定一個給定的自然數是否屬於集合D。
這就是一個不可解問題的例子。首先如果存在這樣的一個算法，我們就能找到這樣的一個圖靈機，但是我可以改造一下這個圖靈機，把以下兩個五元組加入到這個圖靈機：F 0:口-> F 和 F 口:口-> F。
對於這個新的改進的圖靈機來說，如果輸入的數屬於D那麼那麼機器就會像以前一樣運轉，並輸出1而告終，如果輸入的數不屬於D，那這臺機器將永遠向右移動。這樣我們就找到了一臺圖靈機它的停機集合剛好就是D。
於是與我們的對角線方法矛盾。所以並不存在這樣的一個算法。由此可知判斷問題在算法上是不可解的。
為了驗證自己工作的有效性，圖靈又提出了通用機模型，通用機包含了圖靈機代碼以及待處理的數據。
而這剛好對應著我們今天的機器，程序與數據的概念。也為存儲程序計算機提供了一個模型。正是圖靈在證明判定問題的不可解性是，對計算概念的分析以及對通用機的發現促使了計算機的產生。
1945年圖靈又發表了他那篇著名的ACE(自動計算機)報告。這是對計算機的一次完整的描述，一直到邏輯電路圖。也就是在這時馮諾依曼提出了他著名的"關於EDVAC的報告草案"，它實際上主張將要建造的EDVAC作為圖靈通用機的一個物理模型實現出來。
在這個報告裡，提出了存儲程序的概念，也就是沿用至今的馮諾依曼結構，實際上它的革命性不在於存儲程序而是通用性，存儲程序只是達到這一目的的一種手段。
1950年，圖靈又發表了他的經典論文，計算機與智能，提出了著名的圖靈測試來測試計算機是否具有智能。
1954年6月7日，圖靈咬了一個浸過氰化物的蘋果，結束了自己的生命，而他的通用機思想卻延續到今天。