文章目錄

• 一、多個帶子的圖靈機(jī)
• 二、證明過程設(shè)計
• 三、模仿操作
• 四、模仿帶子排列
• 五、模仿讀寫頭操作

一、多個帶子的圖靈機(jī)

---

多個帶子的圖靈機(jī) 指的是 圖靈機(jī)不止一個帶子 , 下圖是 $3$ 個帶子的圖靈機(jī) , 每條帶子有一個對應(yīng)的讀寫頭 , 總共有 $3$ 個讀寫頭 , 有 一個狀態(tài) , 該狀態(tài)根據(jù)指令進(jìn)行操作 ;

$3$ 個帶子的圖靈機(jī)當(dāng)前所處的狀態(tài)是 $\mathrm{q}$ , 三個讀頭所處的位置分別是 $1,\mathrm{a},\mathrm{b}$ , 三個帶子的圖靈機(jī)根據(jù)指令進(jìn)行操作 ,

首先將所處的 狀態(tài)從 $\mathrm{q}$ 轉(zhuǎn)換成 $\mathrm{p}$ 狀態(tài) ,

三個讀寫頭指向的字符需要 同時被擦掉 , 并寫入新字符 , 其操作看起來相當(dāng)于三個圖靈機(jī)同時進(jìn)行工作 , 有一種錯覺就是三個帶子的圖靈機(jī)的計算能力要超過一個帶子的圖靈機(jī) ;

事實上 , 三個帶子的圖靈機(jī)的計算能力 , 等同于 一個帶子的圖靈機(jī)的計算能力 ;

二、證明過程設(shè)計

---

證明過程 :

三個帶子的圖靈機(jī) , 如果其中兩個帶子不工作 , 等同于一個帶子的圖靈機(jī) , 因此 三個帶子的圖靈機(jī)的計算能力 大于等于 一個帶子的圖靈機(jī)的計算能力 ;

然后證明 三個帶子的圖靈機(jī)的計算能力 不會超過 ( 小于等于 ) 一個帶子的圖靈機(jī)的計算能力 ;

最終得到 三個帶子的圖靈機(jī)的計算能力 等同于 一個帶子的圖靈機(jī)的計算能力 ;

三、模仿操作

---

給定一個 三個帶子的圖靈機(jī) , 一定能找到一個 一個帶子的圖靈機(jī) , 可以模仿作出三個帶子圖靈機(jī)相同的計算任務(wù) ;

相同的計算任務(wù)的含義就是 兩個 圖靈機(jī) 接受的語言是相同的 ;

使用 一個帶子圖靈機(jī) 模仿 三個帶子圖靈機(jī) ;

設(shè)計 單個帶子圖靈機(jī) 指令集 , 模仿 三個帶子圖靈機(jī) 計算過程 ;

四、模仿帶子排列

---

帶子的字符排列 :

三個帶子圖靈機(jī) 一步計算中 , 修改了一次狀態(tài) , 同時讀寫頭修改了 $3$ 次字符 ;

一個帶子圖靈機(jī) 模仿 三個帶子圖靈機(jī) 上述 一步計算 , 在一個帶子圖靈機(jī)中 , 引入特殊字符 # ,

第 $1$ 個 # 與第 $2$ 個 # 之間的內(nèi)容是 第 $1$ 個帶子的內(nèi)容 ,

第 $2$ 個 # 與第 $3$ 個 # 之間的內(nèi)容是 第 $2$ 個帶子的內(nèi)容 ,

第 $3$ 個 # 與第 $4$ 個 # 之間的內(nèi)容是 第 $3$ 個帶子的內(nèi)容 ;

上述 $1$ 個帶子 可以模仿 $3$ 個帶子的內(nèi)容 ;

特殊字符 # 之間的空間很大 , 可能間隔十幾個到幾十個字符 , 依次排列即可 ;

排列順序如下 : # 第 $1$ 個帶子的字符串 # 第 $2$ 個帶子的字符串 # 第 $3$ 個帶子的字符串 #

五、模仿讀寫頭操作

---

讀寫頭操作 :

$1$ 個讀寫頭 模仿 $3$ 個讀寫頭 操作 :

$1$ 個讀寫頭 讀寫了 第 $1$ 個帶子的字符串 ,

其并不知道第 $2$ 個讀寫頭的位置 , 根據(jù)字符 $\mathrm{a}$ 是不能區(qū)分當(dāng)前的讀寫頭位置 , 第 $2$ 個帶子的字符串 中有多個 $\mathrm{a}$ 字符 ;

在字符集中 引入 特殊字符 , 如下圖中 第 $1$ 個帶子的字符串換中 紅色的 $1$ 與 黑色的 $1$ 是不同的字符 , 這兩個顏色 $1$ 有公共的部分 , 在指令集中 , 這兩個 $1$ 所起的作用是一樣的 ;

紅色的 $1$ 標(biāo)志的是讀寫頭所在的位置 , 使用紅色表示當(dāng)前讀寫頭的位置信息 ;

上圖中紅色的 $1$ 指的是第一個讀寫頭指向的字符 , 讀寫完畢后 , 繼續(xù)向右走 , 走到第二個讀寫頭指向的紅色的 $\mathrm{a}$ 位置 , 然后以此類推 ;

靠不同的字體顏色 區(qū)分出 不同的帶子 對應(yīng)的 讀寫頭指向的字符 , 這樣就可以實現(xiàn) $1$ 個帶子模擬多個帶子的圖靈機(jī) ;

使用 $1$ 個帶子的圖靈機(jī) 模擬 $3$ 個帶子的圖靈機(jī) 的代價是 讀寫頭必須從左向右整個遍歷一遍帶子 , 才能模擬 $3$ 個帶子的圖靈機(jī) 一步的計算 ;

《新程序員》：云原生和全面數(shù)字化實踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的【计算理论】图灵机 ( 多个带子的图灵机 | 计算能力对比 | 证明过程 | 一个带子图灵机 )的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。