4 ms·
I don't think your claims are correct. If you read a formal definition of Chaitin-Kolmogorov, you can find that the concept are essentially normalized by recur
by joe_the_user 11y ago
I don't think your claims are correct.
If you read a formal definition of Chaitin-Kolmogorov, you can find that the concept are essentially normalized by recursive function theory. By using the Church-Turing thesis, you can see that any program in any language can be simulated up to a constant length-multiple by an abstract Turing machine (speed isn't considered in these definitions so architecture doesn't matter much). Chaintin-Kolmogorov basically considers the log of the length of programs and then thus takes it's values as being plus or minus a constant for a given measure.
- Ono-Sendai 11y agohave 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.