5 ms·

The article abuses Kolmogorov complexity... > When it is applied to the algorithms, it means that an algorithm with the shortest implementation is simpler. Th

by ReidZB 10y ago

The article abuses Kolmogorov complexity... > When it is applied to the algorithms, it means that an algorithm with the shortest implementation is simpler. That is misleading. Kolmogorov complexity is the length of the shortest program (in a pre-defined language) that produces a given object. So, if the shortest program that produces Algorithm A is smaller than the shortest program that produces Algorithm B, then the Algorithm A is less Kolmogorov-complex ("simpler") than Algorithm A. This does not mean you can take two existing implementations (in C, say) and compare the implementation length and declare one is "simpler," unless you are claiming that both implementations are as short as possible. Since Kolmogorov complexity is not computable, that seems like a tall order. Maybe they are right that Single-Decree Paxos is simpler (either in the sense of Kolmogorov complexity or in some other sense, who knows), but invoking Kolmogorov complexity here seems totally unwarranted -- it doesn't add anything substantive.

rystsov 10y ago
Thank you! I'll rework this paragraph to be correct, I wanted to make an observation that the given data (two attempts to implement key-value storages with keeping the length of a program as short as possible) favour Gryadka but of course isn't wrong to make strong statements based just on one data point.
- jerf 10y ago
  I would suggest just dropping Kolmogorov in general, and just referencing the human idea that shorter is generally going to be simpler. I wouldn't have a problem sticking with you through that. Sure, I can feed that to my pedant mill as with anything else, but since it's not really the core idea I'll roll with you on it.
  - ReidZB 10y ago
    Agreed. The section basically boils down to "despite maybe looking simpler, Single-Decree Paxos is still tricky." I don't think something particular and formal like Kolmogorov complexity even fits the tone there.
    - throwaway91111 10y ago
      Right. There's no strict value to higher or lower complexity in the Kolmogorov sense, so you might as well assign the value to something more tangible (like pseudocode terseness or something)
- joe_the_user 10y ago
  Yeah, The problem isn't just the incomputable quality of Kolmogorov complexity but that fact that Kolmogorov complexity applies only to finite strings or things that can be meaningfully mapped to them. Especially, Kolmogorov doesn't apply directly to abstract algorithms or programs with multiple implementations.
  - mafribe 10y ago
    The concept of Kolmogorov complexity can be extended to infinite strings, see e.g. L. Staiger's _The Kolmogorov complexity of infinite words_ (https://www.sciencedirect.com/science/article/pii/S0304397507003180 https://www.sciencedirect.com/science/article/pii/S030439750...).
eutectic 10y ago
Kolmogorov complexity is not computable in general, but it is decidable for a substantial subset of programs.
- moyix 10y ago
  Really? Do you have an example of a substantial set of programs where that holds? I don't see a priori how it could work unless you can do exhaustive search over the space of all programs and determine if they halt and return the right answer.
  - yorwba 10y ago
    The hard part here is not finding a set of programs that always halt (primitive recursive functions can compute anything you'd ever want to run on large inputs), but proving that they are correct (I'm pretty sure equivalence of primitive recursive functions is undecidable). Edit: but if someone gives you the primitive recursive Kolmogorov complexity of a program, you can check it by running all shorter programs on all inputs until you found a counterexample for each of them. So it is semi-decidable. Edit to edit: This would even work for the general Turing-machine definition of Kolmogorov complexity.
    - vog 10y ago
      > The hard part here is not finding a set of programs that always halt [...], but proving that they are correct (I'm pretty sure equivalence of primitive recursive functions is undecidable). This may be true, but: If you use primitive recursive functions (instead of turing complete) because of practicality, with the same reasoning you can cap the inputs at some insanely large number. Then, these functions still "can compute anything you'd ever want to run on large inputs". In that setting, equivalence is decidable, because you can simply run both functions over the finite set of all possible inputs.
  - slaymaker1907 10y ago
    Formally, there are quite a few which are quite simple to show. For instance, for the string 'a', the shortest python problem which can produce this string is obviously print('a') since 'a' has only one character. Additionally, if you limit your language to a recursive language, you can compute complexity (which is no longer Komnogorov) directly. Simply begin enumerating all programs in order of length and then run them checking the output to see if it is that string. While this is by no means efficient, it works for recursive functions since they must halt. For Komogorov complexity, there isn't really a notion of inputs, merely that some particular string should be produced as output. For recursively enumerable (i.e. Turing complete) languages, the former method will not work because a program might run forever.
pizza 10y ago
related: "Program-Size Complexity Computes the Halting Problem", https://www.cs.auckland.ac.nz/research/groups/CDMTCS/researchreports/008HHP.pdf https://www.cs.auckland.ac.nz/research/groups/CDMTCS/researc...

by ReidZB 10y ago

rystsov 10y ago

Thank you! I'll rework this paragraph to be correct, I wanted to make an observation that the given data (two attempts to implement key-value storages with keeping the length of a program as short as possible) favour Gryadka but of course isn't wrong to make strong statements based just on one data point.

jerf 10y ago
I would suggest just dropping Kolmogorov in general, and just referencing the human idea that shorter is generally going to be simpler. I wouldn't have a problem sticking with you through that. Sure, I can feed that to my pedant mill as with anything else, but since it's not really the core idea I'll roll with you on it.
- ReidZB 10y ago
  Agreed. The section basically boils down to "despite maybe looking simpler, Single-Decree Paxos is still tricky." I don't think something particular and formal like Kolmogorov complexity even fits the tone there.
  - throwaway91111 10y ago
    Right. There's no strict value to higher or lower complexity in the Kolmogorov sense, so you might as well assign the value to something more tangible (like pseudocode terseness or something)
joe_the_user 10y ago
Yeah, The problem isn't just the incomputable quality of Kolmogorov complexity but that fact that Kolmogorov complexity applies only to finite strings or things that can be meaningfully mapped to them. Especially, Kolmogorov doesn't apply directly to abstract algorithms or programs with multiple implementations.
- mafribe 10y ago
  The concept of Kolmogorov complexity can be extended to infinite strings, see e.g. L. Staiger's _The Kolmogorov complexity of infinite words_ (https://www.sciencedirect.com/science/article/pii/S0304397507003180 https://www.sciencedirect.com/science/article/pii/S030439750...).

eutectic 10y ago

Kolmogorov complexity is not computable in general, but it is decidable for a substantial subset of programs.

moyix 10y ago
Really? Do you have an example of a substantial set of programs where that holds? I don't see a priori how it could work unless you can do exhaustive search over the space of all programs and determine if they halt and return the right answer.
- yorwba 10y ago
  The hard part here is not finding a set of programs that always halt (primitive recursive functions can compute anything you'd ever want to run on large inputs), but proving that they are correct (I'm pretty sure equivalence of primitive recursive functions is undecidable). Edit: but if someone gives you the primitive recursive Kolmogorov complexity of a program, you can check it by running all shorter programs on all inputs until you found a counterexample for each of them. So it is semi-decidable. Edit to edit: This would even work for the general Turing-machine definition of Kolmogorov complexity.
  - vog 10y ago
    > The hard part here is not finding a set of programs that always halt [...], but proving that they are correct (I'm pretty sure equivalence of primitive recursive functions is undecidable). This may be true, but: If you use primitive recursive functions (instead of turing complete) because of practicality, with the same reasoning you can cap the inputs at some insanely large number. Then, these functions still "can compute anything you'd ever want to run on large inputs". In that setting, equivalence is decidable, because you can simply run both functions over the finite set of all possible inputs.
- slaymaker1907 10y ago
  Formally, there are quite a few which are quite simple to show. For instance, for the string 'a', the shortest python problem which can produce this string is obviously print('a') since 'a' has only one character. Additionally, if you limit your language to a recursive language, you can compute complexity (which is no longer Komnogorov) directly. Simply begin enumerating all programs in order of length and then run them checking the output to see if it is that string. While this is by no means efficient, it works for recursive functions since they must halt. For Komogorov complexity, there isn't really a notion of inputs, merely that some particular string should be produced as output. For recursively enumerable (i.e. Turing complete) languages, the former method will not work because a program might run forever.

pizza 10y ago

related: "Program-Size Complexity Computes the Halting Problem", https://www.cs.auckland.ac.nz/research/groups/CDMTCS/researchreports/008HHP.pdf https://www.cs.auckland.ac.nz/research/groups/CDMTCS/researc...