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

Question

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

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

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

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

Answer 1

也许这属于ctheory 交流，但无论如何我都会尝试一下。

关键是：有些问题是不可判定的，即不能用算法解决，所以应该用其他方法来解决。在这些问题中，有许多与计算机语言有关的“元问题”，例如检测病毒的问题。

确定问题无法确定后，有几种可能的行动方案：

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

1 到 3 对自动推理工具很流行，包括程序验证器。4 是病毒扫描程序的作用。当允许用户编写脚本以自动化更大的系统时，5 是一个不错的选择；与其给他们完整的 JavaScript/Scheme/Lua/whatever，不如给他们一个不允许无限递归/循环的受限子集。

Answer 2

假设您必须编写一些满足条件的软件：“在运行时，任何函数都不应直接或间接地调用自身”。

该条件将是不可判定的，但更严格的条件可能是可判定的，例如：“不得使用函数指针，且任何函数不得直接或间接包含对其自身的调用”。

这是为了强调有时可以用灵活性来换取可判定性，以便系统的某些必需属性可能变得可执行。

如果一种编程语言是可判定的，那么总是可以判定一个程序是否是该语言的有效程序。

但是，即使一个程序对于该语言来说是一个有效的程序，该程序是否会导致缓冲区溢出或死锁仍然无法确定。