2015年5月22日 星期五

Formal Language - Ch9 圖靈機 Turing Machines

2 則留言:
 

為何要定義圖靈機 (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

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





2 則留言:

技術提供:Blogger.