4 ms·

> let’s assume that there exists a universal language U Why not specify it? > That gives us the true language-agnostic definition of Kolmogorov Complexity as

• 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.
  • 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?
• canjobear 3y ago
  The whole point of Kolmogorov complexity is that description lengths under different Turing-complete description languages (such as UTM and lambda calculus) are only different up to a constant that depends on the languages and not on the thing being described.
  • uoaei 3y ago
    The whole point of Kolmogorov complexity is that there exists some language for minimal description length of an arbitrary program and you compare optimal descriptions across languages. In other words, the point is to explicitly consider the choice of language as part of the encoding scheme that needs describing. That choice is included as part of the description whose length is being measured.
    • data_maan 3y ago
      Is that really true? You could just take whatever you want to describe to be part of the language and arrive trivially at a description length of 1...?
      • smilliken 3y ago
        I have an encoding improvement that can reduce the length of that program by 100% to an unbeatable 0 symbols (patent pending).
      • uoaei 3y ago
        How long is the description length of the language...?
• asplake 3y ago
  > let’s assume that there exists a universal language U such that it always gives us the shortest description length for all strings. Read on a bit and it looks like proof by contradiction: > However, let’s bring back the paradox we discussed above. According to that paradox, U cannot exist or U cannot provide shorter descriptions than every arbitrary L.