When have you come upon the halting problem in the field? [closed]

When have you ever personally come upon the halting problem in the field? This can be when a co-worker / boss suggested a solution which would violate the fundamental limits of computation, or when you realized yourself that a problem you were trying to solve was, in fact, impossible to solve.

The most recent time I came up with it was when studying type checkers. Our class realized that it would be impossible to write a perfect type checker (one that would accept all programs that would run without type errors, and reject all programs that would run with type errors) because this would, in fact, solve the halting problem. Another was when we realized, in the same class, that it would be impossible to determine whether a division would ever occur by zero, in the type-checking stage, because checking whether a number, at run-time, is zero, is also a version of the halting problem.

Solution 1:

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.

Solution 2:

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.

Solution 3:

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.

Solution 4:

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++.