Church-Turing Thesis

Turing machine 本身沒什麼特別，是 Church-Turing thesis 使它佔有特殊地位。一個常見的陳述是：當代電腦的計算能力等價於 Turing machine。這句話有兩個方向，而兩個方向其實都有瑕疵。一個方向是，電腦能計算的東西 Turing machine 都能計算，這是依 Church-Turing thesis 而來，而 Church-Turing thesis 其實只是個 conjecture，或者算是公理 ─ 它無法被證明（而我覺得它還不夠「不辯自明」）。另一個方向是說，Turing machine 能計算的東西，電腦都能計算。這個方向似乎對（我們可以寫個程式模擬 Turing machine），但其實只是近似結果 ─ Turing machine 的紙帶是無窮長，而當代電腦顯然沒有容量無窮大的記憶體，只能盡量把記憶體加大而逼近 Turing machine 的計算能力。

--
好了，要看高等微積分了 XD。