圖靈完備性

艾倫·麥席森·圖靈，OBE，FRS（英語：Alan Mathison Turing，又譯阿蘭·圖靈，Turing也常翻譯成塗林或者杜林，1912年6月23日－1954年6月7日），英國計算機科學家、數學家、邏輯學家、密碼分析學家和理論生物學家，他被視為計算機科學與人工智能之父。

1931年圖靈進入劍橋大學國王學院，畢業後到美國普林斯頓大學攻讀博士學位，二戰爆發後回到劍橋，後曾協助軍方破解德國的著名密碼系統Enigma，對盟軍取得了二戰的勝利有一定的幫助。

圖靈對於人工智能的發展有諸多貢獻，例如圖靈曾寫過一篇名為《計算機器和智能》（Computing Machinery and Intelligence）的論文，提問“機器會思考嗎？”（Can Machines Think?），作為一種用於判定機器是否具有智能的試驗方法，即圖靈測試。至今，每年都有試驗的比賽。此外，圖靈提出的著名的圖靈機模型為現代計算機的邏輯工作方式奠定了基礎。

圖靈是著名的男同性戀者，並因為其性傾向而遭到當時的英國政府迫害，職業生涯盡毀。他亦患有花粉過敏症。

圖靈還是一位世界級的長跑運動員。他的馬拉松最好成績是2小時46分3秒，比1948年奧林匹克運動會金牌成績慢11分鐘。1948年的一次跨國賽跑比賽中，他跑贏了同年奧運會銀牌得主湯姆·理查茲（Tom Richards）。

主條目：圖靈測試

1945年到1948年，圖靈在國家物理實驗室負責自動計算引擎（ACE）的研究工作。1949年，他成為曼徹斯特大學計算機實驗室的副主任，負責最早的真正的計算機---曼徹斯特一號的軟件工作。在這段時間，他繼續作一些比較抽象的研究，如“計算機械和智能”。圖靈在對人工智能的研究中，提出了一個叫做圖靈測試（Turing test）的實驗，嘗試定出一個決定機器是否有感覺的標準。

1952年，圖靈寫了一個國際象棋程序。可是，當時沒有一台計算機有足夠的運算能力去執行這個程序，他就模仿計算機，每走一步要用半小時。他與一位同事下了一盤，結果程序輸了。

後來美國新墨西哥州洛斯阿拉莫斯國家實驗室的研究組根據圖靈的理論，在ENIAC上設計出世界上第一個電腦程序的國際象棋－洛斯阿拉莫斯國際象棋。

在計算機科學中，可計算性理論（Computability theory）作為計算理論的一個分支，研究在不同的計算模型下哪些算法問題能夠被解決。相對應的，計算理論的另一塊主要內容，計算複雜性理論考慮一個問題怎樣才能被有效的解決。

這樣我們可以定義可計算性等級：所有的語言的集合，記為All；遞歸可枚舉語言，即可以被圖靈機枚舉的語言的集合，記為RE；遞歸語言，即可以被圖靈機決定的語言的集合，記為R。可見

，即形成可計算性等級。那麼產生相關的問題即是兩個包含關係是不是嚴格的，即是否有在All而不在RE中的語言，以及在RE而不在R中的語言。阿蘭·圖靈在1930年代的工作表明這兩個包含關係都是不嚴格的，即可以證明存在語言L_d，是不能被圖靈機所枚舉的，以及存在語言L_u，是不能被圖靈機所決定的。證明的主要思想是對角線法。 ^[1] 

停機問題就是判斷任意一個程序是否會在有限的時間之內結束運行的問題。該問題等價於如下的判定問題：給定一個程序P和輸入w，程序P在輸入w下是否能夠最終停止。

Post對應問題（Post's correspondence problem）。

不可解度的概念定義了不可解的集合之間的相對計算難度。例如，不可解的停機問題顯然比任何可解的集合都要難，然而同樣不可解的“元停機問題”（即所有具備停機問題的預言機的停機問題）卻要難過停機問題，因為具備元停機問題的預言機可以解出停機問題，然而具備停機問題的預言機卻不能解出元停機問題。

圖靈機（英語：Turing machine），又稱確定型圖靈機，是英國數學家艾倫·圖靈於1936年提出的一種抽象計算模型，其更抽象的意義為一種數學邏輯機，可以看作等價於任何有限邏輯數學過程的終極強大邏輯機器。