請問人工智慧還是圖靈機嗎？再問量子計算機還是圖靈機嗎

12-30

目前人工智慧分為符號主義和聯接主義兩種派別，請問這兩種派別都還是圖靈機原理嗎？
另外一個問題，量子計算機還是圖靈機原理嗎？曾看到有人說，量子計算機是多重宇宙的圖靈機，這種說法對嗎？

1。圖靈機是個數學模型，它是定義了什麼是演算法(或者機械步驟)；事實上「演算法」這個概念，一直以來缺乏嚴格的數學定義，圖靈機的出現，就給了演算法一個定義。當然，在圖靈機之前，大家還嘗試過很多其他對演算法的定義，比如遞歸函數，Lambda演算，Post機，細胞自動機（Game of Life）等。但後來證明這些模型統統都和圖靈機等價，因此他們定義了同一個演算法的概念（PS：我還寫過一篇論文證明了算盤和圖靈機也等價）。於是人們提出了所謂的Church-Turing Thesis：即所有人類直覺上能行可計算（effectively computable）的函數類，等價於圖靈機可計算函數類。但這始終是一個thesis，沒辦法證明，因為講不清什麼是「effectively computable」。

2。試圖超越圖靈機的模型也有人搞過，但大部分都失敗了。有些看上去好像成果了，比如所謂的Hypercomputation（具體可參見wikipedia詞條），但仔細分析一下發現都有漏洞：要麼是需要無窮的計算資源（比如時間、空間、能量、物質等），要麼是假設時間空間是連續的（但現代物理告訴我們時間空間其實是離散的），要麼是理論上可行實際上不存在的，所以都然並卵。話說有段時間我也搞出N個試圖超越turing machine的模型，可惜都以失敗告終。

3。量子計算機，其理論模型依然沒有超越圖靈機。1985年Deutsch就提出了量子圖靈機模型，事實上是概率圖靈機的變種，還是和經典圖靈機等價（是指計算能力相等，但是計算效率並不等價）。後來1993年姚期智證明了量子圖靈機和量子電路等價，得到了兩者之間在計算複雜性上和經典情況類似的結論。

4。事實上，任何有限輸入、有限輸出、有限規則可定義的計算模型，都無法超越圖靈機。圖靈機的極限，就在於有限和無限之間。

5。至於機器學習，人工智慧，他們只是某類特殊的演算法，或者說只是一大類運行在圖靈機上的程序罷了。談不上什麼超越圖靈機，根本沒有可比性。

6。剛才提到過，圖靈機的極限其實在於有限的輸入、有限的輸出、有限的控制規則。如果涉及到無限，問題就變的圖靈不可計算了，比如停機問題。利用這個思路，很容易證明存在圖靈不可計算函數：由於圖靈機的規則總是有限的，所以任何一台圖靈機可看作是其規則的一個有限長度串（一段程序），這樣的有限字符集中的有限長度字元串的集合的大小和自然數集合相同（其秩是aleph_0）；而所有輸入為自然數輸出也為自然數的函數（稱為數論函數）的集合的大小和實數集合大小相同（其秩是aleph_1），所以必然有這樣的一個函數不存在任何圖靈機可以計算它，否則圖靈機集合和數論函數集合大小相同；但我們知道自然數集合和實數集合大小是不同的（康托對角線刪除法），矛盾。事實上，圖靈停機問題不可計算的證明，用到的也是康托對角線刪除法。

7。因此，圖靈機的極限就在於其輸入、輸出、規則的有限性。如果允許圖靈機可以有無限的輸入，以及無限的輸出，那麼問題就變的有趣了：是否可以通過這種方式超越圖靈機？注意到無限的規則是不可能的，否則我們也沒辦法描述這個東西。

8。在我看來，機器學習其實可以看作是某種有無限輸入（訓練數據）和無限輸出的圖靈機，理論上這樣的圖靈機是否可以超越經典圖靈機？但這個問題不是這麼簡單，因為機器學習的過程中是允許出錯的，這個出錯概率如何定義，如何保證最終出錯概率可以收斂有界，這都是需要仔細考慮的問題。這個問題我已經考慮了挺久的了，目前還沒有太好的結論。當然，這並不表明現有的機器學習、人工神經網路之類的可以超越圖靈機，因為它們實際上還是有限輸入有限輸出有限規則的演算法。

9。另一個有趣的問題是，如果把大自然看作一個計算機，任何物理系統都可以用來做計算：只需要把問題的輸入編碼到系統的初態，讓系統按照物理規律做自然演化，然後把系統的末態解碼為計算的輸出結果。從這個角度看，任何物理系統的演化都是一個計算過程。

10。事實上物理系統作為計算過程的思想早已有之，比如我們知道電容的充電放電函數是個積分函數，早起的模擬電路中，就使用電容來做積分器計算積分。現在的電子計算機，本質上也是個物理系統，我們在鍵盤上的輸入，最終都轉化為電信號輸入系統讓系統進行演化，系統演化的結果，再轉換為電信號輸出到屏幕上……所以電子計算機也沒有脫出這個範疇。

11。那麼，一個有趣的問題就是，按照現在的物理學理論，物理系統是否有超越圖靈機的計算能力？這個問題我也仔細調研過，答案是有的。理論上，任何物理系統都可以用系統的哈密頓量描述，而哈密頓量是個酉矩陣，其集合的秩是aleph_1，和實數集合等勢，這就已經超越所有圖靈機的集合大小了，所以一定存在超越圖靈機的物理系統。事實上，上個世紀五十年代，有個蘇聯數學家就構造出一個波動方程，該方程本身可計算，但其導函數處處不可計算。這說明理論上我們可以構造出一個物理系統，讓其演化出的結果可以計算一個圖靈機不可計算函數。

12。當然，除了關注物理系統和圖靈機的可計算性之間的比較，更有意義的其實是關注其計算效率之間的比較，即計算複雜度的問題。關於這個問題，目前已經證明量子圖靈機在某些特定問題上（主要是一類帶oracle問題）遠比經典圖靈機更高效，甚至達到指數級加速。但目前缺乏足夠證據證明其在非oracle的實際問題上也能達到指數級加速。但已經證明的是，對於任意無結構搜索問題，量子圖靈機比經典圖靈機至少可以有平方級加速（即經典的需要O(N)次運算，量子則只需要O(sqrt(N))次運算），具體可參見著名的Grover搜索演算法。

13。最後補充一下：所謂的量子圖靈機是利用整個宇宙做計算，這是基於量子力學的多宇宙解釋的一個推論。如果多宇宙解釋是正確的，量子圖靈機做計算的過程，其實是隨機「猜」結果；當然運氣不好就猜錯了，但是運氣足夠好你會發現它猜對了，這只是因為你恰好處於它猜對結果所處的那個平行宇宙分支之中；在其他的平行宇宙，你的運氣不好它沒有猜對結果。當然，多宇宙的解釋我是不太贊同的，我認為宇宙不該這麼複雜。

人工智慧和圖靈機是不同側面的計算程序概念。兩者沒有任何必然的聯繫。

量子計算機和和圖靈機也是不同側面的計算程序概念。兩者可以有交叉。

結論：目前所有機器學習（人工智慧也好）演算法都由計算機實現的，當然是和圖靈機等價的。

圖靈機是，由無限長度的紙帶，一個讀寫磁頭（左右移動），一組完備的狀態和規則組成的機器，它可以在理論上計算任何可計算的問題。任何現實的計算機在計算能力上都是和圖靈機等價的。

人工智慧（至少機器學習）我認為研究的是一種自組織模型，即通過一套預定義的規則和狀態，在數據的驅動下，自組織和自適應的系統。也可以側面說，在這個系統中，經驗信息會改變系統本身的運行規則。

總而言之，人工智慧和圖靈機不是一個層次的概念，雖然有交集，但是關注點不一樣。圖靈機本質上定義了什麼是演算法，哪些問題是可計算的？而人工智慧設計則是關注具備「智能」屬性的演算法，往往還要考慮計算資源消耗的問題。

如果我們認為智能是由一種計算模型所產生的話，則根據計算等價性，任何圖靈完備的系統（當然需要信息輸入輸出）都有實現人工智慧的能力。

好深奧的問題啊，我來試著回答一下後面的問題。量子計算機不是圖靈機，它比圖靈機更加強大，具體可以參考《量子信息與量子計算》這本綠皮書（量子信息領域的Bible）。量子計算與多重宇宙沒有必然的聯繫，但是量子計算機具有一種內稟的並行能力，可以加速傳統的很多演算法。如果把「多重宇宙」理解為疊加態的話，這話貌似也說得過去~

圖靈機是人工智慧最早的原型機之一，人工智慧的發展早已經遠遠超出了圖靈機的範疇。量子計算機是更為強大的計算機，不是人工智慧機器，但能用於人工智慧計算，由於量子同時具有4種狀態，而電子即「0」「1」只能同時有兩種狀態，因此量子計算機更適合併行計算，也就適合人工智慧演算法，因為人工智慧演算法是大規模並行計算。