问题标签 [halting-problem]

System.currentTimeMillis()让我们观察以下在for循环中使用的 Java 代码段。

在上面的代码中，final long类型变量保存了系统维护的当前毫秒数，尽管循环陷入无限循环，但CURRENT_MILLIS它始终小于Java(MAX_VAL)中数据类型的大小。如何？longfor

集合中有不同的值，这个算法（伪代码）会终止吗？

请注意，我假设如果我们位于数组的末尾，我们将从头开始。

出于好奇，我开始编写以下方法：

为什么Java允许我写这个？此方法永远不会返回任何Object内容，并且会导致StackOverflow Error.

这里有很多关于 SO 的相关问题，但他们都询问是否编写程序来计算任意算法的复杂度（这显然是无法确定的）。我愿意对输入做以下限制：

1. 算法终止
2. 该算法是纯函数式的

问题是，是否可以编写一个程序来通过静态分析计算这种算法的时间复杂度？如果输入算法没有终止，则程序行为未定义（它可能会崩溃、返回谎言或无法终止）。

也就是说，图灵机能否将形式系统 S 作为其输入并确定 S 是否是图灵完备的？

我认为这是一个无法确定的问题，对吗？

如果它是不可判定的，为什么我们（作为人类）可以决定图灵完备性？

有几个地方说所有的agda 程序都会终止。但是我可以构造一个这样的函数：

语法高亮似乎不喜欢它，但没有编译错误。

计算stall 0结果的正规形式0。计算结果stall 1会导致 Emacs 挂在看起来很像非终止循环的地方。

这是一个错误吗？或者 Agda 有时可以永远运行吗？还是发生了更微妙的事情？

我有大量的正则表达式在匹配时调用特定的 http 处理程序。一些较旧的正则表达式无法访问（例如a.c* ⊃ abc*），我想修剪它们。

有没有给出两个正则表达式的库会告诉我第二个是否是第一个的子集？

起初我不确定这是可以决定的（它闻起来像是一个不同名称的停止问题）。但事实证明这是可判定的。

停止问题指出，一个程序不可能预测另一个程序的输出，或者它是否会终止。

这让我开始思考......基于启发式的扫描器如何确定给定的可执行程序的指令是否“类似病毒”，因为这将完全涉及预测程序将要做什么？

所以我们有一个通用图灵机 U，它应该确定输入 x 的图灵机 M 是否会停止。解决方案应以伪代码形式呈现。

有人可以帮我解决一下，我应该解决谁？

有一个工具叫做FindBugs它可以检测给定程序/代码库中的无限循环。

这意味着FindBugs可以通过分析代码来检测程序是否会结束。停止问题是定义以下问题的问题：

给定任意计算机程序的描述，决定程序是完成运行还是永远继续运行

那么这是否意味着停止问题已解决或停止问题的子集已解决？