computer-science - 可判定性的要点和重要性

Question

如果 TM 识别该语言并进入接受或拒绝状态，则语言是可判定的。作为开发者。我认为这很重要，因为这意味着我们可以确定程序是否包含缓冲区溢出或死锁。此外，以下问题是不可判定的:

• 程序是否访问过未初始化的变量。
• 是否有两个上下文无关文法描述相同的语言。
• 子例程的参数是通过引用传递还是通过复制结果传递有区别吗

就可判定性而言，您认为可判定性的关键点是什么，以及为什么可判定性很重要(尤其是对开发人员而言)。

注意:要点在答案中很好 - 我可以自己查找主题。我只想知道要点是什么。

Answer 1

也许这属于 cstheory exchange ，但无论如何我都会尝试一下。

关键是:有些问题是不可判定的，即无法通过算法解决，因此应该通过其他方法解决。在这些问题中有许多关于计算机语言的“元问题”，例如detecting a virus的问题。 .

确定问题不可判定后，有几种可能的行动方案:

1. 有些问题可能是半可判定的，即有一个半算法可以解决某些情况，但在其他情况下会永远循环。在实现半算法时，在其上放置一个计时器，并在时间用完时返回no answer。
2. 通过简化问题，只解决问题的少数关键部分。
3. 2 + 当问题变得过于复杂时，请用户提供意见。
4. 使用大部分时间都能得到正确答案的启发式方法。
5. 使用不同的语言，也许是非图灵完备的语言。

1 到 3 是流行的自动推理工具，包括程序验证器。 4 是病毒扫描程序的工作。 5 是 good choice当允许用户编写脚本来自动化更大的系统时；不要给他们完整的 JavaScript/Scheme/Lua/任何东西，而是给他们一个不允许无限递归/循环的受限子集。