什麼是非確定性圖靈機？

就像在 PDA（部分 NFA）中一樣，非確定性對於一個輸入配置可能有多個可能的輸出。

非確定性圖靈機類似於圖靈機，但具有有限數量的移動選擇；對於相同的輸入“當前狀態和當前符號”，可能有多個移動。

如果至少存在一個計算對於輸入 w 正常停止，則非確定性圖靈機接受輸入 w。

對於下推自動機，非確定性比確定性更強大。但對於有限自動機，它沒有區別。

令人驚訝的是，確定性和非確定性圖靈機的功能相同。

注意

如果一個非確定性圖靈機接受語言 L，則存在一個確定性圖靈機也接受 L。

還有許多其他類似的機器，它們可能看起來功能更強大或更弱，但可以認為它們的功能與簡單的圖靈機相同（識別由無限制語法生成的相同的遞迴可列舉語言）——新增更多磁帶、更多控制單元等。

等價性是透過描述如何使用簡單的單磁帶圖靈機來模擬它們，反之亦然來證明的。

Bhanu Priya

更新於： 2021年6月16日

2K+ 閱讀量

啟動你的 職業生涯

透過完成課程獲得認證

開始學習