4 ms·
You can only prove that the answer is incorrect.
by duh 17y ago
You can only prove that the answer is incorrect.
- amichail 17y agoWhy would you think that?
- jey 17y agoIt only takes a counter-example (an example of a shorter program) to show that an answer is incorrect, but you could probably pick up a Turing Award or two if you find a way to put a tight bound on the Kolmogorov complexity of a bit string.
- eru 17y agoIt's only difficult in general. Nobody says there aren't any easy instances.
- jey 17y agoSure, there's a bunch of trivial/easy ones for programs that do almost nothing, but I really wonder if are there any interesting programs for which tight bounds are known?
- eru 17y agoLook at primitive recursive functions. E.g. see http://en.wikipedia.org/wiki/Primitive_recursive_function http://en.wikipedia.org/wiki/Primitive_recursive_function
- jey 17y agoEven if we limit it to primitive recursive functions, how can we put a bound on the Kolmogorov complexity of one? We'd need some way of coming up with bounds on the smallest Turing machine to compute that function.
- eru 17y agoThat might be possible. Primitive recursion is much less powerful than Turing machines.