-
非確定型圖靈機
鎖定
非確定型圖靈機(non-deterministic Turingmachine)確定型圖靈機的一種推廣。設P為一個由圖靈機指令組成的有窮集合,P不一定滿足相容性條件,如果把P作為程序,依類似於確定型圖靈機的模式進行運行,則可能會在某個時刻有兩條或更多的指令可以用,而它們所規定的動作又不一致。例如P中含有qaBq, BR和qoBq1BL兩條指令。則當內部狀態為q。且所指單元為空白時,這兩條指令都可用,但一個要右移,另一個則要左移。機便稱為非確定型圖靈機.對不確定型圖靈機M來説,對同一個輸入可能有不同的運行過程。
- 中文名
- 非確定型圖靈機
- 外文名
- non-deterministic Turingmachine
- 性 質
- 確定型圖靈機的一種推廣
- 領 域
- 計算機
非確定型圖靈機定義
如果不加特殊説明,通常所説的圖靈機都是確定型圖靈機。非確定型圖靈機和確定型圖靈機的不同之處在於,在計算的每一時刻,根據當前狀態和讀寫頭所讀的符號,機器存在多種狀態轉移方案,機器將任意地選擇其中一種方案繼續運作,直到最後停機為止。具體而言,其狀態轉移函數為
其中 Q是狀態集合,
是帶字母表,
分別表示讀寫頭向左和向右移動;符號
表示集合
的冪集,即
例如,設非確定型圖靈機
的當前狀態為
,當前讀寫頭所讀的符號為
,若
則 M將任意地選擇一個
,按其進行操作,然後進入下一步計算。
非確定型圖靈機 M在輸入串
上的計算過程可以表示為一棵樹,不同的分支對應着每一步計算的不同的可能性。只要有任意一個分支進入接受狀態,則稱 M接受
;只要有任意一個分支進入拒絕狀態,則稱 M拒絕
;某些分支可能永遠無法停機,但只要有一個分支可以進入接受或拒絕狀態,我們就説 M在輸入
上可停機。注意,我們規定 M必須是無矛盾的,即它不能有某個分支接受
而同時另一個分支拒絕
,這樣有矛盾的非確定型圖靈機是不合法的。
[1]
非確定型圖靈機相關定理
定理:對於任意一個非確定型圖靈機M,存在一個確定型圖靈機M',使得它們的語言相等,即
。
證明:因為非確定型圖靈機的計算過程就是一棵樹,因此我們只需遍歷該樹就可以模擬其計算過程。一個簡單的想法是利用深度優先搜索來遍歷 M的計算樹,但這樣行不通,因為 M的某些計算分支可能永遠不停機!所以我們可以採用一種在算法設計中稱為迭代加深搜索的技巧來遍歷 M的計算樹。具體證明如下:
對於非確定型圖靈機 M,構造一個確定型圖靈機M'如下:
1.令
;
2.深度優先地模擬 M的每個分支的計算,但每個分支最多隻計算 k步,如果某個計算分支在 k步內可以停機,則M'也停機,並將該計算分支的計算結果輸出。
3.令 k增加 1,跳轉到上一步繼續執行。
顯然,若 M有某個分支可以停機,則此 M'也一定會找到該分支並停機。因此
。
定理2:如果語言L被非確定型圖靈機 M在多項式時間內接受,則一定存在多項式P使得語言L被時間複雜度為
的確定型圖靈機程序所接受。
非確定型圖靈機圖靈機
圖靈機(英語:Turing machine),又稱確定型圖靈機,是英國數學家艾倫·圖靈於1936年提出的一種抽象計算模型,其更抽象的意義為一種數學邏輯機,可以看作等價於任何有限邏輯數學過程的終極強大邏輯機器。
[1]
非確定型圖靈機通用圖靈機
對於任意一個圖靈機,因為它的描述是有限的,因此我們總可以用某種方式將其編碼為字符串。我們用
表示圖靈機 M的編碼。
- 詞條統計
-
- 瀏覽次數:次
- 編輯次數:6次歷史版本
- 最近更新: w_ou