擴展邱奇-圖靈論題（extended Church-Turing thesis）
/ Church -> CHURCH, Turing -> TYOOR-ing /
普通的邱奇-圖靈論題很寬厚：它只在意「某物能否被計算」，不管要花多久。擴展邱奇-圖靈論題（extended Church-Turing thesis）則是一位大膽得多、要求也高得多的表親。它加上一條關於效率的條款：圖靈機不僅能計算任何合理模型所能計算的一切，還能以至多多項式的慢化做到。換句話說，沒有任何物理上可實現的機器能比標準圖靈機快上超過多項式的程度。
說白了，擴展論題主張：任何合理的計算模型都能被一台（機率型）圖靈機以僅多項式的時間額外開銷模擬。這正是讓複雜度類別 P（多項式時間）成為穩健、與模型無關之概念的關鍵：若它成立，那麼不論你用多帶機、RAM 模型或真實的 C 程式，「可在多項式時間內解出」意義都相同。多數日常模型確實遵守它——圖靈機、暫存器機與尋常電腦之間的模擬都只花多項式倍數，這正是理論家能自在地談「多項式時間」而不指明機型的原因。
但與基本論題不同，這個更強的版本確實受到威脅。量子計算是頭號挑戰者：Shor 演算法在量子電腦上以多項式時間分解整數，而沒有任何已知的古典（圖靈）演算法能做到，且在古典電腦上模擬量子電腦似乎需要指數時間。若那道指數鴻溝是真的，擴展論題對「時間」而言就是錯的，這正是許多人如今把它改述為「量子圖靈機能以多項式額外開銷模擬任何合理模型」的原因。兩個誠實的告誡：其一，這仍是開放問題，沒有人證明古典模擬量子電腦必須是指數的。其二，擴展論題談的是效率，是有爭議的那一個；而談「僅僅可計算性」的普通邱奇-圖靈論題完全不受此影響——量子電腦計算的函數與圖靈機完全相同，只是在某些上可能更快。
一台以時間 t 運行的 k 帶圖靈機，可被單帶機以約 t^2 步模擬，是多項式爆炸，所以這遵守擴展論題。但「模擬一台分解大數的量子電腦」似乎需要指數時間，這正是懷疑該論題一般成立與否的首要理由。
多項式慢化（多帶到單帶）遵守擴展論題；量子加速則可能打破它。
別把它與基本論題混為一談。擴展論題談效率，很可能是錯的（量子計算）；而僅談可計算性的普通邱奇-圖靈論題不受影響——量子電腦計算的是相同的函數，而非新的函數。