圖靈機(jī)與可計(jì)算性理論
在介紹圖靈機(jī)前先來簡略了解一下哥德爾完備性：
哥德爾完備性定理成立。它聲稱對于任何一階理論T和在這個理論中的任何句子S鸥滨，有一個S的自T的形式演繹，當(dāng)且僅當(dāng)S被T的所有模型滿足谤祖。這個更一般的定理被隱含使用婿滓，例如，在一個句子被證實(shí)可以用群論的公理證明的時候粥喜，通過考慮一個任意的群并證實(shí)這個句子被這個群所滿足凸主。完備性定理是一階邏輯的中心性質(zhì)，不在所有邏輯中成立额湘。比如二階邏輯就沒有完備性定理卿吐。
個人感覺圖靈完備是和完備性證明分不開的，下面是圖靈完備的定義：
可圖靈指在可計(jì)算性理論中锋华，編程語言或任意其他的邏輯系統(tǒng)如具有等用于通用圖靈機(jī)的計(jì)算能力嗡官。換言之，此系統(tǒng)可與通用圖靈機(jī)互相模擬毯焕。
上面的解釋比較抽象衍腥，簡單來說，能夠抽象成圖靈機(jī)的系統(tǒng)或編程語言就是圖靈完備的纳猫；一切可計(jì)算的問題圖靈機(jī)都能計(jì)算婆咸，因此滿足這樣要求的邏輯系統(tǒng)、裝置或者編程語言就叫圖靈完備的芜辕。
