语言可判定性

如果存在一台图灵机，对于每一个输入字符串 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' 也是可判定的。

• 如果一个语言是可判定的，那么它就存在枚举器。