问题标签 [halting-problem]

例如，假设我有一台图灵机 H，它告诉我们程序和输入是否会停止。假设我们自己调用 H。它必须给出答案，所以如果它打印出“不停止”，那么它在技术上不是停止打印该语句吗？还是理论上总是会打印出“停止”？我很难将我的头脑完全围绕在自己身上调用 H ，没有否定，以及它会做什么。我明白为什么否定会导致矛盾，但我只是想知道以下情况是否也会导致矛盾。

谢谢！

在运行时我可以：

但不能为编译时做类似的事情：

似乎是无限循环/递归保护，但据我了解停止问题- 没有通用方法来检测图灵完备语言的无限递归（因为检测器本身可能不会停止），因此额外的编译器检查通常不会在这里工作.

那么有没有办法在scalac上获得无限递归？而且，还有其他（除了防止这种递归）理由illegal cyclic reference吗？

这些规则涵盖了“as-if”规则：

对一致性实现的最低要求是：

• 对 volatile 对象的访问严格按照抽象机的规则进行评估。

• 在程序终止时，写入文件的所有数据应与根据抽象语义执行程序可能产生的结果之一相同。

• 交互式设备的输入和输出动态应该以这样一种方式发生，即在程序等待输入之前实际交付提示输出。构成交互式设备的内容是实现定义的。

这些统称为程序的可观察行为。

...访问由 volatile glvalue (3.10) 指定的对象、修改对象、调用库 I/O 函数或调用执行任何这些操作的函数都是副作用，它们是状态的变化执行环境。...

但让我们采用如下程序：

事实是没有对象或对函数的调用，因此没有副作用，因此没有“执行环境状态的变化”。是什么阻止编译器将此代码编译为

这一切都是不确定的吗？无限循环本质上是“这是一个标签，一遍又一遍地跳到它”，并将一直持续到计算机关闭。代码没有做任何有趣的事情，没有计算，没有 I/O 输出等。

在内核代码中，无限循环变得有趣。但在用户空间代码中，无限循环通常是程序编写不佳的标志。那么我的逻辑有什么缺陷呢？

我试图理解为什么不可能编写一个程序 H 来检查特定输入上的另一个程序 P 是否会停止（停止问题），但我无法清楚地了解它。

尽管直觉告诉我们，如果这个程序 H 试图运行一个不会停止的程序 P，那么 H 本身就会进入一个循环。但我不认为这是证明背后的想法。

任何人都可以用简单的外行术语解释证明吗？

问题是：如果求解器没有被组装/模拟/生成/重新创建/将您的选择放在这里/在分析函数中以任何形式使用，是否可以解决停止问题？

有一个非常相似的问题： 如果你不自己调用它，是否可以创建一个停止函数？ 但是答案通常是“我们不调用函数而是传递函数”，但是，如果我们也排除这种情况，它会变得可以解决吗？

假设我想找到一个 n+n=3 的自然数 n 为了计算地解决这个问题，我将运行一个算法：

当然我们知道这个循环是一个无限循环。但是有没有一种算法可以预测这个循环是无限的还是有限的？（与停止机器相似但不同，因为我想要的算法只检查这个循环，而停止机器可以检查所有循环）如果有，算法是什么？

I have this function:

then:

Solving the halting problem. Of course, this can be extended to other types too.

My question: how is this possible? Is Control.Exception.try really breaking things here?

是否有可能创建一种算法来解决 Vim-golf 问题？对于那些不熟悉那是什么的人，您会得到两个不同的文本块，并且必须使用尽可能少的击键次数将第一个块转换为第二个块（在规范示例中使用 Vim，或者您选择的任何文本编辑程序）利用）。我最初的怀疑是答案是否定的。我们知道所需文本更改数量的上限 - 手动删除差异并输入正确的文本。然而，降到最低数量更复杂 - 文本编辑器可以编写强大的宏来执行任务，并且您可以组合多个宏 - 我猜可能有一些方法可以显示与停止问题的对应关系，但我我不太确定细节。

是否有一个程序 (may-halt?p) 可以判断是否存在输入以使 (p input) 停止？

我尝试了简单的对角化，但它只告诉我 (may-halt?di​​ag-may-halt) 必须为真。它无助于证明程序是否存在。

有这样的程序吗？