Formal Language - Ch9 圖靈機 Turing Machines

為何要定義圖靈機 (Turing machine)
圖靈機的基本思想是用機器來模擬人們用紙筆進行數學運算的過程，他把這樣的過程看作下列兩種簡單的動作

1. 在紙上寫上或擦除某個符號
2. 把注意力從紙的一個位置移動到另一個位置

而在每個階段，人要決定下一步的動作，依賴於

• 此人當前所關注的紙上某個位置的符號
• 此人當前思維的狀態

圖靈機具有有限步的操作和無限的記憶體 (無限的紙帶)。



圖靈機定義
圖靈機是一個七元組$(Q, \Sigma, \Gamma, \delta, q_0, q_{accept}, q_{reject})$，其中$Q, \Sigma, \Gamma$是有限集合，且滿足

1. $Q$是狀態集合；
2. $\Sigma$是輸入字母表，其中不包含特殊的空白符$\square$；
3. $b \in \Gamma$為空白符；
4. $\Gamma$是紙帶字母表，其中$\square \in \Gamma$且$\Sigma \subset \Gamma$；
• 紙帶字元集要有空，來表示沒寫的部分。
• 輸入的字元集屬於紙帶上的字元集，因為輸入要放到紙帶上
5. $\delta : Q \times \Gamma \to Q \times \Gamma \times \{L, R\}$是轉移函式，其中$L, R$表示讀寫頭是向左移還是向右移；
• 會根據當前機器的狀態，和讀寫頭所指的格子中的符號來轉移。
• 磁針向左/右，磁針移動前指向的符號可做改變。
6. $q_0 \in Q$ 是起始狀態；
7. $q_{accept} \in Q$ 是接受狀態。$q_{reject}\in Q$ 是拒絕狀態，且$q_{reject}\neq q_{accept}$ 。

例題一 : $A = \{0^{2^n} | n \geq 0\}$ 

例題二 : $B = \{w\#w | w \in \{0,1\}^*\}$ 

圖靈機的組態 Configuration : A configuration of the Turing machine consists of

• the current state
• the current tape contents
• the current head location

* 停機組態 (halting configuration) : accepting and rejecting.

圖靈機的轉移 $C_1$ yields $C_2$ : From configuration $C_1$ to configuration $C_2$

• $ua q_i bv$ yields $u q_j acv$ if $\delta(q_i, b) = (q_j,c,L)$。磁針向左，磁針移動前所指向的符號可改變。
• $ua q_i bv$ yields $uac q_j v$ if $\delta(q_i, b) = (q_j,c,R)$。磁針向右，磁針移動前所指向的符號可改變。

一般描述圖靈機的方法

一般定義演算法(Algorithm)的方式分成丘奇(Church)的$\lambda$演算和圖靈(Turing)的圖靈機，兩者是等價的。而就圖靈機而言，一般用以下方式來描述 :

• 真的寫出狀態機，也就是用圖靈機的正式數學定義描述
• 寫出狀態機的行為，也就是只描述紙帶上的磁頭如何操作
• 寫出演算法

描述圖靈機方法舉例

Recognizable and Decidable
The collection of strings that M accepts is the language of M, or the language recognized by M,denoted L(M).

• Turing-recognizable : some Turing machine recognizes it.
  recognize 意思是指吃到對的字串會報Yes，錯的不一定報No，可能當掉。
• Turing-decidable : some Turing machine decides it.
  decidable 意思是指吃到對的字串會報Yes，錯會報No，不會當掉。

這裏稍微提到 可識別 (Recognizable) 和 可決定 (Decidable) 這兩個詞，後面會很常使用，務必熟練：）

Turing-recognizable 與 Turing-decidable 關係圖

[補充] 計算理論介紹
計算理論和希爾伯特第十個問題、康托爾集合論、羅素悖論、哥德爾不完備定理及布林邏輯等息息相關，最早可以追溯到1900年，當時著名的大數學家希爾伯特(Hilbert)在世紀之交的數學家大會上給國際數學界提出了著名的23個數學問題。在當時，人們還不知道演算法是什麼。而因為後來圖靈奠定了計算理論基礎，人們才有可能發明20世紀以來甚至是人類有史以來最偉大的發明：電腦。因此人們稱圖靈為：電腦理論之父。

詳見計算的極限系列文章 :　
http://mropengate.blogspot.tw/2015/03/blog-post_25.html



Reference

交大陳穎平教授正規語言講義