Hacker News new | ask | show | jobs
by burgerbrain 5522 days ago
"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)
1 comments
grav1tas 5522 days ago
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 ;-).
link
burgerbrain 5522 days ago
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.

link
shasta 5522 days ago
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.

link
grav1tas 5522 days ago
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.

link