可判定性的要点和重要性
如果 TM 识别该语言并进入“接受”或“拒绝”状态，则该语言是可判定的。作为一名开发人员。我认为这很重要，因为这意味着我们可以确定程序是否包含缓冲区溢出或死锁。此外，以下问题是不可判定的：
- 程序是否访问过未初始化的变量。
- 两个上下文无关语法是否描述相同的语言？
- 如果子例程的参数通过引用或复制结果传递，这有什么不同吗？
就可判定性而言，您认为可判定性的关键点是什么以及为什么可判定性很重要（特别是对于开发人员）。
注意：答案中的要点很好 - 我可以自己查找主题。我只想知道其中的要点是什么。
A language is decidable If a TM recognises the language and goes into an Accept or Reject state. As a dev. I think this is important as it would mean we could determine if a program contains buffer overflows or deadlocks. Also, the following problems are Un-Decidable:
- Does a program ever access an uninitialized variable.
- Do two context free grammars describe the same langauge.
- Does it make a difference if parameters to a subroutine are passed by reference or by copy-result
In terms of Decidability what would you say are the key points to Decidability and why is Decidability important (particularly to a developer).
Note: Bullet points are fine in answers - I can look up the topics myself. I just want to know what are the main points.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
也许这属于 cstheory 交易所，但无论如何我都会尝试一下。
关键点是：有些问题是不可判定的，即无法通过算法解决，因此应该通过其他方法来解决。这些问题中有许多与计算机语言有关的“元问题”，例如 检测病毒。
确定问题不可判定后，有几种可能的行动方案：
无应答。1 到 3 是流行的自动推理工具，包括程序验证器。 4 是病毒扫描程序的作用。当允许用户编写脚本来自动化大型系统时，5 是一个不错的选择 ;不要给他们完整的 JavaScript/Scheme/Lua/任何东西，而是给他们一个不允许无限递归/循环的受限子集。
Maybe this belongs in the cstheory exchange, but I'll have a go at it anyway.
The key point is: some problems are undecidable, i.e. not solvable by an algorithm, so they should be tackled by other methods. Among these problems are many "meta-problems" concerning computer languages, for instance the problem of detecting a virus.
Having determined that a problem is undecidable, there are several possible courses of action:
no answerwhen the time runs out.1 to 3 are popular for automated reasoning tools, including program verifiers. 4 is what virus scanners do. 5 is a good choice when allowing users to write scripts to automate a larger system; instead of giving them full JavaScript/Scheme/Lua/whatever, give them a restricted subset that does not allow unbounded recursion/loops.
假设您必须编写一些满足条件的软件：“在运行时，任何函数都不得直接或间接调用自身”。
该条件是不可判定的，但更具限制性的条件可能是可判定的，例如：“不得使用函数指针，并且函数不得包含直接或间接对自身的调用”。
这是为了强调，有时可以用灵活性来换取可判定性，以便系统的某些必需属性可以变得可执行。
如果一种编程语言是可判定的，那么总是可以判定一个程序是否是该语言的有效程序。
但即使一个程序对于该语言来说是有效的程序，仍然无法确定该程序是否会导致缓冲区溢出或死锁。
Suppose you have to write some software that satisfies the condition: "at runtime no function shall ever end up calling itself directly or indirectly".
That condition would be undecidable, but a more restrictive condition may be decidable, for instance something like: "no function pointers shall be used and no function shall contain calls to itself directly or indirectly".
This is to highlight that sometimes it is possible to trade flexibility for decidability, so that certain required properties of the system may become enforceable.
If a programming language is decidable, then it will always be possible to decide whether a program is a valid program for that language or not.
But even if a program is a valid program for that language, it remains undecidable whether that program may incur a buffer overflow or a deadlock.