【形式語(yǔ)言與自動(dòng)機(jī)】圖靈機(jī)

一、圖靈機(jī)

在經(jīng)過(guò)有限狀態(tài)機(jī)的介紹之后，再來(lái)看一種功能更強(qiáng)大的機(jī)器。

圖靈機(jī)基本結(jié)構(gòu)

                                                     

〉 一條分格的無(wú)限長(zhǎng)的紙帶，每格可容納一個(gè)字符
〉 一個(gè)讀寫(xiě)頭，可以在紙帶上移動(dòng)（可以雙向移動(dòng)，之前的有限狀態(tài)機(jī)只能單向移動(dòng)），讀出當(dāng)前格子的字符，重寫(xiě)格子上的內(nèi)容，改變自己的內(nèi)部狀態(tài)。所以它可以做三件事情，自身的狀態(tài)，可雙向移動(dòng)、可讀可寫(xiě)。
〉 一系列關(guān)于讀寫(xiě)頭動(dòng)作的規(guī)則（或者稱為程序、狀態(tài)轉(zhuǎn)移函數(shù)）

輸入、計(jì)算和輸出

〉 紙帶上的內(nèi)容（包括空白 B）是計(jì)算前的輸入和計(jì)算完成后的輸出。輸入輸出在同一條紙帶
〉 計(jì)算從讀寫(xiě)頭的初始狀態(tài) s0、初始位置和輸入的紙帶格局開(kāi)始
〉 按照規(guī)則進(jìn)行讀寫(xiě)頭的

總結(jié)

以上是生活随笔為你收集整理的【形式语言与自动机】图灵机的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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