3 ms·
have a look at the second post, i address that.
by Ono-Sendai 11y ago
have a look at the second post, i address that.
- mafribe 11y agoI'm sorry to say this, but your second post also doesn't really address the issue and continues to misunderstand the purpose and definitions of Kolgomorov complexity. The fact that for any specific string S you can find a language L such that the Kolgomorov complexity K(L, S) is 0, is not that interesting. 1. For any specific L, you can only play this trick (hardcoding a target string) for a finite number of strings. That means for essentially all strings (all but a small finite number) the trick is irrelevant. 2. There is no free lunch: The trick you use to bring down the Kolgomorov complexity K(L, S) down to 0 increases the complexity of L. This can be taken into account, see "conditional Kolgomorov complexity". The book "An Introduction to Kolmogorov Complexity and Its Applications" by Li and Vitányi explains this, and much more in great detail, and is highly recommended.
- Ono-Sendai 11y agoRegarding point 2, I agree, but the question is how to measure the increase in complexity - we are back at square one :)
- mafribe 11y agoYou measure it in the same way, using the idea of shortest decription w.r.t. a fixed universal language. You than show that this is absolute up to a constant. Any results produced that way such as the incompressibility of most strings is independent of such constants, hence the the choice of universal language doesn't matter.