Computing--狀態(tài)機和圖靈機

• Computing--圖靈機
• • 什么是圖靈機？
  • • Input and Tape Alphabet
    • Accepting and Rejecting States
  • 設(shè)計圖靈機
  • • 實例1
    • 實例2
    • 實例3

關(guān)于狀態(tài)機，請點擊鏈接： https://blog.csdn.net/qq_46041930/article/details/107733400.

Computing–圖靈機

什么是圖靈機？

圖靈機是最小的抽象模型。事實上，圖靈機非常類似于人類的大腦，擁有計算功能和存儲功能。
圖靈機由三部分組成：

Finite-state control 有限狀態(tài)機

Infinite Tape 無限長的磁帶

Tape Head 磁頭

實際上對于有限狀態(tài)機而言，狀態(tài)數(shù)是有限的，也就是說有限狀態(tài)機由于狀態(tài)數(shù)有限而無法計算無限長的序列，或者說有限狀態(tài)機沒有辦法存儲大量的狀態(tài)數(shù)。雖然它具備計算能力，但是卻沒有足夠的存儲空間。

磁帶相對于有限狀態(tài)機而言是一個外部的存儲設(shè)備，用來記錄有限狀態(tài)機的輸入、輸出和空間結(jié)果。磁帶是一個任意長的條狀帶，而且它可以分成一個個小的區(qū)域，每一個小的區(qū)域中存儲的字符都來自于有限狀態(tài)機的字符集。

磁頭指向磁帶中的一個個小的區(qū)域，然后從這當(dāng)中讀入字符，再重新向這個區(qū)域中寫入新的字符，最后磁頭選擇左移或者右移到下一個小的區(qū)域。

實際上圖靈機是現(xiàn)代計算機的雛形了，這里的磁帶就是CPU中的內(nèi)存，小的區(qū)域就是內(nèi)存中的一個個內(nèi)存單元，tape head就是用來尋址的CS:IP（指令計數(shù)器）。

Input and Tape Alphabet

圖靈機有兩個字符集，一個是輸入的字符集，另一個是磁帶中的字符集。初始時圖靈機中的磁帶是一串輸入和無限多的空格，同時磁頭指向第一個輸入字符所在的區(qū)域。

Accepting and Rejecting States

圖靈機開始工作后會一直進行，除非進入停止?fàn)顟B(tài)，因此存在圖靈機一直處于無限循環(huán)當(dāng)中。

設(shè)計圖靈機

實例1

設(shè)計一個圖靈機，輸入字符集為 $\Sigma$=$\{0,1\}$，功能為：判斷輸入的序列是否為L=$\{0^n{1}^n|n?N\}$。即序列是否為n個0與n個1拼接在一起？

solution：如圖所示，從初始位置開始判斷，若該位為1則小塊區(qū)域重寫成空格，磁頭右移一位且進入reject state；若為0則重寫成空格，磁頭右移一位之后再一直右移走到序列的最后（序列最后的空格前一位判斷是否為1），若為1則重寫成空格，以此類推序列兩頭對稱的比較0和1的個數(shù)是否相等。直到最后序列若全部重寫成空格（說明0和1的個數(shù)對等）則進入accept state，否則進入reject state。

實例2

設(shè)計一個圖靈機，統(tǒng)計序列中字母A的個數(shù)，并將個數(shù)轉(zhuǎn)換成二進制數(shù)顯示

solution：
實際上就是用二進制數(shù)來表示字母A的個數(shù)，每一輪去掃描序列。每輪掃描之后都在初始位置前一位填上一位二進制數(shù)。如果掃描到A的個數(shù)為偶數(shù)個，則這個一位二進制數(shù)填0，奇數(shù)個填1。 同時掃描的時候如果當(dāng)前位置到初始位置的A為偶數(shù)就將該位置的A替換成X。換言之，這不就相當(dāng)于是在除2取余嗎？

實例3

設(shè)計一個圖靈機，判斷序列中的0和1的個數(shù)是否相等？
！注意啦！這個題目和實例1就有所不同了，為啥呢？這是因為這個不要求序列是有序的0和1排列了，只要序列中0和1的個數(shù)相等就ok了。

solution：那么實際上我依然還是對稱的去匹配0和1，怎么理解呢？
就是說我從序列最左邊位置開始，每次找到一個0或者1，我就把這個數(shù)替換成x，然后接著立馬回到初始位置從頭掃描去找到1或者0。這樣0和1就這樣一個個匹配在一塊然后被替換成x了。所以最后序列就成了兩種情況，要么整個序列同時都變成x，那就說明0和1的個數(shù)相等了；要么序列中還有多余的0或者1，那就說明0和1的個數(shù)不等了。

~啦啦啦啦，說到這里大家明白了么，有啥問題留言哈，寫到這里也不容易，大家給個關(guān)注吧

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

總結(jié)

以上是生活随笔為你收集整理的Computing--图灵机的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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