要点和可决定性的重要性

Question

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

• 程序是否曾经访问过非初始化的变量。
• 做两个免费语法描述相同的语法。
• 如果通过参考或通过复制复制传递子例程的参数，这会有所作为吗

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

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

Answer 1

也许这属于 csheory交换, ，但无论如何我都会去。

关键点是：一些问题是不确定的，即无法通过算法解决，因此应通过其他方法解决它们。这些问题包括许多有关计算机语言的“元问题”，例如 检测病毒.

确定问题是不可决定的，有几种可能的行动：

1. 有些问题可能是半确定的，即有一个 半- 算法可以解决某些情况，但在其他情况下永远循环。实现半有利值时，请在其上放一个计时器并返回 no answer 时间用完了。
2. 通过简化问题，只能解决问题的关键部分。
3. 2 +当问题变得太复杂时，向用户询问输入。
4. 使用获得正确答案的启发式 最多 的时间。
5. 使用不同的语言，也许是一种不充实的语言。

1至3在包括程序验证器在内的自动推理工具中很受欢迎。 4是病毒扫描仪的作用。 5是 好的选择 当允许用户编写脚本以自动化较大系统时；与其给他们完整的JavaScript/Scheme/Lua/其他，不如给他们一个受限制的子集，不允许无界的递归/环。

Answer 2

假设您必须编写一些满足条件的软件：“在运行时，任何功能最终都不会直接或间接地自称”。

该条件是不可决定的，但是可以确定更限制的条件，例如：“不得使用功能指针，并且不得直接或间接任何功能都包含对自己的呼叫”。

这是为了强调，有时可以为可确定性交易灵活性，以便系统的某些必需属性可以强制执行。

如果编程语言是可以决定的，那么将始终可以决定程序是否是该语言的有效程序。

但是，即使程序是该语言的有效程序，该程序是否可能导致缓冲区溢出或僵局。