非確定性圖靈機



在非確定性圖靈機中,對於每個狀態和符號,圖靈機都有一組可以執行的操作。因此,這裡的轉換不是確定性的。非確定性圖靈機的計算是一個從起始配置可以到達的配置樹。

如果樹中至少有一個節點是接受配置,則接受輸入,否則不接受。如果計算樹的所有分支在所有輸入上都停止,則非確定性圖靈機稱為**判定器**,如果對於某些輸入,所有分支都被拒絕,則該輸入也被拒絕。

非確定性圖靈機可以正式定義為一個 6 元組 (Q, X, ∑, δ, q0, B, F),其中 -

  • Q 是一個有限的狀態集

  • X 是帶字母表

  • 是輸入字母表

  • δ 是一個轉移函式;

    δ : Q × X → P(Q × X × {左移, 右移}).

  • q0 是初始狀態

  • B 是空白符號

  • F 是最終狀態集

廣告