If $s$ is a substring so that $s \subset S$, can Kolmogorov complexity of the whole string $S$ be lower than that of the given substring, $K(S) < K(s)$?
Asked
Active
Viewed 74 times
1
-
This question is a duplicate of this one. I didn't flag it though, because the text for flagging says that the other question should have an answer, and the only answer on that one has 0 votes and hasn't been accepted. I still think they should be merged, though. – Tara B Feb 19 '13 at 12:13
1 Answers
2
Yes. The Kolmogorov complexity depends on the language used to describe the strings, but for instance if your string is the concatenation of all binary numbers with $l$ digits in increasing order, then the shortest program required to output a substring of that whose ends are in the middle of two of the numbers is likely to be longer than the shortest program required to output the whole thing, since you need to add some code to take care of the fragments at the ends.
joriki
- 238,052