目錄
其中可以看到儲存的空間稱作tape，在Turing的概念裡這個儲存空間是無限的，裡面可以存放像是a, b這字元，另外定義B是blank的符號代表空字元，而有一個控制器的元件可以對tape裡面的位置進行讀與寫，控制器決定現在讀寫的位置，能夠進行往左一格或往右一格的移動操作，這就是最早的計算機概念，但時至今日還是以這個概念為根源，就算是平行計算，也只需要多幾組tape跟control，以及多一點的符號來紀錄讀寫位置就可以實現。
有限自動狀態機與圖靈機的差異
- 圖靈機可以讀跟寫進tape裡
- 控制器的讀寫頭可以往左或往右移動
- tape的空間是無限的
- 有多兩個特殊的state叫做accept state跟reject state
範例
假設有一個Turing Machine \(M_{1}\)測試能不能接受一個Language B = {w#w: \(w \in {0, 1}^{*}\)}，這是一個做字串比對的Language，#代表區隔兩個不同字串，如果沒有讀到#就直接reject掉。
箭頭代表目前控制器的讀寫頭位置，首先我們讀進左邊第一個位置內容是一個0，用一個符號覆寫上去代表我們已經讀過了，接著往右移找到#，在讀取#右邊找第一個0，如果找到的話我們也用一個X來覆寫上去，就這樣來來回回檢查每一個同位置的符號，如果存在一個位置的符號不一樣的話就reject掉這個字串，掃瞄完到#左右邊如果有一邊還留有原先的符號代表兩個字串長度不同就reject掉，最後如果上面的都沒有被reject掉就accept，代表兩個字串是相同的。
Definition of Turing Machine
一個Turing Machine擁有7-tuple(\(Q, \Sigma, \Gamma, S, q_{0}, q_{accept}, q_{reject}\)), 其中\(Q, \Sigma, \Gamma\)屬於有限集合
- Q: 狀態集合(包含\(q_{0}, q_{1}, …, etc\))
- \(\Sigma\): 所有輸入的字母但不包含特殊符號B
- \(\Gamma\): tape的字母集合，其中{B}\(\in \Gamma\)並且\(\Sigma \subseteq \Gamma\)
- \(\delta:Q \times \Gamma \rightarrow Q \times \Gamma \times {L, R}\) ~ transition function: \(\delta (q, a) = (r, b, L)\)，L是Left讀寫頭往左，而R就是Right讀寫頭往右如下圖
5. \(q_{0} \in Q\): 是起始的狀態
6. \(q_{accept} \in Q\): 是Turing Machine接受輸入的狀態
7. \(q_{reject} \in Q\): 是Turing Machine拒絕輸入的狀態，而\(q_{reject} \neq q_{accept}\)
一個Turing Machine輸入字串後開始執行，最終會輸出accept或reject，也有可能永遠不會停止計算
在每一次計算中會改變
- 現在的狀態
- 現在Turing Machine tape的內容
- 現在讀寫頭的位置
以上三點稱作Turing Machine的”configuration”
假設 \(uqv\) 是一個configuration，\(q\)是目前的state，\(uv\)是目前tape裡面的內容，而\(v\)則是讀寫頭目前的位置，假設\(C_{1}, C_{2}\)是兩個configuration，我們說\(C_{1}\)得出(yields)\(C_{2}\)代表Turing Machine裡面存在合法的transition function讓\(C_{1}\)在一次計算過後變成\(C_{2}\)
\(uaq_{i}bv\) yields \(uq_{j}acv\) if \(\delta(q_{i}, b) = (q_{j}, c, L)\), where \(a, b \in \Gamma, u,v \in \Gamma^{*}\)
反之亦然，也可以讓state看到某個符號後往右移一格，\(uaq_{i}bv\) yields \(uacq_{j}v\) if \(\delta(q_{i}, b) = (q_{j}, c, R)\), where \(a, b \in \Gamma, u,v \in \Gamma^{*}\)
但要注意的是沒辦法讓讀寫頭移出到tape之外，代表不存在一個configuration \(uaq_{i}B\)，B符號通常是Blank的意思，代表字串的結尾
而起始的configuration可以看成 \(q_{0}w\)
如果Turing Machine接受輸入字串是合法的最後會變成\(q_{accept}\)的configuration
反之亦然，如果字串不是合法的狀態就變成\(q_{reject}\)
Halting Configurations
一個Turing Machine M接受輸入字串 w 如果存在一組configuration的順序是\(C_{1},C_{2},…,C_{k}\)以及以下的條件
- \(C_{1}\)是M接收w字串後的起始configuration
- 每一個\(C_{i}\)都可以得出(yields) \(C_{i+1}\)
- \(C_{k}\)是accepting configuration
就可以稱這個字串w對於Turing Machine M來說是合法的內容，而將這些合法的字串搜集起來就代表是M的language，表示成L(M)
所以可以更嚴謹的來定義一下Turing Machine：
定義1
一個language可以被Turing Machine給識別(recognizes 或是 recursively enumerable)的話可以稱這個language是Turing-recognizable，意思是如果Turing Machine存在合法的transition rules可以產出language所有的規則就可以進入到accept的狀態，但如果被拒絕的話無法分辨是不存在還是進入到無窮執行了。
定義2
一個language可以被Turing Machine給決定(decides 或是 recursive)的話稱這個language是Turing-decidable，意思是這些language可以被Turing Machine決定接受或者如果沒出現合法的transition rule可以得出language則明確的拒絕。
範例
使用\(\Sigma = {a, b}\)，設計一個Turing Machine M可以accept \(L = {a^{n}b^{n}: n \geq 1}\)
\(Q = {q_{0}, q_{1}, q_{2}, q_{3}, q_{4}}\)
\(\Sigma = {a, b}\)
\(\Gamma = {a, b, x, y, B}\)
\(q_{0}\): start state
\(q_{4}\): accept state
\(\delta(q_{0}, a) = (q_{1}, x, R)\);
\(\delta(q_{1}, a) = (q_{1}, a, R)\);
\(\delta(q_{1}, y) = (q_{1}, y, R)\);
\(\delta(q_{1}, b) = (q_{2}, y, L)\);
\(\delta(q_{2}, y) = (q_{2}, y, L)\);
\(\delta(q_{2}, a) = (q_{2}, a, L)\);
\(\delta(q_{2}, x) = (q_{0}, x, R)\);
\(\delta(q_{0}, y) = (q_{3}, y, R)\);
\(\delta(q_{3}, y) = (q_{3}, y, R)\);
\(\delta(q_{3}, B) = (q_{4}, B, R)\);
\(q_{0}aabb \vdash xq_{1}abb \vdash xaq_{1}bb \vdash xq_{2}ayb \vdash q_{2}xayb \vdash xq_{0}ayb \vdash xxq_{1}yb \vdash xxyq_{1}b \vdash xxq_{2}yy \vdash xq_{2}xyy \vdash xxq_{0}yy \vdash xxyq_{3}y \vdash xxyyq_{3}B \vdash xxyyBq_{4}\)
M accept language \(L = {a^{n}b^{n}: n \geq 1}\)
