尽管一般情况无法确定，但是许多人仍然确实解决了对于日常使用而言足够合理的问题。

在科恩关于计算机病毒的博士学位论文中，他展示了病毒扫描与停止问题是等价的，但是我们面临着整个挑战。

我也看过微软的终结者项目http://research.microsoft.com/Terminator/

导致我问的是中止问题是否被高估了，我们是否需要担心一般情况？

类型是否会随着时间的推移而变得完整，这看起来像是一个不错的发展吗？

或者，换一种说法，我们是否将开始使用非图灵完整语言来获得静态分析的好处？

解决方案

回答

如果我们在一般情况下查看"停顿问题"，那么实际上只是很有趣，因为如果"停顿"问题是可以决定的，那么所有其他无法确定的问题也可以通过减少来决定。

因此，我对这个问题的看法是，不，在重要的情况下，这并不容易。也就是说，在现实世界中，这可能没什么大不了的。

另请参阅：http://en.wikipedia.org/wiki/Halting_problem#Importance_and_consequences

回答

作为一名日常程序员，我想值得继续走下去，以解决停顿风格的问题，即使我们只是达到极限而从未达到极限。正如我们所指出的，病毒扫描被证明是有价值的。 Google搜索并非伪装成"为我找到Y最好的X"的绝对答案，但它也非常有用。如果我释放出一种新型病毒(muwahaha)，是否会创建更大的解决方案集，还是只是对现有的问题区域进行研究？无论技术上的差异如何，有些公司都会以务实的方式开发并收取后续"检测和清除"服务的费用。

对于其他问题，我期待着真正的科学答案。

回答

Is solving the halting problem easier than people think?

我认为这和人们想的一样困难。

Will types become turing complete over time?

亲爱的，他们已经是！

dependant types do seem like a good development?

非常非常。

我认为非图灵完整但可证明的语言可能会有所增长。在相当长的一段时间内，SQL属于这一类(不再适用)，但这并没有真正减少其实用性。我认为，这样的系统肯定有一个地方。

回答

顺便说一句，我认为模板的图灵完整性表明停顿被高估了。大多数语言都保证其编译器将停止运行。不是C ++。这会削弱C ++作为一种语言吗？我不这么认为。它有很多缺陷，但是并不总是停止的编译不是其中之一。

回答

我不知道人们认为它有多难，所以我不能说它是否更容易。但是，我们认为正确的是，问题的不确定性(通常)并不意味着该问题的所有实例都是不确定的。例如，我可以很容易地告诉我们，" while false做某事"之类的程序会终止(假设while和false的明显语义)。

我们提到的Terminator项目之类的项目显然存在(甚至在某些情况下甚至可以工作)，因此很明显，并非所有项目都是无望的。对于试图证明重写系统终止的工具也有一场竞赛(我相信每年都会这样)，这些基本上都是计算模型。但是，在很多情况下终止很难证明。

最简单的看待方法可能是将不确定性视为问题实例化复杂性的最大化。每个实例化在达到这个最大值的微不足道的范围内，并且通常具有较高的最大值，实例化也平均而言也较难。

回答

有许多程序可以解决暂停问题，其中许多程序很有用。

如果编译器会告诉我们"暂停"，"不暂停"或者"不知道"，那么它可以告诉我们程序的哪一部分导致了"暂停"或者"不知道"情况。如果我们确实想要一个绝对停止或者不停止的程序，则可以通过消除编译器警告的相同方式来修复那些"不知道"的单元。我认为我们所有人都对尝试解决这个普遍不可能的问题证明有用的频率感到惊讶。

回答

哇，这是一个困惑的问题。

第一：从实际意义上讲，"停顿问题"不是"问题"，就像"需要解决的问题"一样。它是关于数学性质的陈述，类似于G？del的不完全性定理。

第二：建立一个完美的病毒扫描程序很棘手(因为它等同于停止问题)，这正是"围绕这个挑战建立整个行业"的原因。如果可以设计出一种完美的病毒扫描算法，那只需要别人做一次就可以了，那么就不再需要一个行业了。故事结束了。

第三：使用Turing Complete语言并不能消除"静态分析的好处"，它只是意味着静态分析存在局限性。没关系-无论如何，几乎我们所做的每件事都有局限性。

最后：如果停止问题可以以任何方式"解决"，那么它肯定"比人们想像的要容易"，图灵证明这是无法解决的。从数学的角度来看，一般情况是唯一相关的情况。具体情况与工程有关。