2 ms·

Compare to the reddit-thread and the other comments. I define boring as "without side effects", that is, without io-access, without access to volatile variables

by tetha 17y ago

Compare to the reddit-thread and the other comments. I define boring as "without side effects", that is, without io-access, without access to volatile variables and such according to the C-Spec. Boring also is language dependant, of course, as different languages have different side effects. And yes, as such, I define the theoretically interesting halting problem as practically boring, because I only care about the result my program computes and outputs. If there is no output, there is no output -- not even the possibility of output, no matter if my program runs in less than a second, an hour, a year or infinitely long. Yes, technically they are differnt programs. Practically, I run the program, notice "What the... how is it so fast?", notice the missing printf in there, add it (while being happy about the change in semantics which saved me several minutes), see the result and do something useful.

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.

by tetha 17y ago

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.