Hacker News Reader

Comment by grav1tas | Hacker News Reader

The set of all possible inputs for a compiler is infinite, too. Does that mean that compilers are all harangued by the halting problem as well? Nope. Having an infinite number of possible inputs (infinite input set size) does not prevent you from showing that a program can actually halt. I think most compilers are written in a way that can be shown to halt, as well.

The Halting Problem does apply in the general case, but if you carve up your programs and reason about them, you can still show that you can have a halter. The Halting Problem just states that there does not exist a method that will take an arbitrary program and show it to be a halter.

View on HN

"The set of all possible inputs for a compiler is infinite, too. Does that mean that compilers are all harangued by the halting problem as well? "

No, because unlike this "try all possible inputs" plan for decompilers, compilers only operate on any particular single input.

"I think most compilers are written in a way that can be shown to halt, as well."

Not C++ compilers (Turing Complete macros) or Lisp dialects (same issue, but even moreso)

The point about the macros being Turing Complete is trivial in this instance because if you wrote a macro that never terminated, you'd never compile anything do decompile ;-).

No, you are incorrect about the point being trivial. First off, the macros used in the original program will of course terminate, but if you simply "try every input to the compiler" like is being suggested, you will be attempting to compile any number of non-terminating macros (and you will of course not know which terminate and which do not (Halting Problem)).

The point is that "compilers terminate for every input" is trivially false.

Non-termination of some compiler inputs is a red herring. The only modification required to the original algorithm is that the search proceed in parallel (such that every input eventually makes arbitrary progress).

I agree with your point in a sister thread that decidable doesn't imply practical, but the claim of the original article was undecidable, which has a technical meaning.

I would qualify that statement better by saying "compilers with Turing Complete macros or type systems terminate for any input is trivially false". The point may not be trivial (which I'm not ready to concede), but it still doesn't matter. The author's means implicitly relies on an evasion where programs aren't written in this (rather strange) way. It's a safe assumption to say that you can eliminate programs written in such a way that will not compile, then the Halting Problem as you've stated it doesn't apply.

I think you may be right about the point your trying to make, but the point I'm making is that your point covers a negligible section of programs that the author would hope to analyze, so it doesn't matter.

My point is not about checking if the given program will halt or not.

The parent comment's suggestion was: (1) for each possible input program, (1.a) compile it, and (1.b) check if the result equals the given compiled code.

Agreed, steps (1.a) and (1.b) terminate deterministically (for a given compiler).

However, the search space for this search procedure is infinite.

Similarly, it would be impossible, in general, to exhaustively test every possible input of a compiler.

And yet, if the output you are decompiling is known to come from a particular compiler, the search will terminate.

If you know the compiler (and every other tools involved in the process), then yes, there exist at least one solution (the original input). The search will eventually find it.

Assuming all possible inputs to the compiler cause it to halt. Not true for many high-profile languages.

And while not strictly related to "is it decidable", in the real world we have to keep in mind the complexity of the solution. The presence of the naive solution for a particular language doesn't say much about how well we can* actually do it. Is the problem actually decidable within the confines of the physical observable universe for real world inputs?

"Assuming all possible inputs to the compiler cause it to halt."

If the compiler did not halt, then we don't have anything to disassemble in the first place.

Formally, it is obvious that a diagonalization-based search will eventually find a correct input, regardless of the halting status of any given input. In practice, none of this matters very much.

As I explained in my other comment, the compiler certainly does halt for the correct input, but that does not mean it will halt for all inputs.

You are however correct that this can be circumvented with diagonalization.

Reply on news.ycombinator.com