问题标签 [halting-problem]

我需要一些帮助来证明Total问题不是递归的（可判定的）。

我知道Halting问题的对角化证明，我只需要Total问题的相同证明。我发布了停止问题证明以供参考：

停止问题证明

假设我们可以决定停机问题。那么存在一些总函数 Halt 使得

在这里，我们对所有程序进行了编号，[x] 指的是此顺序中的第 x 个程序。我们可以将 Halt 视为从 ℵ 到 ℵ 的映射，将其输入视为一个数字，表示通过 one-one on 函数配对两个数字

现在，如果 Halt 存在，那么 Disagree 也存在，其中

由于不同意是从 ℵ 到 ℵ 的程序，因此可以通过 Halt 来推断不同意。令 d 满足 Disagree = Φd，则

Disagree(d) 已定义 ⇔ Halt(d,d) = 0 ⇔ Φd (d) 未定义 ⇔ Disagree(d) 未定义

但这意味着不同意与它自己的存在相矛盾。由于我们采取的每一步都是建设性的，除了最初的假设，我们必须假设最初的假设是错误的。因此，停机问题是无法解决的。

我正在尝试创建一个函数来识别python文件中的代码是否会通过无限循环。这是我到目前为止所拥有的：

我要做的是执行文件，也许尝试计算执行了多少行并将其与前一个计数器中的任何数字进行比较。例如，如果计数器>lines_exected，则返回True，代码中存在无限循环。这行得通吗？还是我必须尝试其他方法？

我并不太深植于静态代码分析的非常正式的一面，因此这个问题。

几年前，我读到使用静态代码分析将代码与数据区分开来等同于停机问题。（需要引用，但我没有了。Stackoverflow 在此处或此处有线程。）至少对于基于Von Neumann 架构的常见计算机架构，其中代码和数据共享相同的内存，这似乎是有道理的。

现在看C/C++代码的静态分析和指针分析；程序不执行。不知何故，我有一种感觉，静态跟踪指针值的所有创建和使用类似于停止问题，因为我无法确定内存中的给定值是否是指针值，即我无法通过以下方式跟踪指针值的值流记忆。 别名分析可能会缩小问题的范围，但在面对多线程代码时它似乎变得不那么有用了。

（甚至可以考虑跟踪任意值，而不仅仅是指针：为任何给定的“有趣”值构造一个完整的值流似乎等同于停止问题。）

由于这只是一种预感，我的问题是：我可以参考更正式的发现吗？我弄错了吗？

图灵证明了停机问题在图灵机上是不可判定的。然而，真正的计算机实际上并不是图灵完备的：如果它们有无限量的内存，它们就会是图灵完备的。

考虑到计算机的内存量是有限的，因此不是完全转动的，停机问题是否可以判定？我的直觉告诉我，是的，但是解决这个受限停机问题的程序可能具有与目标计算机内存大小成指数关系的时间和空间复杂度。

我正在尝试在 Python（或伪代码）中为给定的函数列表 [f1,...,fn] 和给定的输入列表 [x1,...,xn] 仅打印一次 fi(xj)（表示所有函数和输入对）。

当然，实现这一点的天真的建议是：

但问题是某些函数可能会在某些输入上永远循环。

我被允许使用步进器（它有一个 step() 方法，每次调用该函数都会执行一个后续计算步骤）

我只需要一个关于如何做到这一点的想法或算法。

不可能解决停机问题的标准证明通常是这样的

这个证明要求您递归地调用停止函数，但是是否可以创建一个停止函数，只要它本身不被调用，它就总是计算正确的结果？

我本以为应该回答这样的问题，但似乎我在谷歌中找不到任何解决方案。

所以无论如何。谁能给我或链接我一个内置函数，它将检查该函数是否无限递归？

看起来像这样的功能将很棒

python中有类似的东西吗？

假设存在一个实现停止问题的 Haskel 函数：

如果定义了 x，则计算结果为 True，否则计算结果为 False。

假设我们在另一个函数中调用 Haskell 中的这个函数

我想知道在这种情况下会发生什么，如果 fHalt 是单调的。2个可能的答案出现在我身上：

1. Haskell 对预定义的操作符使用严格的求值 - 也就是 (+)。如果现在用 BOT 评估 fHalt，我的猜测是必须首先评估 BOT+1（导致 BOT），因此整体评估不会终止，也会导致 BOT。

2. 如果 Haskell 以某种方式确定内部 (x+1) 不会终止（由于停止问题，这是不可能的），结果将是 False 并且 fHalt 将违反单调性。

在这一点上，我很恼火，因为我的问题已经暗示了在 Haskell 中定义的不可实现的停止功能。虽然我认为答案 1. 是正确的。

我正在上理论 CS 课程，我们刚刚讨论了停机问题。在我的理解中，问题无法解决的原因是如果有一个程序 Halt 告诉我们一个不是程序是否停止，而你编写另一个程序证明这样

对我来说，问题的症结在于 if 条件是让程序无限循环，这就是 Halt 的失败条件。

这是我不确定的部分：

假设您有一个程序来检查另一个程序是否在某个输入上返回数字 4。我们称这个程序为 FourCheck。然后，我们可以编写另一个程序 ProofFour 使得

在这种情况下，我们可以调用 ProofFour(ProofFour,input)。如果 FourCheck() 返回 true，则 ProofFour 返回 5，使 FourCheck() 的输出不正确。如果 FourCheck 返回 false，则 ProofFour 返回 4，再次使 FourCheck() 的输出不正确。

因此，假设您基本上没有程序来检查其他程序是否正确，因为您总是可以构建一个类似于 Proof() 和 ProofFour() 的程序，它基本上反转了检查程序的输出。

我有问题。

我想使用用户输入的 IP 连接到游戏服务器。只要服务器是正确的或者服务器不存在，一切都很好，我有一个连接或一个异常。

问题是，如果我将 IP 放入不运行我的游戏的现有服务器。在这种情况下，程序停留在连接事件中并且不对任何事情做出反应。我考虑过设置一个计时器线程，尽管那没有用。该程序不对用户的任何输入做出反应，只允许您关闭它。

我将客户端实现为线程，将定时器实现为线程。如果超时，Timer-Thread 应该停止 Client-Thread。

我的计时器：

和我的客户：

如果这很重要，我正在将 JAVA 与 Jmonkey 一起使用。