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.
Re:How decompilers work
by burgerbrain on Thursday May 05, 2011 @04:22PM
(#2518772)
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.
Re:How decompilers work
by burgerbrain on Thursday May 05, 2011 @05:05PM
(#2518897)
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.
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.