I literally got assigned the halting problem, as in "write a monitor plugin to determine whether a host is permanently down". Seriously? OK, so I'll just give it a threshold. "No, because it might come back up afterward."
Years ago, I remember reading a review (in Byte magazine, I believe) of a product called Basic Infinite Loop Finder or BILF. BILF was supposed to scan your Microsoft Basic source code and find any loops which didn't terminate. It claimed to be able any find any infinite loops in the code.
The reviewer was savvy enough to point out that for that program to work in all cases, it would have to solve the halting problem and went so far as to provide a mathematical proof of why it couldn't work in all cases.
In the next issue, they published a letter from a company representative explaining that the problem would be fixed in the next release.
Update: I ran across an image of the article on imgur. I remembered the wrong magazine. It was Creative Computing, not Byte. Otherwise, it's pretty much as I remembered it.
The project I'm working on right now has undecidable problems all over it. It's a unit test generator, so in general what it tries to accomplish is to answer the question "what this program does". Which is an instance of a halting problem. Another problem that came up during development is "are given two (testing) functions the same"? Or even "does the order of those two calls (assertions) matter"?
What's interesting about this project is that, even though you can't answer those questions in all situations, you can find smart solutions that solve the problem 90% of the time, which for this domain is actually very good.
Other tools that try to reason about other code, like optimizing compilers/interpreters, static code analysis tools, even refactoring tools, are likely to hit (thus be forced to find workarounds to) the halting problem.
When I was learning to program I played with making a tool to print out pretty reports from data. Obviously I wanted it to be really flexible and powerful so it would be the report generator to end all report generators.
The report definition ended up being so flexible that it was Turing complete. It could look at variables, choose between alternatives, use loops to repeat things.
I defined a built-in variable N, the number of pages in the report instance, so you could put a string that said "page n of N" on each page. I did two passes, the first one to count the pages (during which N was set to zero), and the second to actually generate them, using the N obtained from the first pass.
Sometimes the first pass would compute N, and then the second pass would generate a different number of pages (because now the non-zero N would change what the report did). I tried doing passes iteratively until the N settled down. Then I realised this was hopeless because what if it didn't settle down?
This then leads to the question, "Can I at least detect and warn the user if the iteration is never going to settle on a stable value for the number of pages their report produces?" Fortunately by this time I had become interested in reading about Turing, Godel, computability etc. and made the connection.
Years later I noticed that MS Access sometimes prints "Page 6 of 5", which is a truly marvelous thing.
Example 2: C++ compilers
The compilation process involves expanding templates. Template definitions can be selected from multiple specialisations (good enough to serve as a "cond") and they can also be recursive. So it's a Turing complete (pure functional) meta-system, in which the template definitions are the language, the types are the values, and the compiler is really an interpreter. This was an accident.
Consequently it is not possible to examine any given C++ program and say whether the compiler could in principle terminate with a successful compilation of the program.
Compiler vendors get around this by limiting the stack depth of template recursive. You can adjust the depth in g++.
Many many moons ago I was assisting a consultant for our company who was implementing a very complex rail system to move baskets of metal parts in and out of a 1500-degree blast furnace. The track itself was a fairly complex 'mini-railyard' on the shop floor that intersected itself in a couple of places. Several motorized pallets would shuttle baskets of parts around according to a schedule. It was very important that the furnace doors were open for as short a time as possible.
Since the plant was in full production, the consultant was unable to run his software in 'real time' to test his scheduling algorithms. Instead, he wrote a pretty, graphic-y simulator. As we watched virtual pallets move around on his on-screen track layout, I asked "how will you know if you have any scheduling conflicts?"
His quick answer, "Easy - the simulation will never stop."
Sophisticated static code analysis can run into the halting problem.
For example, if a Java virtual machine can prove that a piece of code will never access an array index out-of-bounds, it can omit that check and run faster. For some code this is possible; as it gets more complex it becomes the halting problem.
应用程序没有 API 来控制驱动程序的行为方式或设置超时等，并且驱动程序当然无法判断着色器是否将完成。
我不知道这种情况最近有没有改善，但我很想知道。
This is still a problem for shaders in GPU applications. If a shader has an infinite loop (or a very long calculation), should the driver (after some time limit) stop it, kill the fragment, or just let it run? For games and other commercial stuff, the former is probably what you want, but for scientific/GPU computing, the latter is what you want. Worse, some versions of windows assume that since the graphics driver has been unresponsive for some time, it kills it, which artificially limits the computing power when doing computation on the GPU.
There's no API for a application to control how the driver should behave or set the timeout or something, and there's certainly no way for the driver to tell if your shader is going to finish or not.
I don't know if this situation has improved recently, but I'd like to know.
假设您有两个锁，A 和 B，以及两个线程，X 和 Y。如果线程 X 拥有锁 A，并且也想要锁 B，并且线程 Y 拥有锁 B 并且也想要 A ，那么你就陷入了僵局。
如果 X 和 Y 都可以访问 A 和 B，那么确保永远不会进入不良状态的唯一方法是确定每个线程在代码中可以采用的所有可能路径以及它们的顺序在所有这些情况下都可以获取和持有锁。 然后，您确定两个线程是否可以以不同的顺序获取多个锁。
但是，确定每个线程可以通过代码采取的所有可能路径（在一般情况下）相当于暂停问题。
Another common version of this is "we need to eliminate any deadlocks in our multi-threaded code". A perfectly-reasonable request, from the management perspective, but in order to prevent deadlocks in the general case, you have to analyse every possible locking state that the software can get into, which is, no surprise, equivalent to the halting problem.
There are ways to partially "solve" deadlocks in a complex system by imposing another layer on top of the locking (like a defined order of acquisition), but these methods are not always applicable.
Why this is equivalent to the halting problem:
Imagine you have two locks, A and B, and two threads, X and Y. If thread X has lock A, and wants lock B also, and thread Y has lock B and wants A too, then you have a deadlock.
If both X and Y have access to both A and B, then the only way to ensure that you never get into the bad state is to determine all of the possible paths that each thread can take through the code, and the order in which they can acquire and hold locks in all those cases. Then you determine whether the two threads can ever acquire more than one lock in a different order.
But, determining all of the possible paths that each thread can take through the code is (in the general case) equivalent to the halting problem.
Perl's testing system maintains a test counter. You either put the number of tests you're going to run at the top of the program, or you declare that you're not going to track it. This guard against your test exiting prematurely, but there are other guards so it's not all that important.
Every once in a while somebody tries to write a program to count the number of tests for you. This is, of course, defeated by a simple loop. They plow ahead anyway, doing more and more elaborate tricks to try and detect loops and guess how many iterations there will be and solve the halting problem. Usually they declare that it just has to be "good enough".
LOOPER may be useful since most infinite loops are trivial errors. However, this paper doesn't even mention the halting problem!
What do they say about their limitations?
[LOOPER] typically cannot reason about loops where non-termination depends on the particulars of heap mutation in every loop iteration. This is because our symbolic execution is conservative in concretizing pointers, and our symbolic reasoning insufficiently powerful. We believe combining our techniques with shape analysis and more powerful invariant generation and proving would be valuable future work.
In other words, "the problem will be fixed in the next release".
I was once working on an integration project in the ATM (Automated Teller Machines) domain. The client requested me to generate a report from my system for transactions sent by the country switch which were not received by my system!!
The Eclipse Visual Editor (VE) can be used to open any .java file. It then parses the Java source code looking for visual beans. ...
Some visual editing tools will only provide a visual model of code that that particular visual tool itself has generated. Subsequent direct editing of the source code can prevent the visual tool from parsing the code and building a model.
Eclipse VE, however, ... can either be used to edit GUIs from scratch, or from Java files that have been 'hardcoded' or built in a different visual tool. The source file can either be updated using the Graphical Viewer, JavaBeans Tree or Properties view or it can be edited directly by the Source Editor.
Maybe I should stick with Matisse for now.
Unrelated, here's someone asking for the halting problem within Eclipse.
To be fair, VE's domain is quite limited, and it probably won't go crazy over tricky things like reflection. Still, the claim to build GUI out of any java file seems halt-ish.
发布评论
评论（13）
我实际上被分配了停止问题，如“编写一个监视器插件来确定主机是否永久关闭”。 严重地？ 好的，所以我就给它一个阈值。 “不，因为之后它可能会回来。”
随后进行了大量的理论阐述。
I literally got assigned the halting problem, as in "write a monitor plugin to determine whether a host is permanently down". Seriously? OK, so I'll just give it a threshold. "No, because it might come back up afterward."
Much theoretical exposition ensued.
几年前，我记得读过一篇关于一款名为 Basic Infinite Loop Finder 或 BILF 的产品的评论（我相信是在 Byte 杂志上）。 BILF 应该扫描您的 Microsoft Basic 源代码并查找任何未终止的循环。 它声称能够找到代码中的任何无限循环。
审阅者很精明地指出，要使该程序在所有情况下都能工作，它必须解决停止问题，并甚至提供了数学证明，证明为什么它不能在所有情况下都工作。
在下一期中，他们发表了一封来自公司代表的信，解释说该问题将在下一版本中得到解决。
更新：我在 imgur 上看到了这篇文章的图片。 我记错杂志了。 这是创意计算，而不是字节。 除此之外，它和我记忆中的差不多。
您可以在 imgur 上查看其高分辨率版本。
Years ago, I remember reading a review (in Byte magazine, I believe) of a product called Basic Infinite Loop Finder or BILF. BILF was supposed to scan your Microsoft Basic source code and find any loops which didn't terminate. It claimed to be able any find any infinite loops in the code.
The reviewer was savvy enough to point out that for that program to work in all cases, it would have to solve the halting problem and went so far as to provide a mathematical proof of why it couldn't work in all cases.
In the next issue, they published a letter from a company representative explaining that the problem would be fixed in the next release.
Update: I ran across an image of the article on imgur. I remembered the wrong magazine. It was Creative Computing, not Byte. Otherwise, it's pretty much as I remembered it.
You can see a hi-res version of it on imgur.
我现在正在从事的项目 到处都有无法判定的问题。 它是一个单元测试生成器，所以一般来说它试图完成的是回答“这个程序做什么”的问题。 这是停机问题的一个例子。 开发过程中出现的另一个问题是“给定两个相同的（测试）函数”？ 或者甚至“这两个调用（断言）的顺序重要吗”？
这个项目的有趣之处在于，即使您无法在所有情况下回答这些问题，但您可以找到能够在 90% 的情况下解决问题的智能解决方案，这对于这个领域来说实际上非常好。
其他尝试推理其他代码的工具，例如优化编译器/解释器、静态代码分析工具，甚至重构工具，都可能会遇到（从而被迫找到解决方法）停止问题。
The project I'm working on right now has undecidable problems all over it. It's a unit test generator, so in general what it tries to accomplish is to answer the question "what this program does". Which is an instance of a halting problem. Another problem that came up during development is "are given two (testing) functions the same"? Or even "does the order of those two calls (assertions) matter"?
What's interesting about this project is that, even though you can't answer those questions in all situations, you can find smart solutions that solve the problem 90% of the time, which for this domain is actually very good.
Other tools that try to reason about other code, like optimizing compilers/interpreters, static code analysis tools, even refactoring tools, are likely to hit (thus be forced to find workarounds to) the halting problem.
示例 1. 我的报告有多少页？
当我学习编程时，我尝试制作一个工具来根据数据打印出漂亮的报告。 显然，我希望它非常灵活和强大，因此它将成为结束所有报告生成器的报告生成器。
报告定义最终变得如此灵活，以至于它是图灵完备的。 它可以查看变量，在替代方案之间进行选择，使用循环来重复操作。
我定义了一个内置变量 N，即报表实例中的页数，因此您可以在每页上放置一个表示“第 n 页，共 N 页”的字符串。 我做了两遍，第一遍是对页面进行计数（在此期间 N 设置为零），第二遍是使用从第一遍获得的 N 来实际生成它们。
有时，第一遍将计算 N，然后第二遍将生成不同数量的页面（因为现在非零 N 会改变报告的内容）。 我尝试迭代地进行传递，直到 N 稳定下来。 然后我意识到这是没有希望的，因为如果它没有安定下来怎么办？
这就引出了一个问题：“如果迭代永远无法确定报告生成的页数的稳定值，我至少可以检测并警告用户吗？” 幸运的是，此时我开始对阅读图灵、哥德尔、可计算性等感兴趣，并建立了联系。
多年后，我注意到 MS Access 有时会打印“第 6 页，共 5 页”，这确实是一件了不起的事情。
示例2：C++编译器
编译过程涉及扩展模板。 模板定义可以从多个专业化中选择（足以充当“条件”），并且它们也可以是递归的。 所以它是一个图灵完备（纯函数）元系统，其中模板定义是语言，类型是值，而编译器实际上是一个解释器。 这是一次意外。
因此，不可能检查任何给定的 C++ 程序并判断编译器原则上是否可以成功编译该程序而终止。
编译器供应商通过限制模板递归的堆栈深度来解决这个问题。 您可以在 g++ 中调整深度。
Example 1. How many pages in my report?
When I was learning to program I played with making a tool to print out pretty reports from data. Obviously I wanted it to be really flexible and powerful so it would be the report generator to end all report generators.
The report definition ended up being so flexible that it was Turing complete. It could look at variables, choose between alternatives, use loops to repeat things.
I defined a built-in variable N, the number of pages in the report instance, so you could put a string that said "page n of N" on each page. I did two passes, the first one to count the pages (during which N was set to zero), and the second to actually generate them, using the N obtained from the first pass.
Sometimes the first pass would compute N, and then the second pass would generate a different number of pages (because now the non-zero N would change what the report did). I tried doing passes iteratively until the N settled down. Then I realised this was hopeless because what if it didn't settle down?
This then leads to the question, "Can I at least detect and warn the user if the iteration is never going to settle on a stable value for the number of pages their report produces?" Fortunately by this time I had become interested in reading about Turing, Godel, computability etc. and made the connection.
Years later I noticed that MS Access sometimes prints "Page 6 of 5", which is a truly marvelous thing.
Example 2: C++ compilers
The compilation process involves expanding templates. Template definitions can be selected from multiple specialisations (good enough to serve as a "cond") and they can also be recursive. So it's a Turing complete (pure functional) meta-system, in which the template definitions are the language, the types are the values, and the compiler is really an interpreter. This was an accident.
Consequently it is not possible to examine any given C++ program and say whether the compiler could in principle terminate with a successful compilation of the program.
Compiler vendors get around this by limiting the stack depth of template recursive. You can adjust the depth in g++.
很多个月前，我正在协助我们公司的一位顾问，他正在实施一个非常复杂的铁路系统，用于将金属零件篮移入和移出 1500 度的高炉。 轨道本身是车间里一个相当复杂的“迷你铁路站”，在几个地方相交。 几个机动托盘将按照时间表运送一篮子零件。 炉门打开时间尽可能短非常重要。
由于工厂已全面投入生产，顾问无法“实时”运行他的软件来测试他的调度算法。 相反，他编写了一个漂亮的图形模拟器。 当我们看到虚拟托盘在他屏幕上的轨道布局上移动时，我问“你如何知道是否有任何调度冲突？”
他很快回答道：“很简单——模拟永远不会停止。”
Many many moons ago I was assisting a consultant for our company who was implementing a very complex rail system to move baskets of metal parts in and out of a 1500-degree blast furnace. The track itself was a fairly complex 'mini-railyard' on the shop floor that intersected itself in a couple of places. Several motorized pallets would shuttle baskets of parts around according to a schedule. It was very important that the furnace doors were open for as short a time as possible.
Since the plant was in full production, the consultant was unable to run his software in 'real time' to test his scheduling algorithms. Instead, he wrote a pretty, graphic-y simulator. As we watched virtual pallets move around on his on-screen track layout, I asked "how will you know if you have any scheduling conflicts?"
His quick answer, "Easy - the simulation will never stop."
复杂的静态代码分析可能会遇到停机问题。
例如，如果 Java 虚拟机可以证明一段代码永远不会越界访问数组索引，它就可以省略该检查并运行得更快。 对于某些代码来说这是可能的； 当它变得更加复杂时，它就会成为停止问题。
Sophisticated static code analysis can run into the halting problem.
For example, if a Java virtual machine can prove that a piece of code will never access an array index out-of-bounds, it can omit that check and run faster. For some code this is possible; as it gets more complex it becomes the halting problem.
对于 GPU 应用程序中的着色器来说，这仍然是一个问题。 如果着色器有无限循环（或非常长的计算），驱动程序（在一定时间限制后）是否应该停止它，杀死片段，或者只是让它运行？ 对于游戏和其他商业内容，前者可能是您想要的，但对于科学/GPU 计算，后者才是您想要的。 更糟糕的是，某些版本的 Windows 认为由于图形驱动程序在一段时间内没有响应，因此将其杀死，这人为地限制了在 GPU 上进行计算时的计算能力。
应用程序没有 API 来控制驱动程序的行为方式或设置超时等，并且驱动程序当然无法判断着色器是否将完成。
我不知道这种情况最近有没有改善，但我很想知道。
This is still a problem for shaders in GPU applications. If a shader has an infinite loop (or a very long calculation), should the driver (after some time limit) stop it, kill the fragment, or just let it run? For games and other commercial stuff, the former is probably what you want, but for scientific/GPU computing, the latter is what you want. Worse, some versions of windows assume that since the graphics driver has been unresponsive for some time, it kills it, which artificially limits the computing power when doing computation on the GPU.
There's no API for a application to control how the driver should behave or set the timeout or something, and there's certainly no way for the driver to tell if your shader is going to finish or not.
I don't know if this situation has improved recently, but I'd like to know.
另一个常见的版本是“我们需要消除多线程代码中的任何死锁”。 从管理角度来看，这是一个完全合理的请求，但为了防止一般情况下的死锁，您必须分析软件可能进入的每种可能的锁定状态，这相当于停机问题。
有一些方法可以通过在锁定之上施加另一层（例如定义的获取顺序）来部分“解决”复杂系统中的死锁，但这些方法并不总是适用。
为什么这相当于暂停问题：
假设您有两个锁，A 和 B，以及两个线程，X 和 Y。如果线程 X 拥有锁 A，并且也想要锁 B，并且线程 Y 拥有锁 B 并且也想要 A ，那么你就陷入了僵局。
如果 X 和 Y 都可以访问 A 和 B，那么确保永远不会进入不良状态的唯一方法是确定每个线程在代码中可以采用的所有可能路径以及它们的顺序在所有这些情况下都可以获取和持有锁。 然后，您确定两个线程是否可以以不同的顺序获取多个锁。
但是，确定每个线程可以通过代码采取的所有可能路径（在一般情况下）相当于暂停问题。
Another common version of this is "we need to eliminate any deadlocks in our multi-threaded code". A perfectly-reasonable request, from the management perspective, but in order to prevent deadlocks in the general case, you have to analyse every possible locking state that the software can get into, which is, no surprise, equivalent to the halting problem.
There are ways to partially "solve" deadlocks in a complex system by imposing another layer on top of the locking (like a defined order of acquisition), but these methods are not always applicable.
Why this is equivalent to the halting problem:
Imagine you have two locks, A and B, and two threads, X and Y. If thread X has lock A, and wants lock B also, and thread Y has lock B and wants A too, then you have a deadlock.
If both X and Y have access to both A and B, then the only way to ensure that you never get into the bad state is to determine all of the possible paths that each thread can take through the code, and the order in which they can acquire and hold locks in all those cases. Then you determine whether the two threads can ever acquire more than one lock in a different order.
But, determining all of the possible paths that each thread can take through the code is (in the general case) equivalent to the halting problem.
Perl 的测试系统维护一个测试计数器。 您要么将要运行的测试数量放在程序的顶部，要么声明您不会跟踪它。 这可以防止您的测试过早退出，但还有其他保护措施，因此这并不是那么重要。
每隔一段时间，就会有人尝试编写一个程序来为您计算测试的数量。 当然，这可以通过简单的循环来解决。 不管怎样，他们会继续努力，做越来越复杂的技巧来尝试检测循环并猜测将会有多少次迭代并解决停止问题。 通常他们宣称它只需“足够好”即可。
这是一个特别详细的示例。
Perl's testing system maintains a test counter. You either put the number of tests you're going to run at the top of the program, or you declare that you're not going to track it. This guard against your test exiting prematurely, but there are other guards so it's not all that important.
Every once in a while somebody tries to write a program to count the number of tests for you. This is, of course, defeated by a simple loop. They plow ahead anyway, doing more and more elaborate tricks to try and detect loops and guess how many iterations there will be and solve the halting problem. Usually they declare that it just has to be "good enough".
Here's a particularly elaborate example.
我找到了一篇伯克利论文：Looper：运行时无限循环的轻量级检测
http://www.eecs.berkeley.edu/~jburnim/pubs /BurnimJalbertStergiouSen-ASE09.pdf
LOOPER 可能很有用，因为大多数无限循环都是微不足道的错误。 然而，这篇论文甚至没有提到停机问题！
他们对它们的局限性有何看法？
换句话说，“问题将在下一个版本中得到解决”。
I found a Berkeley paper: Looper: Lightweight Detection of Infinite Loops at Runtime
http://www.eecs.berkeley.edu/~jburnim/pubs/BurnimJalbertStergiouSen-ASE09.pdf
LOOPER may be useful since most infinite loops are trivial errors. However, this paper doesn't even mention the halting problem!
What do they say about their limitations?
In other words, "the problem will be fixed in the next release".
我曾经参与过 ATM（自动柜员机）领域的一个集成项目。 客户要求我从我的系统生成一份报告，记录由国家/地区交换机发送但我的系统未收到的交易！
I was once working on an integration project in the ATM (Automated Teller Machines) domain. The client requested me to generate a report from my system for transactions sent by the country switch which were not received by my system!!
来自(Eclipse) 可视化编辑器的功能概述：
也许我现在应该坚持马蒂斯。
不相关，有人询问 Eclipse 中的停止问题。
公平地说，VE 的领域相当有限，它可能不会因为像反射这样棘手的事情而疯狂。 尽管如此，从任何 java 文件构建 GUI 的说法似乎有些停顿。
From the Functional Overview of (Eclipse) Visual Editor:
Maybe I should stick with Matisse for now.
Unrelated, here's someone asking for the halting problem within Eclipse.
To be fair, VE's domain is quite limited, and it probably won't go crazy over tricky things like reflection. Still, the claim to build GUI out of any java file seems halt-ish.
“你如何向我保证你的代码 100% 没有错误？”
"How can you assure me your code is 100% free of bugs?"