5 ms·

I feel like a conversion from binary strings to Unicode/Chinese characters would be in PTIME, so adding a conversion machine would be a nonfactor for languages

by mxkopy 3y ago

I feel like a conversion from binary strings to Unicode/Chinese characters would be in PTIME, so adding a conversion machine would be a nonfactor for languages in most complexity classes.

smallnamespace 3y ago
The stronger result here is that any sort of conversion you can explicitly specify can be turned into a program. Since Kolmogorov Complexity is specified in terms of lengths of programs, that means the KC between two different pairs of encodings can differ at most by a constant amount (the size of the program that converts back and forth). The above is a bit handwavey, there are details you can tighten up (Is it the program size or something smaller? The program length in which encoding?), but heuristically that's why theorists can talk about "the" Kolmogorov complexity without getting bogged down in with pesky encoding details. It's also why we usually don't worry too much about the fine details of Turing Machines (alphabet, etc.), since you can generally emulate one sort of Turing Machine pretty easily with a short program written on another.
- rhelz 3y ago
  > any sort of conversion you can explicitly specify can be turned into a program. If your Turing machine can only print out zeros and ones, there's no program which can get it to print out "ABC". So it cannot specify a conversion between a language whose symbols are {0,1} and a language whose symbols are {"A",B","C"}. It could specify a mapping between one binary string and another binary string, but it can't even print out "ABC" so how could it possibly specify a conversion? This is elementary guys.
  - smallnamespace 3y ago
    You pick an obvious encoding (such as binary) yourself, in the same way your computer is not outputting some platonic ideal "A" but a series of electrical impulses that your monitor plus your eyes and brain interprets as "A". 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.
    - rhelz 3y ago
      Well, here's why it's not that simple....I can make any number N have a kolmogorov complexity number equal to 1--if the Turing machine has N+1 symbols :-) I just express the number in base N. (which will bet "10" for any base :-) It true that we typically limit ourselves to binary when we are proving theorems, etc in Kolmogorov complexity. You can prove that for any two turing machines U and V, KU(X) <= KV(X) + O(1).....but this relies on the fact that there is an O(1)-sized program which lets U emulate V, and V emulate U. And that is only true if U and V share the same symbol set. If they don't, then the kolmogorov complexity of the two machines can be made arbitrarily different from each other, just by changing the symbol set.
  - cscurmudgeon 3y ago
    It is not an intractable problem as you believe it is. E.g., make the machine print out pixel values for a large screen. The screen can display Chinese characters in canonical ways.
    - rhelz 3y ago
      This might sound a bit...but hang with me please... Are the symbols "0" and "1" also definable as pixel values on a large screen? If so, what is a pixel? It it further composed of smaller micro pixels? Or is it pixels all the way down? What I'm saying is that a binary computer cannot write "A" to its memory any more than you can write a green patch to a black-and white monitor's pixel. Sure, there are various work around...you could dither, and make some bit patterns represent red, green, etc...or you could put a picture of an apple onscreen with an arrow pointing to it which said "this is red". And just like a color monitor can display more information than a black and while monitor can, the programs of a Turing machine with more symbols can express more information in smaller strings than a binary turing machine can.

by mxkopy 3y ago

I feel like a conversion from binary strings to Unicode/Chinese characters would be in PTIME, so adding a conversion machine would be a nonfactor for languages in most complexity classes.

smallnamespace 3y ago

The stronger result here is that any sort of conversion you can explicitly specify can be turned into a program. Since Kolmogorov Complexity is specified in terms of lengths of programs, that means the KC between two different pairs of encodings can differ at most by a constant amount (the size of the program that converts back and forth). The above is a bit handwavey, there are details you can tighten up (Is it the program size or something smaller? The program length in which encoding?), but heuristically that's why theorists can talk about "the" Kolmogorov complexity without getting bogged down in with pesky encoding details. It's also why we usually don't worry too much about the fine details of Turing Machines (alphabet, etc.), since you can generally emulate one sort of Turing Machine pretty easily with a short program written on another.

rhelz 3y ago
> any sort of conversion you can explicitly specify can be turned into a program. If your Turing machine can only print out zeros and ones, there's no program which can get it to print out "ABC". So it cannot specify a conversion between a language whose symbols are {0,1} and a language whose symbols are {"A",B","C"}. It could specify a mapping between one binary string and another binary string, but it can't even print out "ABC" so how could it possibly specify a conversion? This is elementary guys.
- smallnamespace 3y ago
  You pick an obvious encoding (such as binary) yourself, in the same way your computer is not outputting some platonic ideal "A" but a series of electrical impulses that your monitor plus your eyes and brain interprets as "A". 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.
  - rhelz 3y ago
    Well, here's why it's not that simple....I can make any number N have a kolmogorov complexity number equal to 1--if the Turing machine has N+1 symbols :-) I just express the number in base N. (which will bet "10" for any base :-) It true that we typically limit ourselves to binary when we are proving theorems, etc in Kolmogorov complexity. You can prove that for any two turing machines U and V, KU(X) <= KV(X) + O(1).....but this relies on the fact that there is an O(1)-sized program which lets U emulate V, and V emulate U. And that is only true if U and V share the same symbol set. If they don't, then the kolmogorov complexity of the two machines can be made arbitrarily different from each other, just by changing the symbol set.
- cscurmudgeon 3y ago
  It is not an intractable problem as you believe it is. E.g., make the machine print out pixel values for a large screen. The screen can display Chinese characters in canonical ways.
  - rhelz 3y ago
    This might sound a bit...but hang with me please... Are the symbols "0" and "1" also definable as pixel values on a large screen? If so, what is a pixel? It it further composed of smaller micro pixels? Or is it pixels all the way down? What I'm saying is that a binary computer cannot write "A" to its memory any more than you can write a green patch to a black-and white monitor's pixel. Sure, there are various work around...you could dither, and make some bit patterns represent red, green, etc...or you could put a picture of an apple onscreen with an arrow pointing to it which said "this is red". And just like a color monitor can display more information than a black and while monitor can, the programs of a Turing machine with more symbols can express more information in smaller strings than a binary turing machine can.