问题标签 [halting-problem]

停止问题指出，给定一个输入和一个程序，没有算法可以决定程序将停止的天气。这使得这个问题无法确定。我对停机问题的误解是，我们不能只创建另一个程序来检查程序是否有无限循环。我只是说可以检查循环不会停止的情况，并据此决定程序是否会停止。请你能告诉我我对这个问题的理解有什么问题吗？

鉴于：

• 仅包含从to字符的 char 字符串 S长度l'a''z'
• 一组ordered替换规则R（格式为X->Y），其中x,y是来自的单个字母'a' to 'z'（例如，'a' -> ' e'可能是有效规则，但'ce'->'abc'永远不会是有效规则）

当应用规则inr时，如果规则导致任何替换 in ，则所有与规则的字母相等的字母都将被替换为中的字母。RSSleft siderright siderrSrtriggered rule

流程图（算法）：
(1) 在 上交替应用all规则R（按照规则的顺序R）S。
(2) While (there exists any 'triggered rule' DURING (1) ): 重复 (1)
(3) 终止

问题是：有没有办法确定给定字符串 S 和集合 R，算法是否会终止（永远运行）

示例1：（手动执行）

S = 'abcdef' R = { 'a'->'b' , 'b' -> 'c' }
（顺序隐含每条规则从左到右出现的顺序）

在 S 和 R 上运行算法：
(1.1): 'abcdef' --> 'bbcdef' --> 'cccdef'
(2.1): 重复 (1) 因为在 (1.1) 期间有 2 个替换
(1.2): 'cccdef'
(2.2): 继续 (3) 因为在 (1.1) 期间没有替换(1.2)
(3) : 终止算法
=> 算法以给定的 S 和 R 终止示例 2
：

S = 'abcdef'R = { 'a'->'b' , 'b' -> 'a' }
（顺序隐含每条规则从左到右的出现顺序）

在 S 和 R 上运行算法：
(1.1): 'abcdef' --> 'bbcdef' --> 'abcdef'
(2.1): 重复 (1) 因为在 (1.1) 期间有 2 个替换
(1.2): 'abcdef--> 'bbcdef' --> 'abcdef'
(2.2): 重复 (1) 因为有在 (1.2) (1.3) 期间有 2 次替换
：......这将永远是 (1.1)....
步骤 (3) (terminate) 永远不会到达。
=> 算法不会以给定的 S 和 R 终止。

• 我对此进行了研究，发现“如果算法停止”这个问题没有有效的算法。

• 我想到的第一个想法是对 "find cycle"其中的字母，triggered rules但规则的数量可能太大，以至于这个想法不理想。

• 第二个是为"threshold"重复的时间提出一个，如果超过阈值，我们得出结论算法不会终止。

• 可以随机选择，"threshold"（只要它足够大） - 这种方法并不是很有吸引力。

• 我在想，如果有任何东西upper bound可以 "threshold" 确保我们总是得到正确的答案。我想出了 threshold = 2626 是从“a”到“z”的字母数——但我无法证明它是真的（或不是）。（我希望它会类似于 Bellman-Ford 算法，它以固定的步数确定负循环，..）

• 你呢？请帮我找到答案（这不是作业）

  谢谢你的阅读。

我正在寻找图灵机停止问题的简单解释。我知道 TM 的工作原理、它们如何枚举事物、机器配置等，但我无法很好地处理停机问题。

有人可以很好地解释这个话题吗？

我的理解是，对于一个足够简单的功能，让我们说

可以判断它是否会因任何可能的输入而停止。

很容易看出，上面的函数会因为 fhaltingFinder(haltingFinder)` 而终止而false不是终止，本质上是一个悖论。true. It's only impossible to solve the halting problem for an arbitrary function, as of course you can evaluate

我的理解正确吗？

我已经用自己的 BF 解释器在汇编中编写，现在我正在用 Java 编写一个 BF 编译器，它可以编译为汇编代码。

我想实现一个很好的功能，可以检测内存单元数组是否超出范围。数组的一个传统限制是让索引在 中[0, 30000)，否则[0, inf)也是常用的。另一种选择是内存是环绕的，所以在第一种情况下，这可能意味着访问索引 30000 意味着访问索引 0。

在我的编译器中，这种检测将在传统编译器的语义分析阶段完成，因此我们已经从语法分析阶段获得了我们的 AST（抽象语法树）。

在尝试为此提出一个结构一段时间后，我发现在 Brainfuck 程序中检测无限循环，连同 BF 的 Wikipedia 页面，我发现带有内存数组的 BF 程序[0, inf)类似于图灵机。

所以我的问题是，对于这两种情况[0, max)，[0, inf)是否可以检测内存指针是否低于零，而在前一种情况下是否低于最大值？显然，在检查它时不会陷入无限循环，我也宁愿避免设置最大执行时间。

额外问题：是否可以检测循环构造[...]循环的次数？

我最近遇到了停止问题矛盾证明。在证明中，我们必须向图灵机提供程序的副本和输入的副本，以决定该程序是否在输入时停止。在矛盾中，为什么一定要程序作为程序和输入？对不起，如果这听起来令人困惑。我可以简单地给机器输入一个程序和一个随机输入并得出相同的结论。

谁能告诉我为什么？有没有我没有想到的具体原因？

当我第一次阅读有关-XUndecidableInstances.

事实上，我遇到过很多需要不可判定实例的应用程序，但没有一个应用程序实际上会导致与不可判定性相关的任何问题。卢克的例子是有问题的，原因完全不同

– 好吧，这显然会与任何适当的实例重叠，所以不确定性Group是我们最不担心的：这实际上是不确定的！

但很公平，因为我一直在脑海中保留“不可判定的实例可能会使编译器挂起”。

当我在 CodeGolf.SE 上阅读这个挑战时，它是从哪里获得的，要求提供可以无限挂起编译器的代码。好吧，这听起来像是在不确定的情况下工作，对吧？

事实证明我无法让他们这样做。以下内容立即编译，至少从 GHC-7.10 开始：

我什至可以使用类方法，它们只会在运行时导致循环：

但是运行时循环并不罕见，您可以在 Haskell98 中轻松编写这些代码。

我还尝试了不同的、不那么直接的循环，例如

同样，在编译时没有问题。

那么，在解析不可判定的类型类实例时，实际上需要什么来挂起编译器呢？

这是用于计数事物的 Meteor 应用程序的一些代码（带有相关数据）的本质。计数可以链接在一起，以便一个可以增加另一个：

因此，如果Meteor.call('projects.increment',1)调用此代码，则会因为每个计数都链接到另一个计数而崩溃。检测这样的设置可能相当困难，因为可能存在非常复杂的计数安排，并且链接也可能减少，设置为零，每 N 个计数操作一次等等。＆C。不过，出于提出这个问题的目的，这并不重要。

我想到的一种可能性是添加一个计数器counts.check-links，在任意循环次数（例如 5 次）后将在该计数器内停止执行。据推测，为了防止篡改该计数器的值，必须将其存储在数据库中并通过流星法。它需要在任何check-links调用序列结束时重置。

我不确定这是否是最好的主意，或者如果是这样，如何实现它的好方法，所以我很想知道是否有人有任何建议。

我试图证明 TM = DFA 使用停止问题的减少是不可判定的 理论上我知道图灵机捕获所有可计算的函数，而 DFA 只捕获可以在恒定空间中计算的函数，因此 TM = DFA 是不可判定的。

这是我的步骤：假设决定 L(M)=L(D) 的 R

EQ_DM = { [D,M] | L(M) = L(D) }

我们创建了一个图灵机

HALT_TM = { [M,w] | （M 在输入 w 时停止→接受
M 在输入 w 时没有停止→拒绝）}

我如何构造一个 D & M 以便 R[D,M] 告诉 M 是否在 w 上停止？

我对算法有非常基本的了解。我是数学专业的毕业生。我正在阅读 Susanna Epp 的应用程序离散数学一书中的停止问题。它有以下定理：

定理：没有计算机算法会接受任何算法 X 和数据集 D 作为输入，然后将输出“halts”或“loops forever”来指示当 X 运行数据时 X 是否以有限步数终止设置 D。

证明：假设有一个算法，称为 CheckHalt，如果输入了算法 X 和数据集 D，则 CheckHalt 打印“halts”，如果 X 在使用数据集 D 或“永远循环”，如果 X 在使用数据集 D 运行时没有在有限的步数内终止。

现在下一行是我在这个证明中不理解的那些

观察构成算法 X 的字符序列可以看作是一个数据集本身。因此，可以考虑使用输入 (X,X) 运行 CheckHalt。

所以我理解 CheckHalt 本质上是作为算法 X 和数据集 D 获取输入的。它告诉我们是否使用该数据集 D 作为（X 的）输入运行算法 X，然后 X 将永远停止或循环。因此 CheckHalt(X,D) 看起来不错。

我的问题是算法 X 本身如何具有输入 X，即我们如何将算法称为数据集？

句子“组成算法X的字符序列”是什么意思？

我能理解 CheckHalt(X,D)。但是 CheckHalt(X,X) 是什么？

谢谢。