看下面这个Java中的无限while循环。它会导致紧接着它下面的语句在编译时出现错误。while(true) { System.out.println("inside while"); } System.out.println("while terminated"); //Unrea...

在工作中你曾经遇到过停机问题吗？这可能是当你的同事/老板提出了一种违反计算基本限制的解决方案，或者当你自己意识到你试图解决的问题实际上是无法解决的时候。 我最近遇到的一个例子是在学习类型检查器时。我们班意识到，要编写一个完美的类型检查器（接受所有不会发生类型错误的程序，并拒绝所有会发生类型错...

每当人们谈到与编程有关的停机问题时，人们会回答说：“如果你只添加一个循环，你就得到了停机程序，因此你无法自动化任务。” 这是有道理的。如果你的程序有一个无限循环，那么当你的程序运行时，你无法知道程序是仍在处理输入，还是只是无限循环。 但有些东西似乎是违反直觉的。如果我正在编写一个停机问题求...

几乎所有使用的编程语言都是图灵完备的，尽管这使得该语言能够表示任何可计算算法，但它也带来了自己的一套问题。考虑到我编写的所有算法都旨在停止，我希望能够用一种保证它们会停止的语言来表示它们。 在词法分析时，用于匹配字符串的正则表达式和有限状态机被使用，但我想知道是否有更通用、广泛的语言，而不是...

我有一大批常规表达式，当匹配成功时会调用特定的HTTP处理程序。其中一些旧的表达式已经无法到达（例如a.c* ⊃ abc*），我想对它们进行修剪。 是否有一个库可以给出两个正则表达式，告诉我第二个是不是第一个的子集？ 一开始我不确定这是否可判定（它听起来像是另一种形式的停机问题）。但事实证...

在关于NP、NP-hard和NP-complete定义的一个问题的这个回答中，Jason声称：停机问题是经典的NP-hard问题。这个问题给定一个程序P和输入I，它是否会停止？这是一个判定问题，但它不属于NP。很明显，任何NP-complete问题都可以归约到这个问题。 尽管我认为停机问题在...

在课堂上，我们学习了停机问题、图灵机、约化等概念。很多同学说这些都是抽象无用的概念，知道它们没有实际意义（即，课程结束后可以忘记它们而不会失去任何东西）。 理论为什么有用？你是否在日常编码中使用它？

我用MATLAB脚本语言写了一个简单的Brainfuck解释器，它可以执行随机bf程序（作为基因算法项目的一部分）。 我面临的问题是，在相当多的情况下，程序会出现无限循环，因此GA在那一点上被卡住了。 因此，我需要一种机制来检测无限循环并避免执行bf中的代码。 一个显而易见（琐碎）的情况是当我...

我正在审查Sipser的《计算理论导论》中停机问题的证明，我主要关注以下证明：如果TM M不知道它何时循环（它不能接受或拒绝任何字符串，这就是为什么TM对于所有字符串都是图灵可识别的），那么决策器H如何确定M是否可能进入循环？当TM D进行处理时，同样的问题也会出现。

图灵完备语言的停机问题无法解决，但对于某些非图灵完备语言（例如正则表达式），其总是停机的停机问题可以轻松解决。我想知道是否有一些语言既有停机又没有停机的能力，但却能够采用算法来确定它是否会停机。