3 ms·

You write code. You write the smallest possible amount of code that can solve the problem. The smallest multiprecision multiply is pretty small; I’ve written th

You write code. You write the smallest possible amount of code that can solve the problem. The smallest multiprecision multiply is pretty small; I’ve written that. Just for Starcraft pathing alone (the most complex of all the code I wrote in Starcraft) is orders of magnitude more code, even for the smallest possible version that’s not tuned for efficiency. If you’re a purist, you write the programs in MIX and you count ops. Or whatever your preferred Turing Machine is.

deleted 7y ago
[deleted]
deleted 7y ago
[deleted]
YeGoblynQueenne 7y ago
That's not any way to calculate Kolmogorov complexity. That's comparing the length of the two shortest programs that you could write to do digit multiplication and pathfinding in Starcraft.
- inimino 7y ago
  You can't calculate it. You can make strong comparative statements about it. And it is a much more specifically relevant concept than program length.
  - YeGoblynQueenne 7y ago
    Can you, though, "make strong comparative statements"? How do you know what is the shortest program to perform some operation, X, in a language L? I'm prepared to agree that on the balance of probabilities the pathfinding code in Starcraft _should_ be inherently more complex than that for multiplication- but that is just intuition, whereas Kolmogorov complexity is a formal concept that does not admit intuitive judgements. Which is (part of) why it's necessary. If we could just compare the length of programs in some language and determine their relative Kolmogorov complexity from that, then there wouldn't be no need to define Kolmogorov complexity. We'd just make do with program length. I know that sounds pedantic and this is the internet and not a scientific paper etc, but if this is an informal discussion then formal terminology like "Kolmogorov complexity" has no place in it and the purpose of the OP would, I think, be better served by using an informal term. If you 're gonna use maths, use maths. If you 're gonna wave hands, then wave hands, by all means. But don't mix the two, it just makes a mess. Because at the end of the day I can just say, "no, I don't believe that multiplication has smaller Kolmogorov complexity than Starcraft's pathfinding"... and then, what? Where do we go from there? The OP says "yes it does", I say "no it doesn't", the OP says "does too", I say "nuh-huh". And we just waste our time.
    - inimino 7y ago
      The OP says: > yes, I can assure you the Kolmogorov complexity ... This is a strong comparative statement, and it's clear that it's an assertion but not a proof. So it's perfectly fine for you to say "I don't believe that" and then you would give your reasoning. Of course the conversation didn't go that way because it's pretty obvious to everyone that this is actually true even though we don't have a proof. And it's extremely likely that if you could find a minimal multiplication algorithm and enumerate all the Turing machines up to that length you could prove that none of them solve the harder problem. This is where the intuition comes from. > using an informal term But the OPs argument wasn't that one program would happen to be longer, but rather that it must by necessity be longer, because the problem is fundamentally more complex, which is exactly what the formal concept was created to capture. > Kolmogorov complexity is a formal concept that does not admit intuitive judgements This is a bad way of thinking about maths. The value of formal concepts is precisely that they give us tools for making intuitive judgements more effectively and give us a wider variety of tools to manipulate and express our intuition. As intuitions become conjectures and theorems, we accumulate new bedrock we can use for new intuitions, but don't short-circuit your thinking by saying that intuition about technical terms is off-limits. That's literally what they are good for.
      - YeGoblynQueenne 7y ago
        >> This is a bad way of thinking about maths. I don't agree. I don't need formal terms to develop intuition. Formal terms are necessary when speaking formally, and they are only detracting from the point of a discussion otherwise. And I don't agree with this either: >> But the OPs argument wasn't that one program would happen to be longer, but rather that it must by necessity be longer, because the problem is fundamentally more complex, which is exactly what the formal concept was created to capture. The way I understand it the formal concept is useful in proofs of the impossibility to calculate various other quantitites. Its utility is not to argue that this or that program should intuitively have lower Kolmogorov complexity. To be honest, I'm so confused by the use of the term by the OP that I have no idea what they meant to say with it.
        7y ago

deleted 7y ago

[deleted]

deleted 7y ago

[deleted]

YeGoblynQueenne 7y ago

That's not any way to calculate Kolmogorov complexity. That's comparing the length of the two shortest programs that you could write to do digit multiplication and pathfinding in Starcraft.

inimino 7y ago
You can't calculate it. You can make strong comparative statements about it. And it is a much more specifically relevant concept than program length.
- YeGoblynQueenne 7y ago
  Can you, though, "make strong comparative statements"? How do you know what is the shortest program to perform some operation, X, in a language L? I'm prepared to agree that on the balance of probabilities the pathfinding code in Starcraft _should_ be inherently more complex than that for multiplication- but that is just intuition, whereas Kolmogorov complexity is a formal concept that does not admit intuitive judgements. Which is (part of) why it's necessary. If we could just compare the length of programs in some language and determine their relative Kolmogorov complexity from that, then there wouldn't be no need to define Kolmogorov complexity. We'd just make do with program length. I know that sounds pedantic and this is the internet and not a scientific paper etc, but if this is an informal discussion then formal terminology like "Kolmogorov complexity" has no place in it and the purpose of the OP would, I think, be better served by using an informal term. If you 're gonna use maths, use maths. If you 're gonna wave hands, then wave hands, by all means. But don't mix the two, it just makes a mess. Because at the end of the day I can just say, "no, I don't believe that multiplication has smaller Kolmogorov complexity than Starcraft's pathfinding"... and then, what? Where do we go from there? The OP says "yes it does", I say "no it doesn't", the OP says "does too", I say "nuh-huh". And we just waste our time.
  - inimino 7y ago
    The OP says: > yes, I can assure you the Kolmogorov complexity ... This is a strong comparative statement, and it's clear that it's an assertion but not a proof. So it's perfectly fine for you to say "I don't believe that" and then you would give your reasoning. Of course the conversation didn't go that way because it's pretty obvious to everyone that this is actually true even though we don't have a proof. And it's extremely likely that if you could find a minimal multiplication algorithm and enumerate all the Turing machines up to that length you could prove that none of them solve the harder problem. This is where the intuition comes from. > using an informal term But the OPs argument wasn't that one program would happen to be longer, but rather that it must by necessity be longer, because the problem is fundamentally more complex, which is exactly what the formal concept was created to capture. > Kolmogorov complexity is a formal concept that does not admit intuitive judgements This is a bad way of thinking about maths. The value of formal concepts is precisely that they give us tools for making intuitive judgements more effectively and give us a wider variety of tools to manipulate and express our intuition. As intuitions become conjectures and theorems, we accumulate new bedrock we can use for new intuitions, but don't short-circuit your thinking by saying that intuition about technical terms is off-limits. That's literally what they are good for.
    - YeGoblynQueenne 7y ago
      >> This is a bad way of thinking about maths. I don't agree. I don't need formal terms to develop intuition. Formal terms are necessary when speaking formally, and they are only detracting from the point of a discussion otherwise. And I don't agree with this either: >> But the OPs argument wasn't that one program would happen to be longer, but rather that it must by necessity be longer, because the problem is fundamentally more complex, which is exactly what the formal concept was created to capture. The way I understand it the formal concept is useful in proofs of the impossibility to calculate various other quantitites. Its utility is not to argue that this or that program should intuitively have lower Kolmogorov complexity. To be honest, I'm so confused by the use of the term by the OP that I have no idea what they meant to say with it.
      - 7y ago