? ? ? ? 一些形式的圖靈機：雙向無窮、多維帶（帶子是平面）、多個帶子、一個帶上多個讀寫頭，非確定性圖靈機等。這些變形是等價的，即在能力上具有等價性：可以識別相同的語言類。因而：圖靈機具有穩健性。

? ? ? ? 下面分別證明：單帶圖靈機和多帶圖靈機以及非確定性圖靈機等價。

---

? ? 1：多帶圖靈機的定義

? ? ?特點：

1：有多個帶子，每個帶子有自己的讀寫頭。? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 2：初始狀態時：輸入只出現在第一條帶子，其他帶子都是空白。（因此：第一個帶子帶頭必須位于最左端，其他帶子的帶頭可以在任意位置）? ?

?多帶圖靈機的轉移函數（）：

? ? 這里的k是帶子的數量

指的是：當前處于狀態,讀寫頭1到k分別指向符號,...,,這時轉移到下一狀態時，把符號寫成,...,,且把每個帶子的讀寫頭移動到左,....,右。

2：多帶圖靈機與單帶圖靈機等價

? ? ? ? ?顯然，單帶圖靈機是特殊的多帶圖靈機，下面證明：多帶圖靈機能識別的語言，單帶圖靈機也能識別。

? ? ? ? 定理：每個多帶圖靈機都有與之等價的單帶圖靈機。

單帶TM模擬多帶TM有兩種方法：①：“分道”：每道模擬一個帶（改變字母表）②：每段模擬一條帶，這里采用第二種方法。

用單帶s模擬多帶m:

1:不同帶子之間用#分開，在首尾兩端也用#號（k個帶子需要k+1個#號）

2:s上的點叫“虛擬讀寫頭”，也就是做特殊標志，記住多帶m每個帶子讀寫頭所指位置。

3:如果多帶寫新符號，則s對應位置后的內容整體右移。

?具體實現：

S=“對于輸入w=:? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?1):S在自己的帶子上放入：###....#? ,此格式表示了M全部帶子的內容?

? ? ? ?2):為了模擬一步移動，S從第一個#號掃描直到最后一個#，目的是為了確定虛擬讀寫頭下的符號。（這一次掃描是記住每一個帶子的帶頭符號）然后S進行第二次掃描，并根據M的轉移函數指示的運行方式來更新帶子。（這是對每一個讀寫頭的改寫和帶頭移動的步驟）?

? ? ?? 3):任何時候，S的虛擬讀寫頭向右移動到某個#號時，就把這個位置的符號寫成B，然后把這個位置已右的所有內容向右平移一格，然后繼續模擬。（如果一個帶子讀寫頭移動到空白位置，則有寫新符號的可能，此時要把其他以右的內容右移一格，空出寫新符號的位置）? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?”

? ? ? ?這是一個構造性證明，正確性證明略（即：一個串，s接受m接受；s拒絕m拒絕）

? ? ? ?推論：圖靈可識別iff多帶圖靈機可識別? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ???一般：描述問題喜歡用多帶圖靈機，證明性質喜歡用單帶圖靈機

---

2：非確定性圖靈機（NTM）

特點：在計算的任何時刻，機器可以在多種可能性中去選擇一種繼續進行。

狀態轉移描述：P:冪集（所以子集的并），S：停止不動

? ? 格局間的轉換可以用計算樹描述。

? ? 1：停機接受，2：停機拒絕，?:可能永不停機（不確定）? ? 這里：每個結點表示一個格局，每個樹枝表示當前格局可以轉換下一格局的不同可能。

? ? ? ? ? 定理：每個NTM都有一個與之等價的確定性TM.

1：? NTM只要有一個分支可以接受此語言就說NTM可接收，所有分支都不能接收，才說不可計算

2：? NTM遍歷一般選用廣度搜索，因為深度搜索會導致某一分支永不停機從而進入死循環。

用多帶圖靈機TM D模擬非確定性圖靈機NTM N?

?輸入帶：單獨作為一條帶是因為每次模擬一個分支都需要讀輸入字符串。? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?模擬帶：用于模擬NTM的一個計算分支，存放N的帶子中的內容。? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?地址帶：又叫路徑帶，告訴當前結點要選擇的子結點，相當于確定分支（如：地址231，根節點出發尋找第二個子結點，再走第三個子結點，最后選擇第一個子結點。）

采用輪換方式，每個格局模擬幾步后，重新選擇路徑，以防選擇的分支永不停機。

pf:用DTM D模擬NTM N.? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?D="對輸入w:? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?①? ?初始狀態，第一個帶子包含w，另外兩個帶子為空。? ? ? ? ? ? ? ? ? ? ? ?

? ? ? ? ? ? ? ? ? ?②? ?把輸入帶內容復制到模擬帶上。（準備在此模擬各分支）? ?

? ? ? ? ? ? ? ? ? ?③? ?在第二個帶子上模擬N在輸入w上的某個非確定性的計算分支，這個分支由第三個帶子的地址指定。若遇到接收格局則接收，否則進入第四步。?

? ? ? ? ? ? ? ? ?? ④? ? 在第三個帶子上，用字典序（類似哈弗曼編碼樹，左小右大，先短再長）下的下一個串來代替原用的串，轉到第二步。? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??"（遍歷所有可能就相當于由非確定轉為確定）

推論：圖靈可識別當且僅當非確定圖靈機識別。圖靈可判定當且僅當確定性圖靈機判定

? ? ? ? ? ??（所有分支都得要么接收，要么拒絕，不能永不停機）。

---

圖靈機作為計算裝置的工作方式：? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?1：識別器---輸入x,輸出0/1/?? ? ? ?

? ? ? ? ? ?2:? ?判定器---輸入x,輸出0/1(要么接受，要么拒絕)? ? ? ? ? ? ? ?

? ? ? ? ? ?3：轉換器--輸入x,輸出y（輸出不同串，一般作為轉換函數）? ? ?

? ? ? ? ? ?4：產生器--輸入,輸出(從串中截取)? ?

? ? ? ? ? ?5：枚舉器--輸入，輸出,一般：無遺漏，無多余，可重復，無順序（枚舉一個語言）

? ? ? ? ? ? ? ? TH：圖靈可識別等價于圖靈可枚舉

---

（算法是直覺概念，圖靈機是數學概念。由于基于經驗是正確的，相當于物理中由實驗總結的規律，故而稱為論題）

? ? 圖靈機算法的描述：? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 1：形式描述--七元組? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 2：實現描述--不給出狀態和轉移函數的細節，只描述數據的存放和讀寫頭的移動。? ? ? ? ? ? ? ? ? ? ? ? 3：高層描述--用日常語言描述算法，不考慮讀寫頭和對帶的管理。

? ? 圖靈機的輸入必須是串，如果不是就需要編碼成串（如：圖，文法，多項式）

編碼的細節：? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 字符串： X=010,Y=11,=?

第一種：=001100101111(X和Y的各字符雙寫，再用01連接。讀到兩個連續不同符號就知道字符串結束了)? ||=2|x|+2|y|+2

第二種：=11111001011(X和Y的符號直接相連，記錄第一個串的字符串長度雙寫位于頭部，然后用10連接)? ? ||=|x|+|y|+2+2

第三種：=111110010? ? ?=11001011? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? =11111001011001011（將x和y分別把自己長度位于首部用10連接，然后兩個編碼后的字符串直接相連)? ?解碼方便

---

? ? ?描述圖靈機算法的的格式：帶引號的鋸齒狀日常語言文字段?? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 其中：第一行描述算法的輸入（暗含了TM會首先檢查輸入的對象編碼是否符合要求，否則拒絕）? ?

? ? ? :判定無向圖的連通性

? ?? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?高層描述：? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?M="輸入的是圖G的編碼:(描述首先指明輸入)? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?1：選擇G的一個頂點，做上標記。? ? ? ? ?

? ? ? ? ? ? ?2：重復下列步驟，直到沒有新的頂點可做標記。? ? ? ? ? ? ? ?

? ? ? ? ? ? ?3：對于G的每個頂點，如果它是帶標記頂點的:鄰接點，則給它做標記。?

? ? ? ? ? ? ?4：掃描G的所有頂點，如果都有標記則拒絕，否則接收。（判定依據）? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? "?

細節：

?1：編碼如右圖，頂點集合與邊? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?2：合法性檢查：頂點序列不可重復，邊序列不能包含不在頂點序列中的新節點。? ? ? ? ? ? ? ? ? ? ? ? ? ?3：步驟：①最左邊頂點加個點②在一個已加點畫個線做標記，再選任意一個未加點的的畫個線，去邊序列中尋找是否有兩條線的邊序列，有就將未加點的加個點③最后檢查是否都加了點。

總結

以上是生活随笔為你收集整理的图灵机2：等价变形+算法定义的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。