語言可判定性

如果存在一臺圖靈機，對於每一個輸入字串 w 都能接受並停機，則稱該語言為可判定或遞迴語言。每個可判定語言都是圖靈可接受的。

如果所有肯定例子的語言 L 是可判定的，則判定問題 P 是可判定的。

對於可判定語言，對於每個輸入字串，圖靈機都會在接受狀態或拒絕狀態停機，如下圖所示：

示例 1

找出以下問題是否可判定：

數字‘m’是否為素數？

解答

素數 = {2, 3, 5, 7, 11, 13, …………..}

從 ‘2’ 開始，將數字 ‘m’ 除以 ‘2’ 到 ‘√m’ 之間的全部數字。

如果任何這些數字產生餘數為零，則進入“拒絕狀態”，否則進入“接受狀態”。因此，答案可以是“是”或“否”。

因此，這是一個可判定問題。

示例 2

給定一個正則語言 L 和字串 w，我們如何檢查 w ∈ L？

解答

取接受 L 的 DFA 並檢查是否接受 w

一些其他的可判定問題：

• DFA 是否接受空語言？
• 對於正則集，L₁ ∩ L₂ = ∅ 是否成立？

注意：

• 如果語言 L 是可判定的，則其補集 L' 也是可判定的。

• 如果一個語言是可判定的，那麼它就存在列舉器。