为什么停止问题很重要呢?

发布网友 发布时间：2022-06-26 11:32

我来回答

共3个回答

热心网友 时间：2024-10-21 03:06

停止问题是描述计算的基本局限性的一种简单而具体的方法——它是理解不确定性的起点。我们能用电脑解决什么问题?也许更明显的是，有什么问题是我们不能解决的，即使我们有无限的资源?

在学习计算理论之前，我从来没有想过这些问题。如果你当时催促我，我会猜想只要有足够的时间和内存，我们就能解决任何问题。存在纯粹理论(而非实践)极限的事实是对计算本质的巨大启示。

这也有实际的后果:许多现实世界的问题是无法决定的。如果我们想要接近它们，我们需要了解它们的本质:因为我们先天知道，我们不可能完美地解决这些问题，我们可以直接跳到它们周围去工作。这在静态分析中总是会出现，因为几乎任何静态分析问题都是无法确定的(参见Rice定理)。我们必须做几件事中的一件

保守地解决这个问题——我们可以有错误的肯定但没有错误的否定，或者反之亦然。有时不能解决问题——如果分析运行的时间太长，

例如，问题-静态类型可以被看作是完整语言语义的近似，*这个问题——定义一个非图灵完备的语言，而不是使用现有的图灵完备的语言

了解这些问题是如何以及为什么无法确定的，可以让我们立即解决其中的一个问题，而不是徒劳地寻找一个完美的解决方案。

而“停止”问题则是发展这种认识的一个完美起点:有一个简单的证据证明停止的问题是不可决定的，我们可以系统地将其他不可定问题简化为停止问题，为证明问题不可定提供了有力的技术。这种方法得到一个普遍的结果——前面提到的赖斯定理

对于为什么不可判定的问题是不可判定的，我们有了一个很好的直觉:当我们去解决它们时，我们可能需要运行一个算法任意的时间，我们永远不知道我们最终会得到一个结果还是它会永远运行下去

停顿问题是对可计算性理论的一个完美的介绍，这就是为什么它在这一主题的课堂和教科书中具有突出的特点。

顺便说一下，如果您对此感兴趣并且想了解更多，我可以强烈推荐Sipser的《计算理论导论》。这是我读过的最好的和最容易理解的教科书之一。

热心网友 时间：2024-10-21 03:07

热心网友 时间：2024-10-21 03:07