4 ms·

There is another, more insidious, problem with trying to give a language agnostic definition: Different languages will have different symbols which are outputa

by rhelz 3y ago

There is another, more insidious, problem with trying to give a language agnostic definition: Different languages will have different symbols which are outputable. If you have a Turing machine which can only print out binary digits, then it can't print out a chinese character, no matter how long the input program is. Yeah, you can do something like unicode, and associate a binary string with each chinese character--but printing out that binary string is not printing out the chinese character. It's printing out a binary string. In particular, your lambda-calculus based turing machine cannot print out chinese characters. It therefore cannot be used to define a universal complexity for any string.

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.
canjobear 3y ago
Why is this a problem? No information is lost when characters (or graphics) are encoded in binary.
- rhelz 3y ago
  A turing machine is defined as a set of symbols which it can read/write to the tape, and a state machine which maps the current symbol read to the next state and some actions. 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.
SimplyUnknown 3y ago
But Chinese (or mandarin) is not a context-free grammar whereas I believe that encoding a language on a turing machine implies a context-free grammar so this example doesn't hold.
- rhelz 3y ago
  Well, a couple of points: its not obvious that Chinese doesn't have a context-free grammar: see the talk by David Branner: "The Grammar of Classical Chinese is Very Close to Being a Context-Free Grammar". And a properly programmed turing machine can parse languages which are way more complex than context-free languages are.
AnotherGoodName 3y ago
This is quite misguided as you seem to think the alphabet for Shannon entropy or Kolmogorov complexity is in any way what we think of as an alphabet. Did you know the best compression methods out all have a variable length (measured in bits) alphabet? eg. Dynamic Markov Coding will start with just '0' and '1' and then predict the next bit but as it see's more symbols it will extend this to single characters (so see 'a' or 'b' and predict the next bit). They'll then continue as they learn more of the file and their alphabet will essentially include common pairwise letters, then words and entire common phrases. This is actually a commonly missed aspect of Shannon entropy. A file of 0111101110111 repeated will give you a different result if you consider a 1 bit alphabet of 25% '0' and 75% '1' than a 4 bit alphabet of 100% '0111'. No one in the real world is using the character frequencies of english characters as a measure of Shannon entropy or Kolmogorov complexity. No algorithm expects that. They all work at the binary level and they will try to adjust the symbol lengths of the alphabet to common sequences to achieve the best result. This is in fact the reason Kolmogorov complexity is used rather than Shannon entropy. Shannon entropy doesn't tell you how to define an optimal alphabet. That part is actually undefinable. It just tells you what to do if you have that already. Kolmogorov complexity says more completely 'find the optimal alphabet and the symbol probabilities and make a minimal sequence from that'. Different human languages don't figure into this at all and are completely irrelevant.
- rhelz 3y ago
  > Different human languages don't figure into this at all and are completely irrelevant. Back to basics: A Turing machine is specified by a set of symbols it can read/write to a tape, and a state machine matching current state and read symbol to next state and actions. If that set of symbols is just {1,0}, then it absolutely, positively, cannot print out the string "ABC". > the best compression methods out all have a variable length (measured in bits) alphabet. This is a category error....if the compression algorithm reads and writes binary data, its alphabet is "zero" and "one." The symbols read and written by a Turing machine are atomic--they are not composed of any simpler parts. Sure, external to the turning machine, you can adopt some conventions which map bit patterns to letters in a different alphabet. But a binary Turing machine cannot print out those letters--it can only print out a string of 1's and 0's. 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. This is a subtle problem, often glossed over or just missed entirely. We are so used to encoding things in binary that it might not occur to us unless we think about it deeply. Nevertheless, it is a real, genuine problem.
tromp 3y ago
> It therefore cannot be used to define a universal complexity for any string. It defines a complexity for anything which can be represented in binary. Which in practice is all we want. Who wants to define a new complexity measure for every new alphabet of symbols?

by rhelz 3y ago

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.

canjobear 3y ago

Why is this a problem? No information is lost when characters (or graphics) are encoded in binary.

rhelz 3y ago
A turing machine is defined as a set of symbols which it can read/write to the tape, and a state machine which maps the current symbol read to the next state and some actions. 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.

SimplyUnknown 3y ago

But Chinese (or mandarin) is not a context-free grammar whereas I believe that encoding a language on a turing machine implies a context-free grammar so this example doesn't hold.

rhelz 3y ago
Well, a couple of points: its not obvious that Chinese doesn't have a context-free grammar: see the talk by David Branner: "The Grammar of Classical Chinese is Very Close to Being a Context-Free Grammar". And a properly programmed turing machine can parse languages which are way more complex than context-free languages are.

AnotherGoodName 3y ago

This is quite misguided as you seem to think the alphabet for Shannon entropy or Kolmogorov complexity is in any way what we think of as an alphabet. Did you know the best compression methods out all have a variable length (measured in bits) alphabet? eg. Dynamic Markov Coding will start with just '0' and '1' and then predict the next bit but as it see's more symbols it will extend this to single characters (so see 'a' or 'b' and predict the next bit). They'll then continue as they learn more of the file and their alphabet will essentially include common pairwise letters, then words and entire common phrases. This is actually a commonly missed aspect of Shannon entropy. A file of 0111101110111 repeated will give you a different result if you consider a 1 bit alphabet of 25% '0' and 75% '1' than a 4 bit alphabet of 100% '0111'. No one in the real world is using the character frequencies of english characters as a measure of Shannon entropy or Kolmogorov complexity. No algorithm expects that. They all work at the binary level and they will try to adjust the symbol lengths of the alphabet to common sequences to achieve the best result. This is in fact the reason Kolmogorov complexity is used rather than Shannon entropy. Shannon entropy doesn't tell you how to define an optimal alphabet. That part is actually undefinable. It just tells you what to do if you have that already. Kolmogorov complexity says more completely 'find the optimal alphabet and the symbol probabilities and make a minimal sequence from that'. Different human languages don't figure into this at all and are completely irrelevant.

rhelz 3y ago
> Different human languages don't figure into this at all and are completely irrelevant. Back to basics: A Turing machine is specified by a set of symbols it can read/write to a tape, and a state machine matching current state and read symbol to next state and actions. If that set of symbols is just {1,0}, then it absolutely, positively, cannot print out the string "ABC". > the best compression methods out all have a variable length (measured in bits) alphabet. This is a category error....if the compression algorithm reads and writes binary data, its alphabet is "zero" and "one." The symbols read and written by a Turing machine are atomic--they are not composed of any simpler parts. Sure, external to the turning machine, you can adopt some conventions which map bit patterns to letters in a different alphabet. But a binary Turing machine cannot print out those letters--it can only print out a string of 1's and 0's. 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. This is a subtle problem, often glossed over or just missed entirely. We are so used to encoding things in binary that it might not occur to us unless we think about it deeply. Nevertheless, it is a real, genuine problem.

tromp 3y ago

> It therefore cannot be used to define a universal complexity for any string. It defines a complexity for anything which can be represented in binary. Which in practice is all we want. Who wants to define a new complexity measure for every new alphabet of symbols?