文章目錄

• 一、接受狀態(tài)作用
• 二、格局
• 三、圖靈機(jī)語(yǔ)言
• 四、圖靈機(jī)設(shè)計(jì)復(fù)雜性

一、接受狀態(tài)作用

---

自動(dòng)機(jī) / 圖靈機(jī) 與 現(xiàn)實(shí)計(jì)算 的區(qū)別是 現(xiàn)實(shí)計(jì)算中 沒有 接受狀態(tài) 概念 ,

自動(dòng)機(jī) / 圖靈機(jī) 的目的是 將計(jì)算轉(zhuǎn)為一個(gè)集合 , 從數(shù)學(xué)角度研究計(jì)算 ;

設(shè)置了 接受狀態(tài) 概念 , 可以將字符串分為 接受字符串 , 非接受字符串 , 兩部分 ;

接受字符串可以組成一個(gè)集合 , 集合組成的語(yǔ)言 , 剛好對(duì)應(yīng) 計(jì)算模型 ;

此時(shí)就可以 將計(jì)算轉(zhuǎn)為集合 , 方便進(jìn)行數(shù)學(xué)證明 ;

圖靈機(jī) 一旦達(dá)到 接受狀態(tài) , 自動(dòng)停機(jī) ;

自動(dòng)機(jī) 即使達(dá)到了接受狀態(tài) , 也要將所有輸入字符讀取完畢 , 然后才停機(jī) ;

二、格局

---

格局 Configuration , 格局是給圖靈機(jī)照一個(gè) 快照 , 下圖就是圖靈機(jī)在計(jì)算過(guò)程中 , 某一個(gè)時(shí)刻的快照 ;

將圖靈機(jī)計(jì)算過(guò)程 , 每個(gè)步驟都照一份快照 , 通過(guò)軌跡將這些快照聯(lián)系到一起 , 就可以得到一個(gè)數(shù)據(jù)結(jié)構(gòu) ,

上述格局可以記作 $00\mathrm{q}1\mathrm{B}$ , 該寫法表示 與 某個(gè)格局 ( 快照 ) 一一對(duì)應(yīng) ;

在 圖靈機(jī)中 , 讀頭指向 $1$ , 就將狀態(tài)寫在 $1$ 的左邊 ;

三、圖靈機(jī)語(yǔ)言

---

給定一個(gè)字符串 , 將字符串寫在帶子上 , 讓圖靈機(jī)從開始狀態(tài) , 開始位置進(jìn)行計(jì)算 ,

如果在計(jì)算過(guò)程中的 某個(gè)時(shí)刻 , 圖靈機(jī)進(jìn)入接受狀態(tài) , 那么稱 該圖靈機(jī)是接受這個(gè)字符串的 ;

將圖靈機(jī) $\mathrm{M}$ 所 接受的所有字符串 $\mathrm{w}$ 都放在一起 , 組成一個(gè) 集合 $\mathrm{L}$ , 則該集合就是 圖靈機(jī) $M$ 的語(yǔ)言 ;

使用符號(hào)化表示為 : $\mathrm{L}(\mathrm{M})=\{\mathrm{w}|\mathrm{M}接受\mathrm{w}字符串\}$

四、圖靈機(jī)設(shè)計(jì)復(fù)雜性

---

圖靈機(jī)設(shè)計(jì)是一個(gè)很復(fù)雜的工程 , 與設(shè)計(jì)電路等同 , 需要注意很多微妙的地方 ;

圖靈給算法提供了一個(gè)嚴(yán)格的數(shù)學(xué)定義 , 如果要給一個(gè)算法提供一個(gè)嚴(yán)格的數(shù)學(xué)證明 , 必須將該算法寫出來(lái) , 即寫出該算法對(duì)應(yīng)的圖靈機(jī) , 設(shè)計(jì)一個(gè)簡(jiǎn)單算法對(duì)應(yīng)的圖靈機(jī)很復(fù)雜 ;

這里希望嚴(yán)格證明算法 , 但盡量避免設(shè)計(jì)圖靈機(jī) ;

設(shè)計(jì)一個(gè)圖靈機(jī) $\mathrm{M}2$ , 認(rèn)識(shí)一種特定語(yǔ)言 , 該語(yǔ)言由 $0$ 組成 , 字符串的長(zhǎng)度是 $2^{\mathrm{n}}$ 個(gè) , $\mathrm{n}=0,1,2,?$ ;

設(shè)計(jì)一個(gè)圖靈機(jī) , 認(rèn)識(shí)一種特定語(yǔ)言 , $\mathrm{B}=\{\mathrm{w}\#\mathrm{w}|\mathrm{w}是0和1組成的字符串\}$ ;

設(shè)計(jì)一個(gè)圖靈機(jī) , 作乘法運(yùn)算 , 語(yǔ)言為 $\mathrm{C}=\{{\mathrm{a}}^{\mathrm{i}}{\mathrm{b}}^{\mathrm{j}}{\mathrm{c}}^{\mathrm{k}}:\mathrm{i}\times \mathrm{j}=\mathrm{k}\}$ ;

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

總結(jié)

以上是生活随笔為你收集整理的【计算理论】图灵机 ( 接受状态作用 | 格局 | 图灵机语言 | 图灵机设计复杂性 )的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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