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