1、所謂的圖靈機就是指一個抽象的機器，它有一條無限長的紙帶，紙帶分成瞭一個一個的小方格，每個方格有不同的顏色。有一個機器頭在紙帶上移來移去。機器頭有一組內部狀態，還有一些固定的程序。在每個時刻，機器頭都要從當前紙帶上讀入一個方格信息，然後結合自己的內部狀態查找程序表，根據程序輸出信息到紙帶方格上，並轉換自己的內部狀態，然後進行移動。
2、1936年，英國數學傢阿蘭麥席森圖靈(1912―-1954年)提出瞭一種抽象的計算模型——圖靈機(Turingmachine)。圖靈機，又稱圖靈計算機，即將人們使用紙筆進行數學運算的過程進行抽象，由一個虛擬的機器替代人類進行數學運算。
