News for hackers. Stuff that matters.
Re:The Single Sign On by nostrademons on Wednesday March 10, 2010 @02:54AM (#1180433)
3. It's quite possible to determine what the Kolmogorov complexity of something is, it's only impossible to determine what the Kolmogorov complexity of everything is. The halting problem only states that it's impossible to prove whether an arbitrary Turing machine halts. There're many Turing machines that can be proved to halt, some quite easily. For example,

  int main(int argc, char** argv) {
    return 1;
  }
can be proved to halt pretty easily, just looking at the CFG for the program.
Re:The Single Sign On by gjm11 on Wednesday March 10, 2010 @04:56AM (#1180572)
I think that even in practice being able to determine the Kolmogorov complexity exactly is very decidedly not the usual case; you need to know that every program shorter than your candidate fails to do the right thing.

Your general point is very much correct, though. A clearer-cut application: In general, one cannot prove that a program does what it's supposed to; but if doing that is important, "all" you have to do is write it in a way that makes a correctness proof possible.

Re:The Single Sign On by Herring on Wednesday March 10, 2010 @04:33AM (#1180555)
Yeah CS theory & practice are often quite different.

http://en.wikipedia.org/wiki/Termination_analysis