4 ms·
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 everythi
by nostrademons 17y ago
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.
- Herring 17y agoYeah CS theory & practice are often quite different. http://en.wikipedia.org/wiki/Termination_analysis http://en.wikipedia.org/wiki/Termination_analysis
- gjm11 17y agoI 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.