停止使用非图灵完整的语言
图灵完整的语言无法解决停止问题，对于某些非TC语言(例如正则表达式)，它总是可以停止，因此可以轻松解决. 我想知道是否有任何语言既具有停止能力又不具有停止能力，但接受一种可以确定其是否停止的算法. 解决方案 是.这种重要的类之一是原始递归函数.此类包括您希望能够与数字进行的所有基本操作(加法，乘法等)，以及@adrian提到的一些复杂类(正则表达式/有限自动机，无上下文语法/下推式)
..
halting-problem相关内容
“在给定的二进制文件中查找所有代码等效于停止问题."真的吗?
只需阅读 事实证明，找到所有 给定二进制文件中的代码是等效的 停止问题. 真的对我伸出了双手. 那肯定不是真的吗?不仅仅是一个大的依赖图吗? 非常感谢您对此声明有进一步的了解. 解决方案 我相信这是“查找曾经执行过的所有代码"，即查找覆盖范围，可能与动态生成的代码结合使用.确实可以将其简化为停顿问题. 说您有一个完善的覆盖率工具，可以找到程序中可能执行的每段代码(
..
所有正则表达式都停止吗?
对于任何输入字符串，是否有任何正则表达式将永远搜索匹配项? 解决方案 对于有限输入，没有不会停止的正式正则表达式. 任何形式的正则表达式都可以转换为确定性有限自动机. DFA一次读取输入一个字符，在输入结束时，您处于接受状态或非接受状态.如果状态为接受，则输入匹配正则表达式.否则，不会. 现在，大多数“正则表达式"库支持的东西不是正则表达式，例如反向引用.只要您远离这些功能并输
..
证明暂停问题对NP不利吗?
在此问题的答案中NP，NP-hard和NP-complete的定义，Jason声称 停顿问题是经典的NP难题.这是给定程序P和输入I会停止的问题吗?这是一个决策问题，但不是NP问题.显然，任何NP完全问题都可以简化为这个问题. 虽然我同意暂停问题在直观上比NP中的任何问题都要“困难"得多，但老实说，我无法提出形式上的数学证据来证明暂停问题是NP难题.特别是，我似乎找不到从NP中每个问题
..
确定正则表达式是否是另一个的子集
我有大量的正则表达式集合，当匹配时调用特定的http处理程序.某些较旧的正则表达式无法访问(例如a.c* ⊃ abc*)，我希望对它们进行修剪. 是否有一个提供两个正则表达式的库会告诉我第二个是否是第一个的子集? 我一开始不确定这是可以决定的(它闻起来像是停顿问题，换了个名字).但是事实证明这是可以决定的. 解决方案 尝试发现这个问题的复杂性导致我进入本文. 问题的正式定
..
实用的非图灵完整语言?
几乎所有使用的编程语言都是 Turn Complete ，尽管这提供了代表任何语言的语言可计算算法，它还带有自己的 正则表达式用于匹配字符串和 编辑:我应该通过“通用"来阐明，我不一定希望能够用该语言编写所有停止算法(我认为这样的语言不会存在) )，但我怀疑暂停证明中存在一些通用线程，可以将其通用化，以产生一种可以保证所有算法都停止的语言. 还有另一种解决此问题的方法-消除对理论上无限内存的
..
在Brainfuck程序中检测无限循环
我已经用MATLAB脚本语言编写了一个简单的 brainfuck 解释器。它被馈送给随机的bf程序以执行（作为遗传算法项目的一部分）。我面临的问题是，程序在相当多的情况下都出现了无限循环，因此GA陷入了困境。 因此，我需要一种机制来检测无限循环并避免在bf中执行该代码。 一个明显的（琐碎的）情况是当我有 []时 我可以检测到并拒绝运行该程序。 对于简单的情况
..
如果您自己不调用它，是否可以使它停止?
解决暂停问题的不可能的标准证明通常是这样的 //does_halt() takes a function as input and returns true if it will ever finish computing function paradox() {if does_halt(paradox()) { while(true){}
..
您什么时候遇到现场停顿问题?
您何时亲自遇到 停止问题 在该领域?可能是因为同事/老板提出了一种解决方案，该解决方案违反了计算的基本限制，或者是您意识到自己要解决的问题实际上是无法解决的. 我最近想到的是在研究类型检查器时.我们的班级意识到，不可能编写出完美的类型检查器(该检查器将接受所有将运行且没有类型错误的程序，并拒绝所有将出现类型错误的程序)，因为这实际上可以解决暂停问题.另一个是当我们意识到在同一个类中，在类型检
..
Java中的无限循环
在Java中查看以下无限而循环。它会导致它下面的语句出现编译时错误。 while（true）{ System.out。 println（“inside while”）; } System.out.println（“终止时”）; //无法访问的语句 - 编译器错误。 以下相同的无限而循环，但工作正常，并没有发出任何错误，我只是用一个布尔变量替换条件。
..
不可否认的实例如何实际挂起编译器？
在我第一次阅读严肃的对 -XUndecidableInstances ，我已经完全习惯了，认为它只是解除了一个恼人的限制Haskell98让编译器更容易实现 class Group g其中 （％）:: g - > g - > g ... 实例数字g => Group g，其中 ... - 嗯，这显然是重叠的由Group 实例，所以不可判定性是我们最担心的：
..
agda程序是否必然终止？
已经说明了所有agda程序终止的几个地方。但是我可以构造一个这样的函数： stall：∀n→ℕ stall 0 = 0 摊位x =摊位x 语法荧光笔似乎不喜欢，但没有编译错误 计算正常形式的 stall 0 导致 0 。计算 stall 1 的结果会导致Emacs挂起，看起来很像非终止循环。 这是一个bug吗？还是Agda有时会永远运行？或者是更微
..
是否存在一种算法，可以解决Vim的高尔夫问题
是否有可能建立一个算法解决的Vim高尔夫球场的问题？对于那些不熟悉的是什么，您将得到两个不同的文本块，并且必须使用按键（在典型的例子使用Vim的最低数量改造的第一个块至第二或任何文本编辑程序，你选择使用）。我最初的怀疑是，答案是否定的;我们知道一个上限所需要的文本更改数 - 手动删除的差异，并输入正确的文字。然而越来越下降到的最低金额是更为复杂 - 文本编辑器可以编程强大的宏来执行任务，你可以有多
..