-
遞歸語言
鎖定
- 中文名
- 遞歸語言
- 又 稱
- 圖靈可判定語言
- 性 質
- 形式語言類型
- 領 域
- 計算機
目錄
- 1 定義
- 2 閉包性質
- 3 圖靈可判定語言與圖靈可識別語言的關係
遞歸語言定義
遞歸語言有兩種等價的主要定義:
設S⊆ Σ是一個語言,M是一台圖靈機, 若對於任何字符串 ω ∈ Σ,有
- ω ∈S當且僅當M接受 ω
- ω ∉S當且僅當M拒絕 ω
則稱M判定語言S。 若存在這樣的M,S就稱為圖靈可判定語言。
[1]
遞歸語言閉包性質
L的Kleene星號:
L的非刪除(non-erasing)同態:φ(L)
L和P的串接:
並集:
交集:
L的補集:
差集:
遞歸語言圖靈可判定語言與圖靈可識別語言的關係
注意圖靈可判定語言和圖靈可識別語言的區別:若S是圖靈可識別語言,則只需存在一 台圖靈機M,當M的輸入 ω ∈S時,M一定會 停機並進入接受狀態;當M的輸入 ω ∉S時,M可能停 機並進入拒絕狀態,或者永不停機。而若S是圖靈可判定語言,則必須存在圖靈機M, 使得對於任意輸入串 ω ∈ Σ,M總能停機,並根據 ω 屬於或不屬於S分別進入接受或拒絕狀態。
定理:存在圖靈不可判定語言。
證明:定義語言 HALTING 如下:
- HALTING = { <M,x> |M是一台圖靈機,x是一個字符串,且M在輸入x上可以停機}
其中 <M,x> 表示將M的編碼和串x以某種方式配對而得到的串。 可以證明 HALTING 是圖靈不可判定語言。
下列定理表明了圖靈可判定語言和圖靈可識別語言的關係。
定理:一個語言是圖靈可判定的當且僅當它和它的補語言都是圖靈可識別的。
證明:若S是圖靈可判定的,顯然S和S的補都是圖靈可識別的。 下面假設存在圖靈機M1和M2分別識別S和S的補,我們可以構造一個圖靈機M如下:
M= 對於輸入 ω
- 對於i= 1, 2, 3, ... 分別重複以下步驟:
- 將 ω 作為M1的輸入,模擬運行M1,如果M1可以在i步之內接受 ω,則M進入接受狀態並停機;
- 將 ω 作為M2的輸入,模擬運行M2,如果M2可以在i步之內接受 ω,則M進入拒絕狀態並停機。
很顯然,對於任何 ω,它要麼屬於S,要麼屬於S的補, 所以M1和M2中必然有且僅有一個 可以在有限步執行內接受 ω 。 若M1在k步內接受 ω,説明 ω 屬於S, 則當i=k時,M會接受 ω 並停機; 同理,若M2在k步內接受 ω, 説明 ω 屬於S的補,則當i=k時,M會拒絕 ω 並停機。於是M就判定了語言S。
根據上述定理直接可得下述引理:
定理:HALTING 的補語言是圖靈不可識別的。
- 參考資料
-
- 1. Michael Sipser (1997). "Decidability". Introduction to the Theory of Computation. PWS Publishing. pp. 151–170. ISBN 0-534-94728-X.
- 2. Fischer, Michael J.; Rabin, Michael O. (1974). "Super-Exponential Complexity of Presburger Arithmetic". Proceedings of the SIAM-AMS Symposium in Applied Mathematics. 7: 27–41.
- 詞條統計
-
- 瀏覽次數:次
- 編輯次數:2次歷史版本
- 最近更新: G敏吖吖