《離散數(shù)學(xué)-屈婉玲(形式語(yǔ)言與自動(dòng)機(jī)).ppt》由會(huì)員分享，可在線(xiàn)閱讀，更多相關(guān)《離散數(shù)學(xué)-屈婉玲(形式語(yǔ)言與自動(dòng)機(jī)).ppt（15頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1 11 4圖靈機(jī) 圖靈機(jī)的基本模型圖靈機(jī)接受的語(yǔ)言 遞歸可枚舉語(yǔ)言用圖靈機(jī)計(jì)算函數(shù) 部分可計(jì)算函數(shù)與可計(jì)算函數(shù) 2 問(wèn)題的提出 1900年D Hilbert在巴黎第二屆數(shù)學(xué)家大會(huì)上提出著名的23個(gè)問(wèn)題 第10個(gè)問(wèn)題 如何判定整系數(shù)多項(xiàng)式是否有整數(shù)根 要求使用 有限次運(yùn)算的過(guò)程 1970年證明不存在這樣的判定算法 即這個(gè)問(wèn)題是不可判定的 或不可計(jì)算的 3 計(jì)算模型 從20世紀(jì)30年代先后提出圖靈機(jī)A M Turing 1936年 轉(zhuǎn)換演算A Church 1935年遞歸函數(shù)K G del 1936年正規(guī)算法A A Markov 1951年無(wú)限寄存器機(jī)器J C Shepherdson 1963年 4 Church Turing論題 已經(jīng)證明這些模型都是等價(jià)的 即它們計(jì)算的函數(shù)類(lèi) 識(shí)別的語(yǔ)言類(lèi) 是相同的 Church Turing論題 直觀(guān)可計(jì)算的函數(shù)類(lèi)就是圖靈機(jī)以及任何與圖靈機(jī)等價(jià)的計(jì)算模型可計(jì)算 可定義 的函數(shù)類(lèi) 5 圖靈機(jī)的基本模型 定義圖靈機(jī) TM M Q q0 B A 其中 1 狀態(tài)集合Q 非空有窮集合 2 輸入字母表 非空有窮集合 3 帶字母表 非空有窮集合且 4 初始狀態(tài)q0 Q 控制器 6 圖靈機(jī)的基本模型 續(xù) 5 空白符B 6 接受狀態(tài)集A Q 7 動(dòng)作函數(shù) 是Q 到 L R Q的部分函數(shù) 即dom Q q s s R q 的含義 當(dāng)處于狀態(tài)q 讀寫(xiě)頭掃視符號(hào)s時(shí) M的下一步把狀態(tài)轉(zhuǎn)移到q 讀寫(xiě)頭把這個(gè)s改寫(xiě)成s 并向右移一格 q s s L q 的含義類(lèi)似 只是讀寫(xiě)頭向左移一格 若 q s 沒(méi)有定義 則M停機(jī) 7 一個(gè)TMM的實(shí)例 例1 8 格局 帶的內(nèi)容 當(dāng)前的狀態(tài)和讀寫(xiě)頭掃視的方格 q 其中 q Q初始格局 0 q0w 其中w 是輸入字符串接受格局 q q A停機(jī)格局 qs q s 沒(méi)有定義 1 2 從 1經(jīng)過(guò)一步能夠到達(dá) 2 稱(chēng) 2是 1的后繼 1 2 從 1經(jīng)過(guò)若干步能夠到達(dá) 2 圖靈機(jī)的計(jì)算 9 圖靈機(jī)的計(jì)算 續(xù) 計(jì)算 一個(gè)有窮的或無(wú)窮的格局序列 序列中的每一個(gè)格局都是前一個(gè)格局的后繼 w M從 0 q0w開(kāi)始的計(jì)算有3種可能 1 停機(jī)在接受格局 即計(jì)算為 0 1 n 其中 n是接受的停機(jī)格局 2 停機(jī)在非接受格局 即計(jì)算為 0 1 n 其中 n是非接受的停機(jī)格局 3 永不停機(jī) 即計(jì)算為 0 1 n 10 圖靈機(jī)接受的語(yǔ)言 定義 w 如果M從 0 q0w開(kāi)始的計(jì)算停機(jī)在接受格局 則稱(chēng)M接受輸入串w M接受的語(yǔ)言L(fǎng) M 是M接受的所有輸入串 即L M w M接受w 例1 續(xù) M關(guān)于輸入w 10100的計(jì)算 q010100B 1q00100B 10q0100B 101q000B 1010q00B 10100q0B 1010q10B 101q20BB 101Bq3BB由于停機(jī)在接受格局 故M接受10100 L M w00 w 0 1 11 圖靈機(jī)接受的語(yǔ)言 續(xù) 定義能被圖靈機(jī)接受的語(yǔ)言稱(chēng)作遞歸可枚舉的 記作r e 定理語(yǔ)言L(fǎng)是r e 當(dāng)且僅當(dāng)L是0型語(yǔ)言 圖靈機(jī)與0型文法是等價(jià)的 12 用圖靈機(jī)計(jì)算函數(shù) 上的m元部分字函數(shù) m的某個(gè)子集到 的部分函數(shù)TMM計(jì)算的m元部分字函數(shù)f 設(shè)輸入字母表為 x1 xm 如果M從初始格局 0 q0 x1B xmB開(kāi)始的計(jì)算停機(jī) 不管是否停機(jī)在接受狀態(tài) 從停機(jī)時(shí)帶的內(nèi)容中刪去 以外的字符 得到字符串y 則f x1 x2 xm y 如果M從初始格局 0開(kāi)始的計(jì)算永不停機(jī) 則f x1 x2 xm 沒(méi)有定義 記作f x1 x2 xm 例1 續(xù) M計(jì)算函數(shù) x 0 1 13 數(shù)論函數(shù) 數(shù)論函數(shù) 自然數(shù)集合N上的函數(shù)N上的m元部分函數(shù)N上的m元全函數(shù) 在Nm的每一點(diǎn)都有定義例如x y是全函數(shù) x y是部分函數(shù) 當(dāng)x y時(shí) x y 一進(jìn)制表示 用1x表示自然數(shù)x例如111表示3 空串 表示0數(shù)論函數(shù)的一進(jìn)制表示 字母表 1 上的字函數(shù) 用一進(jìn)制表示自然數(shù)例如x y可表成f 1x 1y 1x y 14 遞歸函數(shù) 定義設(shè)f是N上的m元部分函數(shù) 如果圖靈機(jī)M計(jì)算f的一進(jìn)制表示 即M的輸入字母表為 1 x1 xm N 從初始格局 0 開(kāi)始 若f x1 xm y 則M的計(jì)算停機(jī) 且停機(jī)時(shí)帶的內(nèi)容 不計(jì) 1 以外的字符 為1y 若f x1 xm 則M永不停機(jī) 那么稱(chēng)M以一進(jìn)制方式計(jì)算f 定義圖靈機(jī)M以一進(jìn)制方式計(jì)算的N上的m元部分函數(shù)稱(chēng)作部分遞歸函數(shù) 或部分可計(jì)算函數(shù) 部分遞歸的全函數(shù)稱(chēng)作遞歸函數(shù) 或可計(jì)算函數(shù) 15 遞歸函數(shù) 續(xù) 例1 續(xù) M以一進(jìn)制方式計(jì)算 這是一個(gè)部分遞歸函數(shù)