halting-problem

0热度

1回答

我陷入了一个问题，并希望对解决方案有一点指导。我需要证明的是，接下来的问题是不可判定：输入 - 一种程序问题 - 是否为其程序暂停可能输入的数量比那些该节目赢得了”大停止？我试图建立一个减少（如果输入是偶数）每个偶数停止，对每个奇数进行无限循环，并用输入运行程序。或者，如果输入是奇数，则相反 - 但它只在我能够证明实际奇数的数量等于实数偶数时才有效。

0热度

1回答

流星 - 检测无限循环

下面是一些代码（具有相关联的数据），用于计数东西流星应用的本质。计数可以连接在一起，这样一是可以增加另： // The counting and linking code. Meteor.methods({ 'counts.increment'(countId) { const count = Counts.findOne(countId); Counts.up

1热度

1回答

基于启发式的病毒检测如何实现？

停机问题指出，这是不可能的一个程序来预测的另一个输出，或是否将被终止。这让我想......怎么办启发式为主的扫描仪决定一个给定的可执行程序的指令是否是“病毒式”，看到这将完全涉及预测哪些程序该怎么办？

1热度

1回答

“haltingproblem”矛盾证明

我最近碰到了停止问题的矛盾证明。在证明中，我们必须为图灵机提供一份程序副本和一份输入副本，以决定程序是否停止输入。在矛盾中，为什么它必须作为程序和输入的程序？对不起，如果听起来很混乱。我可以简单地给机器提供程序和随机输入，并得出相同的结论。有谁能告诉我为什么？有没有我没有想到的具体原因？

0热度

2回答

非确定性运行时间真的很糟糕吗？

当我在这里谈论暂停问题时，听起来好像不可终止是需要避免的，暂停问题使得不可能知道程序/算法是否好。但是，当我仔细想想，不终止程序的异常，没有规则？我可以想到一类应用程序在预计在有限的时间内终止：编译器。从我正在使用的Web浏览器到桌面环境，文本编辑器，shell，服务器托管SO，到操作系统本身，其他一切都不应该自行终止。哎呀，即使是包管理者也应该要求用户确认。除非用户或系统管理员另有说明，否则它

2热度

1回答

'试' 可以决定当一个程序暂停

我有这样的功能： isUndefined ::() -> Bool isUndefined x = case unsafePerformIO $ (try (return $! x) :: IO (Either SomeException())) of Left _ -> True Right _ -> False 则： isUndefined() =

3热度

2回答

图灵机停机问题

我正在寻找图灵机停机问题的简单解释。我对这个话题很陌生，但我知道TMs是如何工作的基础，他们是如何枚举事物，机器配置等的，但我没有很好地处理暂停问题。有人可以提供一个很好的解释这个话题吗？

0热度

1回答

对于某些有限功能，可以停止使用吗？

这是我的理解是十分简单的功能，让我们说 function(boolean input){ while(input){ } } 就可以判断它会阻止任何可能的输入。很容易看出上述函数将终止为false，而不是终止于haltingFinder（haltingFinder），并且本质上会产生一个悖论。我的理解是否正确？

0热度

1回答

证明TM和DFA的等价性

我试图用停止问题的减少来证明TM = DFA是不可判定的理论上我明白图灵机捕获所有可计算函数，而DFA只捕获可以常量计算的函数因此TM = DFA是不可判定的。这里是我的步骤：假设是R那个决定L（M）= L（d） EQ_DM = {[d，M] | L（M）= L（d）} 和我们创建一个图灵机 HALT_TM = {[M，W] | （在输入砂→M停止接受中号没有输入停止波→拒绝）} 如何构建一

3热度

1回答

停止问题是否意味着程序无法检查其他程序？

我正在参加理论课，我们刚刚讨论了暂停问题。在我的理解，这个问题不能得到解决的原因是，如果有一个程序暂停，告诉我们没有一个程序是否会停机，而你写另一个程序证明这样 function Proof (program, input) if (Halt(program, input)) loop infinitely; else return 1 对我来说，症结问题在于if条件是程序无限循环，这是