3 ms·
This may sound silly, but does any aspect of this take into account which language is used to print the string? Suppose there's a language where a single dot ".
by _greim_ 8y ago
This may sound silly, but does any aspect of this take into account which language is used to print the string? Suppose there's a language where a single dot "." is the command to print out some particular string. Then that string's complexity in that language is the shortest possible, and so forth. I guess that language's implementation would somehow have to contain a representation of the string, but that just begs the question of what meta-language the language is implemented in.
- FartyMcFarter 8y agoYou need to choose a language and use it as the basis to define your Kolmogorov complexity for all strings. Otherwise, as you said, the definition of Kolmogorov complexity becomes pointless and vacuous - every string has "Kolmogorov complexity" equal to 1! Once you have done this and your language is Turing complete, your language's program sizes can be transformed to other languages' and vice-versa by simply emulating languages in each other (which does not necessarily give you the shortest possible program, but just a bound for its size).