2 ms·
The Halting problem is primarily practically useful in automated program analysis, of which the most common instance is compiler optimizers. I'm loathe to refe
by barrkel 17y ago
The Halting problem is primarily practically useful in automated program analysis, of which the most common instance is compiler optimizers.
I'm loathe to reference Wikipedia as an authority, but it's even quoted there as part of a proof as to why compilers cannot optimize programs as much as might be possible:
http://en.wikipedia.org/wiki/Compiler_optimization http://en.wikipedia.org/wiki/Compiler_optimization
However, optimizing compilers are by no means perfect. There is no way that a compiler can guarantee that, for all program source code, the fastest (or smallest) possible equivalent compiled program is output; such a compiler is fundamentally impossible because it would solve the halting problem.
This may be proven by considering a call to a function, foo(). This function returns nothing and does not have side effects (no I/O, does not modify global variables and "live" data structures, etc.). The fastest possible equivalent program would be simply to eliminate the function call. However, if the function foo() in fact does not return, then the program with the call to foo() would be different from the program without the call; the optimizing compiler will then have to determine this by solving the halting problem.