匿名使用者 2013-12-05

1936年，阿蘭·圖靈提出了一種抽象的計算模型 ── 圖靈機 （Turing Machine）。圖靈的基本思想是用機器來模擬人們用紙筆進行數學運算的過程，他把這樣的過程看作下列兩種簡單的動作：

在紙上寫上或擦除某個符號；

把注意力從紙的一個位置移動到另一個位置；

而在每個階段，人要決定下一步的動作，依賴於 （a） 此人當前所關注的紙上某個位置的符號和（b） 此人當前思維的狀態。為了模擬人的這種運算過程，圖靈構造出一臺假想的機器，該機器由以下幾個部分組成：

一條無限長的紙帶。紙帶被劃分為一個接一個的小格子，每個格子上包含一個來自有限字母表的符號，字母表中有一個特殊的符號 表示空白。紙帶上的格子從左到右依此被編號為 0， 1， 2， 。。。 ，紙帶的右端可以無限伸展。

一個讀寫頭。該讀寫頭可以在紙帶上左右移動，它能讀出當前所指的格子上的符號，並能改變當前格子上的符號。

一個狀態暫存器。它用來儲存圖靈機當前所處的狀態。圖靈機的所有可能狀態的數目是有限的，並且有一個特殊的狀態，稱為停機狀態。

一套控制規則。它根據當前機器所處的狀態以及當前讀寫頭所指的格子上的符號來確定讀寫頭下一步的動作，並改變狀態暫存器的值，令機器進入一個新的狀態。

注意這個機器的每一部分都是有限的，但它有一個潛在的無限長的紙帶，因此這種機器只是一個理想的裝置。圖靈認為這樣的一臺機器就能模擬人類所能進行的任何計算過程

圖靈機停機問題（The Halting Problem）的不可判定性

圖靈機停機問題： 能否給出一個判斷任意一個圖靈機是否停機的一般方法？ 答案是NO。

這個問題實際上是問： 是否存在一臺“萬能的”圖靈機 H， 把任意一臺圖靈機 M 輸入給 H， 它都能判定 M 最終是否停機， 輸出一個明確的 “yes” 或 “no” 的答案？ 可以利用反證法來證明這樣的 H 不可能存在。 假定存在一個能夠判定任意一臺圖靈機是否停機的萬能圖靈機 H（M）， 如果 M 最終停機， H 輸出 “halt”； 如果 M 不停機， H 輸出 “loop”。 我們把 H 當作子程式， 構造如下程式 P：

function P（M） {

if （H（M）==“loop”） return “halt”；

else if （H（M）==“halt”） while（true）； // loop forever

}

因為 P 本身也是一臺圖靈機， 可以表示為一個字串， 所以我們可以把 P 輸入給它自己， 然後問 P（P） 是否停機。 按照程式 P 的流程， 如果 P 不停機無限迴圈， 那麼它就停機， 輸出“halt”； 如果 P 停機， 那麼它就無限迴圈， 不停機； 這樣無論如何我們都將得到一個矛盾， 所以假設前提不成立， 即不存在這樣的 H。 或者說， 圖靈機停機問題是不可判定的（undecidable）。

李雲龍飛 2006-10-11

圖靈機

1936年，阿蘭·圖靈提出了一種抽象的計算模型 —— 圖靈機 （Turing Machine）。圖靈的基本思想是用機器來模擬人們用紙筆進行數學運算的過程，他把這樣的過程看作下列兩種簡單的動作：

在紙上寫上或擦除某個符號；

把注意力從紙的一個位置移動到另一個位置；

而在每個階段，人要決定下一步的動作，依賴於 （a） 此人當前所關注的紙上某個位置的符號和（b） 此人當前思維的狀態。為了模擬人的這種運算過程，圖靈構造出一臺假想的機器，該機器由以下幾個部分組成：

一條無限長的紙帶。紙帶被劃分為一個接一個的小格子，每個格子上包含一個來自有限字母表的符號，字母表中有一個特殊的符號 表示空白。紙帶上的格子從左到右依此被編號為 0， 1， 2， 。。。 ，紙帶的右端可以無限伸展。

一個讀寫頭。該讀寫頭可以在紙帶上左右移動，它能讀出當前所指的格子上的符號，並能改變當前格子上的符號。

一個狀態暫存器。它用來儲存圖靈機當前所處的狀態。圖靈機的所有可能狀態的數目是有限的，並且有一個特殊的狀態，稱為停機狀態。

一套控制規則。它根據當前機器所處的狀態以及當前讀寫頭所指的格子上的符號來確定讀寫頭下一步的動作，並改變狀態暫存器的值，令機器進入一個新的狀態。

注意這個機器的每一部分都是有限的，但它有一個潛在的無限長的紙帶，因此這種機器只是一個理想的裝置。圖靈認為這樣的一臺機器就能模擬人類所能進行的任何計算過程

秒懂百科精選 2020-11-19

嬉皮笑臉吧 推薦於2017-09-15

圖靈機，又稱圖靈計算、圖靈計算機，是由數學家阿蘭·麥席森·圖靈（1912～1954）提出的一種抽象計算模型，即將人們使用紙筆進行數學運算的過程進行抽象，由一個虛擬的機器替代人們進行數學運算。

所謂的圖靈機就是指一個抽象的機器，它有一條無限長的紙帶，紙帶分成了一個一個的小方格，每個方格有不同的顏色。有一個機器頭在紙帶上移來移去。機器頭有一組內部狀態，還有一些固定的程式。在每個時刻，機器頭都要從當前紙帶上讀入一個方格資訊，然後結合自己的內部狀態查詢程式表，根據程式輸出資訊到紙帶方格上，並轉換自己的內部狀態，然後進行移動。

阿蘭·麥席森·圖靈是英國數學家、被稱為計算機科學之父

阿蘭·麥席森·圖靈（Alan Turing，也被譯作阿蘭-圖林）生平簡介：

1912年6月23日，出生於英國倫敦。

1931年-1934年，在英國劍橋大學國王學院（King‘s College）學習。

1932年-1935年，主要研究量子力學、機率論和邏輯學。

1935年，年僅23歲的圖靈，被選為劍橋大學國王學院院士。

1936年，主要研究可計算理論，並提出“圖靈機”的構想。

1936年-1938年，主要在美國普林斯頓大學做博士研究，涉及邏輯學、代數和數論等領域。

1938-1939年，返回劍橋從事研究工作，並應邀加入英國政府破譯二戰德軍密碼的工作。

1940年-1942年，作為主要參與者和貢獻者之一，在破譯納粹德國通訊密碼的工作上成就傑出，併成功破譯了德軍U-潛艇密碼，為扭轉二戰盟軍的大西洋戰場戰局立下汗馬功勞。

1943年-1945年，擔任英美密碼破譯部門的總顧問。

1945年，應邀在英國國家物理實驗室從事計算機理論研究工作。

1946年，這個時候，圖靈在計算機和程式設計原始理論上的構思和成果，已經確定了他的理論開創者的地位。由於圖靈的傑出貢獻，年輕的他被英國皇室授予OBE爵士勳銜。

1947年-1948年，主要從事計算機程式理論的研究，並同時在神經網路和人工智慧領域做出開創性的理論研究。

1948年，應邀加入英國曼徹斯特大學從事研究工作，擔任曼徹斯特大學計算實驗室副主任。

1949年，成為世界上第一位把計算機實際用於數學研究的科學家。

1950年，發表論文“計算機器與智慧”，為後來的人工智慧科學提供了開創性的構思。提出著名的“圖靈測試”理論。

1951年，從事生物的非線性理論研究。年僅39歲的圖林，被選為英國皇家學會會員。

1952年，在當年保守愚昧和冷戰的時代，當警察得知圖靈與同性朋友密切交往的訊息之後，同性戀傾向的圖靈被逮捕入獄。在法庭審判過程中，圖靈明確告知人們，他認為自己沒有做錯什麼事。在那個觀念落後的年代，為了避免被判刑入獄，圖靈被迫選擇了為期一年的雌性激素注射的所謂“治療”，才得以重新返回研究工作。

1953年-1954年，繼續在生物和物理學等方面的研究。被迫承受的對同性戀傾向的“治療”，致使原本熱愛體育運動的圖靈在身心上受到極大的傷害。

1954年6月7日，圖靈被發現死於家中的床上。死因是氰化物中毒，警方調查結論是自殺。一代英靈，就此過早離去，成為人類科學史上的一大遺憾。

阿蘭-圖靈（Alan Turing，也被譯作阿蘭-圖林）生平簡介：

1912年6月23日，出生於英國倫敦。

1931年-1934年，在英國劍橋大學國王學院（King’s College）學習。

1932年-1935年，主要研究量子力學、機率論和邏輯學。

1935年，年僅23歲的圖靈，被選為劍橋大學國王學院院士。

1936年，主要研究可計算理論，並提出“圖靈機”的構想。

1936年-1938年，主要在美國普林斯頓大學做博士研究，涉及邏輯學、代數和數論等領域。

1938-1939年，返回劍橋從事研究工作，並應邀加入英國政府破譯二戰德軍密碼的工作。

1940年-1942年，作為主要參與者和貢獻者之一，在破譯納粹德國通訊密碼的工作上成就傑出，併成功破譯了德軍U-潛艇密碼，為扭轉二戰盟軍的大西洋戰場戰局立下汗馬功勞。

1943年-1945年，擔任英美密碼破譯部門的總顧問。

1945年，應邀在英國國家物理實驗室從事計算機理論研究工作。

1946年，這個時候，圖靈在計算機和程式設計原始理論上的構思和成果，已經確定了他的理論開創者的地位。由於圖靈的傑出貢獻，年輕的他被英國皇室授予OBE爵士勳銜。

1947年-1948年，主要從事計算機程式理論的研究，並同時在神經網路和人工智慧領域做出開創性的理論研究。

1948年，應邀加入英國曼徹斯特大學從事研究工作，擔任曼徹斯特大學計算實驗室副主任。

1949年，成為世界上第一位把計算機實際用於數學研究的科學家。

1950年，發表論文“計算機器與智慧”，為後來的人工智慧科學提供了開創性的構思。提出著名的“圖靈測試”理論。

1951年，從事生物的非線性理論研究。年僅39歲的圖林，被選為英國皇家學會會員。

1952年，在當年保守愚昧和冷戰的時代，當警察得知圖靈與同性朋友密切交往的訊息之後，同性戀傾向的圖靈被逮捕入獄。在法庭審判過程中，圖靈明確告知人們，他認為自己沒有做錯什麼事。在那個觀念落後的年代，為了避免被判刑入獄，圖靈被迫選擇了為期一年的雌性激素注射的所謂“治療”，才得以重新返回研究工作。

1953年-1954年，繼續在生物和物理學等方面的研究。被迫承受的對同性戀傾向的“治療”，致使原本熱愛體育運動的圖靈在身心上受到極大的傷害。

1954年6月7日，圖靈被發現死於家中的床上。死因是氰化物中毒，警方調查結論是自殺。一代英靈，就此過早離去，成為人類科學史上的一大遺憾。

是英國數學家、被稱為計算機科學之父

阿蘭-圖靈（Alan Turing，也被譯作阿蘭-圖林）生平簡介：

1912年6月23日，出生於英國倫敦。

1931年-1934年，在英國劍橋大學國王學院（King‘s College）學習。

1932年-1935年，主要研究量子力學、機率論和邏輯學。

1935年，年僅23歲的圖靈，被選為劍橋大學國王學院院士。

1936年，主要研究可計算理論，並提出“圖靈機”的構想。

1936年-1938年，主要在美國普林斯頓大學做博士研究，涉及邏輯學、代數和數論等領域。

1938-1939年，返回劍橋從事研究工作，並應邀加入英國政府破譯二戰德軍密碼的工作。

1940年-1942年，作為主要參與者和貢獻者之一，在破譯納粹德國通訊密碼的工作上成就傑出，併成功破譯了德軍U-潛艇密碼，為扭轉二戰盟軍的大西洋戰場戰局立下汗馬功勞。

1943年-1945年，擔任英美密碼破譯部門的總顧問。

1945年，應邀在英國國家物理實驗室從事計算機理論研究工作。

1946年，這個時候，圖靈在計算機和程式設計原始理論上的構思和成果，已經確定了他的理論開創者的地位。由於圖靈的傑出貢獻，年輕的他被英國皇室授予OBE爵士勳銜。

1947年-1948年，主要從事計算機程式理論的研究，並同時在神經網路和人工智慧領域做出開創性的理論研究。

1948年，應邀加入英國曼徹斯特大學從事研究工作，擔任曼徹斯特大學計算實驗室副主任。

1949年，成為世界上第一位把計算機實際用於數學研究的科學家。

1950年，發表論文“計算機器與智慧”，為後來的人工智慧科學提供了開創性的構思。提出著名的“圖靈測試”理論。

1951年，從事生物的非線性理論研究。年僅39歲的圖林，被選為英國皇家學會會員。

1952年，在當年保守愚昧和冷戰的時代，當警察得知圖靈與同性朋友密切交往的訊息之後，同性戀傾向的圖靈被逮捕入獄。在法庭審判過程中，圖靈明確告知人們，他認為自己沒有做錯什麼事。在那個觀念落後的年代，為了避免被判刑入獄，圖靈被迫選擇了為期一年的雌性激素注射的所謂“治療”，才得以重新返回研究工作。

1953年-1954年，繼續在生物和物理學等方面的研究。被迫承受的對同性戀傾向的“治療”，致使原本熱愛體育運動的圖靈在身心上受到極大的傷害。

1954年6月7日，圖靈被發現死於家中的床上。死因是氰化物中毒，警方調查結論是自殺。一代英靈，就此過早離去，成為人類科學史上的一大遺憾。