邱奇-圖靈論題（Church-Turing thesis）
/ Church -> CHURCH, Turing -> TYOOR-ing /
早在電腦存在之前，數學家就對「有效程序」或「演算法」有個直覺：一張有限的、完全機械且毫不含糊的步驟清單，一個只有紙筆、有充裕時間、不靠任何聰明才智的書記員就能照著執行。難題在於這個直覺從來沒有精確定義。邱奇-圖靈論題（Church-Turing thesis）就是一個大膽的主張：我們終於捕捉到了它——凡是能被任何機械程序計算的東西，都能被圖靈機計算。
這個論題把一個非形式的概念（「能被某演算法有效計算」）等同於一個精確的數學概念（「能被圖靈機計算」）。它以阿隆佐·邱奇（Alonzo Church，用 λ 演算定義可計算性）與艾倫·圖靈（Alan Turing，用他的機器定義可計算性）命名；兩人在 1930 年代各自工作，卻得到完全相同的函數類別。關鍵在於：這是論題，不是定理。它無法被證明，因為等式的一邊「可有效計算」是非形式、直覺的概念，而你無法證明一個非形式概念等於一個形式概念。原則上，它可以被反駁——只要舉出一個明顯機械、卻沒有圖靈機能執行的程序——但近一個世紀來無人辦到。
論題確實主張的是：圖靈機能做到的界線，就是機械計算的界線，因此被證明對圖靈機不可判定的問題（如停機問題），對任何演算法、任何程式語言、任何可想像的數位電腦都不可判定。它並未主張的是：它對速度或效率隻字未提，對人類能直覺或證明什麼隻字未提，並且（在其基本形式下）對奇異的物理過程隻字未提。更強、更具推測性的版本——物理論題（大自然本身也算不出任何不可計算的東西）與擴展論題（圖靈機能以至多多項式慢化模擬任何模型）——超出了這個範圍，爭議也大得多。
當教科書說「有一個演算法能把兩個數相乘」時，它只用平白的文字給出高層次的步驟，而不費事去編一台圖靈機。邱奇-圖靈論題正是這種做法背後沒明說的許可：任何這樣明顯機械的步驟都能被改寫成一台圖靈機，所以非形式地描述演算法就夠了。
正因有這個論題，我們才能用散文描述演算法，卻仍稱它們為圖靈可計算。
它是論題，不是定理：因為「可有效計算」是非形式的，所以無法被證明。它也對效率隻字未提，更不是關於人類心智能領會什麼的主張。