计算理论中的可判定和不可判定问题
先决条件–图灵机
如果我们总能构造出一个能正确回答问题的相应的算法，那么一个问题就被称为可判定。我们可以通过一个简单的例子直观地理解可判定问题。假设我们被要求计算 1000 到 2000 范围内的所有素数。为了找到这个问题的解，我们可以很容易地设计出一个算法，可以枚举这个范围内的所有素数。
现在从图灵机的角度来讨论可判定性，如果存在一个相应的图灵机，该图灵机在每次输入时都用一个答案是或否来停止，那么这个问题就被称为可判定性问题。知道这些问题被称为图灵可判定也很重要，因为图灵机总是在每一次输入时停止，接受或拒绝它。
半可判定问题– 半可判定问题是指图灵机在其接受的输入上暂停，但它可以在被图灵机拒绝的输入上暂停或永远循环。这些问题被称为图灵可识别问题。
示例–我们现在将考虑几个重要的可判定问题:
- 两种常规语言 L 和 M 是否等价？ 我们可以通过设置差异操作轻松检查这一点。 L-M =空，M-L =空。 因此(L-M) U (M-L) = Null，那么 L、M 是等价的。
- CFL 的成员？ 通过使用基于动态规划的算法，我们总能发现给定 CFL 中是否存在字符串。
- CFL 的空虚 通过检查 CFL 的产生规则，我们可以很容易地陈述语言是否产生任何字符串。
不可判定问题– 我们无法在有限时间内构造出能够正确回答问题的算法的问题被称为不可判定问题。这些问题可能是部分可判定的，但它们永远不会是可判定的。也就是说，总会有一个条件会导致图灵机进入无限循环，而根本不提供答案。
我们可以通过考虑费马定理来直观地理解不可判定的问题，这是一个流行的不可判定的问题，指出对于任何 n > 2，没有三个正整数 a、b 和 c 能够满足以下等式:a^n + b^n = c^n.
如果我们把这个问题交给图灵机去寻找这样一个给出矛盾的解，那么图灵机可能会永远运行，去寻找 n、a、b 和 c 的合适值。但是我们总是不确定矛盾是否存在，因此我们把这个问题称为不可判定问题。
示例–这些是少数几个重要的不可判定的问题:
- 一个 CFG 是否会生成所有的字符串？ 由于一个 CFG 生成无限个字符串，我们永远无法到达最后一个字符串，因此它是不可判定的。
- 两个 CFG L 和 M 是否相等？ 由于我们不能确定任何一个 CFG 的所有字符串，所以我们可以预测两个 CFG 是否相等。
- CFG 的歧义？ 不存在能够检查 CFL 模糊度的算法。我们只能检查 CFL 的任何特定字符串是否生成了两个不同的解析树，然后 CFL 是不明确的。
- 有没有可能把一个给定的模棱两可的 CFG 转换成相应的非模棱两可的 CFL？ 这也是一个不可判定的问题，因为不存在任何算法来将模棱两可的 CFL 转换成不模棱两可的 CFL。
- CFL 的语言学习有规律吗？ 这是一个不可判定的问题，因为我们无法从 CFL 的生产规则中发现它是否正规。
更多与图灵机相关的不可判定问题:
- 图灵机的成员资格问题？
- 图灵机的有限性？
- 图灵机的空？
- 图灵机接受的语言是正规的还是 CFL 的？
版权属于：月萌API www.moonapi.com，转载请注明出处
