Kolmogorov Complexity and Compression Distance (2023)

Pretty much all the best compression methods are language agnostic and work on bit wise sequences. They also pretty much all predict the next bit and feed that into an alogithmic encoder.

Eg. look up dynamic markov coding which is commonly used by Hutter prize winners. The paper is short and readable. They dynamically create a binary tree and binary sequences are seen so if the pattern '01101000 01100101' comes in it walks down the binary tree. It'll probably predict the next bit as '0' as '0110100001100101' just so happened to be a common sequence in English that will likely have a next bit of '0' but the Dynamic Markov coding model has no idea of that. It just has binary sequences of bits and a prediction of the next bit given that.

Likewise it can continue reading the bits of the file in and walking down its binary tree where history of the next bit are stored in every node and it see's '111001001011110110100000'. It makes the prediction of the next bit as a likely '1' that it feeds into an arithmetic coder that takes predictions and forms an optimally minimal bitsequence from that. That second binary sequence forms part of 你好.

In both cases the turing machine doesn't care about that. It's also just writing 1's and 0's as per a turing machine. Eventually those 1's and 0's form sequences that happen to map to characters in various languages but it doesn't care about that.

>The mapping from strings in the binary language to letters in the target language cannot participate in the calculations for the complexity of a string in another language. Because if it did, again, you could make the Kolmogorov complexity of any arbitrary string S you choose to be 0, because you could just say the null output maps to S.

One other thing to address here is that Kolmogorov complexity explicitly includes any dictionary you use in it's calculation. A dictionary of the file you wish to compress would just blow out your Kolmogorov complexity to that size exactly. That's why Kolmogorov complexity is an excellent tool. You explicitly cannot cheat in this way.

The symbols of the Turing machine are atomic. They are not composed of any simpler parts. If one of the Turing machine's symbol is the letter "A", it's the letter "A". It is not, say, the ascii code (1000001)

1000001 could be the Goedel number for "A", but its not the symbol "A". The two strings "A" and "1000001" are two different strings.

Its a map-vs-territory kind of thing. If you are really good at programming--which is to say, you are really good at Goedel mapping your problem to integers--you might, by years of long familiarity, just start thinking of them as one and the same, but they are not.

It might make it vivid to consider a turing machine whose symbols were {1, 0, A}. Clearly, the string "1000001" and the string "A" are two different outputs for this turing machine. The lengths of the strings "1000001" and "A" are different. They are composed of different symbols. They are absolutely, positively, not the same string, so they are not the same thing.

And a properly programmed turing machine can parse languages which are way more complex than context-free languages are.

Sure, you can object that the encoding is "outside" the TM, but for the purposes of discussing complexity these objections are pretty trivial, again for the same reasons (whatever encoding you pick the conversion process is a program you can write down, and once you write it down it means the Kolmogorov Complexity is the same between different TMs up to the length of whatever encoding/decoding program you come up with).

Put another way, a TM with alphabet is {0, 1} is technically not the same as the TM with alphabet {A, B}. But it's obvious to us that the TMs are equivalent.