通用圖靈機

通用圖靈機（universal Turing machine，又稱Machine U）是一種圖靈機，由艾倫·圖靈在1936年發明。這種多用途單機器（計算機器）模型可以“運行”任何任意（但well-formed）指令序列（稱為 "quintuples"）。這模型被一些人例如Davis (2000) 認為是“存儲程式電腦”的原點。存儲程式電腦一詞由約翰·馮·諾伊曼使用在他的《電子計算裝置》（"Electronic Computing Instrument"）。這種電腦現在使用馮·諾伊曼的名字稱為馮·諾伊曼結構。

基本介紹

• 中文名：通用圖靈機
• 外文名：Universal Turing Machine
• 意思：能夠模擬其它所有圖靈機的圖靈機
• 簡稱：UTM

簡介

通用圖靈機（universal Turing machine，又稱Machine U）是一種圖靈機，由艾倫·圖靈在1936年發明。這種多用途單機器（計算機器）模型可以“運行”任何任意（但well-formed）指令序列（稱為 "quintuples"）。這模型被一些人例如Davis (2000) 認為是“存儲程式電腦”的原點。存儲程式電腦一詞由約翰·馮·諾伊曼使用在他的《電子計算裝置》（"Electronic Computing Instrument"）。這種電腦現在使用馮·諾伊曼的名字稱為馮·諾伊曼結構。

每台圖靈機從它的字母表得到字元串計算一確定的固定偏可計算函式。從外觀上它的行為就像一台使用固定程式的電腦。儘管如此，我們可以把任何圖靈機的動作表格編碼到一條字元串。因此，我們可以建構出一台圖靈機，它期待的紙帶上記載有一條用以描述動作表格的字元串緊跟著一條用以描述輸入的字元串，從而計算那台被編碼的圖靈機所計算的。圖靈在1936年的文章中詳細描述如此的構思。

艾倫·圖靈

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

在第二次世界大戰期間，圖靈曾在“政府密碼學校”（GC&CS，今政府通信總部）工作。政府密碼學校位於布萊切利園，是英國頂級機密情治單位。圖靈在這裡從事密碼破譯工作，有一段時間，他領導了小屋8號（Hut 8）小組，負責德國海軍密碼分析。 期間他設計了一些加速破譯德國密碼的技術，包括改進波蘭戰前研製的機器Bombe，一種可以找到恩尼格瑪密碼機設定的機電機器。 圖靈在破譯截獲的編碼信息方面發揮了關鍵作用，使盟軍能夠在包括大西洋戰役在內的許多重要交戰中擊敗納粹，並因此幫助贏得了戰爭。

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

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

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

圖靈機

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