4 ms·

That is correct. However, in reality, a program whose only side effect is to terminate (or not terminate) is boring enough to be considered an edge case and cha

• barrkel 17y ago
  I don't think "boring" is the right technical term; are you suggesting that the halting problem itself is boring, since it explicitly only relates to whether programs terminate or not? The compiler is not privileged enough to state what is boring and what isn't. The example program calculates something meaningful - if it terminated, it would mean that there was a solution found, contrary to Fermat's theorem.
  • 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.
  • jfoutz 17y ago
    No, i think he's suggesting knowledge understanding and science as a whole depend on observable side effects. For example, i have a program that does in fact provide a counter example to fermat's last theorem. Unfortunately it does not print the result. If you deny observable side effects as a requirement, you must accept that i do have a program that does that. Most cs curriculums cover propositional logic. if you recall the truth table for implication, the false case always evaluates to true. my instructor used to call it the "who cares" case. If you don't demand a witness for the proposition, the compiler is under no obligation to provide one.
    • barrkel 17y ago
      I find it somewhat difficult to believe we're having this conversation in any seriousness. Consider this program fragment: for (;;) /* do nothing */; destroy_the_world(); /* has side-effects */ Would you say that a compiler that removed the loop changed the side-effects of the program?
      • _delirium 17y ago
        Yes, but in what vaguely reasonable circumstances would you write dead code whose deadness depends on the fact that an infinite loop precedes it? The fact that the C standard doesn't consider changing termination properties from nonterminating to terminating to be an impermissible optimization seems reasonably practical. The only thing I can guess at would be something in embedded-land that's using nonterminating loops as some sort of control-flow construct.
        • barrkel 17y ago
          Reasonable has nothing much to do with it, IMO; and I'm not really talking about C (it is only an example), but about compiler optimizers.
          • buster 17y ago
            In the end, this only means the following: - The C spec permits this behaviour, the Java Spec doesn't - as a programmer, know the language and the spec that you use The destroying_world() example only shows that the programmer needs to know the language he is using. The optimization is in my opinion practical and reasonable in most cases. Every programmer that depends his program workflow and important decisions on the termination of an infinite loop should be bitch slapped to hell. Do you have another more reasonable example? The only example for the infinite loop i can think of is the eventloop of some network code. But i fail to see where any code over a few lines doesn't have any side effects.