众所周知,暂停问题不能有一个明确的解决方案,一个是a)返回true <==>程序确实停止了,b)处理任何输入,但我想知道是否有足够好的解决方案来解决问题,那些可以完美地处理某些类型的程序流程,或者能够识别何时无法正确解决问题,或者能够正确地解决问题,等等......
如果是这样,他们有多好,他们依赖什么想法/限制？
正常的方法是将程序行为限制为有效可计算的算法。例如，简单类型的 lambda 演算可用于确定算法始终停止。这意味着简单类型的 lambda 演算不是图灵完备的，但它仍然足够强大，可以表示许多有趣的算法。