【正文】 第一個(gè)符號(hào)，帶上 v 的字符最后字符以后的符號(hào)都是空白符。 例如 ?: (q, a) = (r, b, L) 22 圖靈機(jī)的計(jì)算方式 ?開(kāi)始時(shí)， M 以最左邊的 n 個(gè)帶方格接收輸入 w=w1w2… wn ? ?*，帶的其余部分保持空白 (即填以空白符 )，讀寫(xiě)頭從最左邊的帶方格開(kāi)始運(yùn)行，注意 ? 不含空字符 ，故 出現(xiàn)在帶上的第一個(gè)空字符表示輸入的結(jié)束 。 (4) ? : Q ?? Q ? { L, R }是轉(zhuǎn)移函數(shù)。 (2) 當(dāng) 左邊的所有符號(hào)都被消去時(shí)，檢查 右側(cè)是否還有符號(hào)，如果有則拒絕，否則接受。 (4)圖靈機(jī) 進(jìn)入拒絕和接受狀體將立即停機(jī) 。 計(jì)算過(guò)程中讀寫(xiě)頭左右移動(dòng)，機(jī)器內(nèi)部狀態(tài)改變，帶子上內(nèi)容重寫(xiě)。 ?丘奇 —圖靈論題：一切合理的計(jì)算模型都等同于圖靈機(jī) . 8 主要內(nèi)容 丘奇 —圖靈論題 圖靈機(jī)的形式化定義 圖靈機(jī)的例子 圖靈機(jī)的變形 多帶圖靈機(jī) 非確定型圖靈機(jī) 枚舉器 與其他模型的等價(jià)性 算法的定義 希爾伯特問(wèn)題 描述圖靈機(jī)的術(shù)語(yǔ) 9 圖靈機(jī) (Turning Machine) 非形式化描述 根據(jù)當(dāng)前狀態(tài)和字符 xi ，決定 寫(xiě) 移 轉(zhuǎn) 三動(dòng)作 寫(xiě) letter, 有存儲(chǔ)器 左或右移動(dòng) 轉(zhuǎn)移狀態(tài) 可以作循環(huán)語(yǔ)句 磁帶相當(dāng)于數(shù)組，可讀寫(xiě)。1 樸秀峰 計(jì)算理論 2 引言 ?什么是計(jì)算？ ?計(jì)算機(jī)的基本能力和局限性是什么？ ????其它情況個(gè)的展開(kāi)式中連續(xù)有若 05 1)( nng ?3 引言 計(jì)算機(jī)科學(xué)歷史上關(guān)于概念的爭(zhēng)論 ?什么是計(jì)算 ?什么是操作系統(tǒng) 基本上解決 ?什么 inter ? ?什么是數(shù)據(jù)庫(kù) ?什么是數(shù)據(jù)倉(cāng)庫(kù) 還在爭(zhēng)論 ?什么是數(shù)據(jù)網(wǎng)格 ?解決方法， 給出大眾能理解的代表 4 引言 計(jì)算機(jī)科學(xué)歷史上關(guān)于概念的爭(zhēng)論 ?解決的辦法， 給出一個(gè)代表 ?什么是 3的倍數(shù) { 3N |N=1,2,3}, {x| x mod 3 =0} ?代表元 ： 3 ?什么是操作系統(tǒng) 代表元： Windows, Unix ?什么 inter 代表元：大眾理解： Web ， IE ?什么是計(jì)算 ? 多個(gè)模型；代表元：圖靈機(jī) , 或 遞歸函數(shù)論 5 引言 在還沒(méi)有計(jì)算機(jī)的時(shí)候， 憑想象力 把后來(lái)出現(xiàn)的 把計(jì)算機(jī)的理論模型建立起來(lái)了。這是增加的重要資源 internal state set Q R L ?__10_1101每一步，讀寫(xiě)頭在單向無(wú)窮帶上左右移動(dòng)并讀寫(xiě)。 ?數(shù)組結(jié)構(gòu) 11 圖靈機(jī) 輸出約定 三種輸出：接受、拒絕、循環(huán) state qaccept ?? _vvv m21state qreject ?? _vvv m21or 非常規(guī)意義循環(huán) —— 不停機(jī) 引出可判定性 12 圖靈機(jī)與有限自動(dòng)機(jī) 狀態(tài) 控制器 a a b ? ? 相似性：有限狀態(tài)集 區(qū)別： (1)圖靈機(jī)在帶子上 既能讀也能寫(xiě) 。 13 圖靈機(jī) ?考慮圖靈機(jī) M1，它檢查語(yǔ)言 B = { ww | w∈ {0,1}* } 的成員關(guān)系?！? 14 M1 的運(yùn)行示意圖 0 1 1 0 0 0 1 1 0 0 ? ? ? ? X 1 1 0 0 0 1 1 0 0 ? ? ? ? X 1 1 0 0 0 1 1 0 0 ? ? ? ? X 1 1 0 0 0 1 1 0 0 ? ? ? ? M Tape head moves to right 15 M1 的運(yùn)行示意圖 X 1 1 0 0 0 1 1 0 0 ? ? ? ? X 1 1 0 0 0 1 1 0 0 ? ? ? ? X 1 1 0 0 X 1 1 0 0 ? ? ? ? X 1 1 0 0 X 1 1 0 0 ? ? ? ? M Tape head moves to left 16 M1 的運(yùn)行示意圖 X 1 1 0 0 X 1 1 0 0 ? ? ? ? X 1 1 0 0 X 1 1 0 0 ? ? ? ? X X 1 0 0 X 1 1 0 0 ? ? ? ? X X 1 0 0 X 1 1 0 0 ? ? ? ? M Tape head moves to right 17 M1 的運(yùn)行示意圖 X X 1 0 0 X 1 1 0 0 ? ? ? ? X X 1 0 0 X 1 1 0 0 ? ? ? ? X X 1 0 0 X X 1 0 0 ? ? ? ? X X 1 0 0 X X 1 0 0 ? ? ? ? M Tape head moves to left 18 M1 的運(yùn)行示意圖 X X 1 0 0 X X 1 0 0 ? ? ? ? X X 1 0 0 X X 1 0 0 ? ? ? ? X X X 0 0 X X 1 0 0 ? ? ? ? X X X 0 0 X X 1 0 0 ? ? ? ? M Tape head moves to right 19 M1 的運(yùn)行示意圖 X X X X X X X X X 0 ? ? ? ? X X X X X X X X X X ? ? ? ? X X X X X X X X X X ? ? ? ? M X X X X X X X X X X ? ? ? ? Tape head moves to left 20 M1 的運(yùn)行示意圖 X X X X X X X X X X ? ? ? ? X X X X X X X X X X ? ? ? ? X X X X X X X X X X ? ? ? ? M X X X X X X X X X X ? ? ? ? accept Tape head moves to right 21 圖靈機(jī)的形式化定義 定義 圖靈機(jī)是一個(gè) 7 元組 (Q, ?, ?, ?, q0, qaccept, qreject) (1) Q 是狀態(tài)集。 (5) q0 是起始狀態(tài)。 ? M 開(kāi)始運(yùn)行后，計(jì)算根據(jù)轉(zhuǎn)移函數(shù)所描述的規(guī)則進(jìn)行，如果 M 試圖將