圖靈機簡介

今天計算機病毒課上老師給我們介紹了一下圖靈機。以前一直有聽說過圖靈機，今天簡單地了解了一下圖靈機，寫下一些學習過程中的收獲。

圖靈機是由圖靈大神由1936年提出的一種确定的抽象計算模型，據說它可以被看做是終極強大的邏輯機器。

圖靈的基本思想是用機器來模拟人們用紙筆進行數學運算的過程，他把這樣的過程看作下列兩種簡單的動作：

• 在紙上寫上或擦除某個符号；

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

而在每個階段，人要決定下一步的動作，依賴于（a）此人目前所關注的紙上某個位置的符号和（b）此人目前思維的狀态。

為了模拟人的這種運算過程，圖靈構造出一台假想的機器，該機器由以下幾個部分組成：

1. 一條無限長的紙帶TAPE。紙帶被劃分為一個接一個的小格子，每個格子上包含一個來自有限字母表的符号，字母表中有一個特殊的符号表示空白。紙帶上的格子從左到右依次被編号為0, 1, 2, …，紙帶的右端可以無限伸展。
2. 一個讀寫頭HEAD。該讀寫頭可以在紙帶上左右移動，它能讀出目前所指的格子上的符号，并能改變目前格子上的符号。
3. 一套控制規則TABLE。它根據目前機器所處的狀态以及目前讀寫頭所指的格子上的符号來确定讀寫頭下一步的動作，并改變狀态寄存器的值，令機器進入一個新的狀态。

4. 一個狀态寄存器。它用來儲存圖靈機目前所處的狀态。圖靈機的所有可能狀态的數目是有限的，并且有一個特殊的狀态，稱為停機狀态。

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

在最初的設計中圖靈機中是采用一種帶（tape）的東西作為臨時存儲，這種帶子無限長。帶可以被劃分成一個個的單元，每個機關隻包含一個符号。帶子的各個機關可以被讀寫頭讀寫，這個讀寫頭可以在帶子上左右移動，但是每次隻能讀寫一個符号。

我們可以把這個帶子和讀寫頭的關系跟國中使用過的複讀機的錄音帶、磁頭想類比。一般它直覺看起來像是這個樣子：

表示目前狀态為q0,讀寫頭的字元為a時，狀态轉移的時候會把這個讀寫頭所指的字元改為b,然後讀寫頭先左移動一個機關，狀态由q0變成q1.

通常圖靈機以一個給定的初始狀态和帶上的資訊開始，然後在狀态函數的指導下由一個狀态轉移到另外一個狀态。最後圖靈機将處于停機（halt state）狀态。當圖靈機到達一個狀态函數沒有定義的輸入時，圖靈機将會停止。另外，我們假定對于任意的狀态都沒有定義其轉移函數，圖靈機到達狀态的時候都會停機。

圖靈論題：

任何在算法上可計算的問題同樣可由圖靈機計算；

任何無法由圖靈機計算的問題都不可能找到解決的算法。