6 ms·

The Kolmogorov complexities of the best programs to solve those two classes of problems, digit multiplication vs Starcraft, are quite different. Edit: We don’t

The Kolmogorov complexities of the best programs to solve those two classes of problems, digit multiplication vs Starcraft, are quite different. Edit: We don’t know the best programs, but we can approximate the bounds with some confidence that, unless some paradigm-changing discovery is made, the programs to solve digit multiplication would be significantly simpler. (This is not a formal argument, but the intuition is very strong for most people who study the problems seriously.)

YeGoblynQueenne 7y ago
How did you calculate the Kolmogorov complexity of those two classes of program?
- neurocline 7y ago
  I wrote a decent fraction of the code in the original Starcraft, so, yes, I can assure you the Kolmogorov complexity of Starcraft is leaps and bounds above that of multiplication :)
  - YeGoblynQueenne 7y ago
    But how did you calculate the Kolmogorov complexity of your code? Kolmogorov complexity is a distinct quantity. How did you compute this quantity?
    - neurocline 7y ago
      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.
scarejunba 7y ago
Perhaps that's the trick. The machines are better at all these things because it takes a skilled human to do them. The machines are not so good at the things it doesn't take a skilled human to do (walk, dance, fold clothes).

YeGoblynQueenne 7y ago

How did you calculate the Kolmogorov complexity of those two classes of program?

neurocline 7y ago
I wrote a decent fraction of the code in the original Starcraft, so, yes, I can assure you the Kolmogorov complexity of Starcraft is leaps and bounds above that of multiplication :)
- YeGoblynQueenne 7y ago
  But how did you calculate the Kolmogorov complexity of your code? Kolmogorov complexity is a distinct quantity. How did you compute this quantity?
  - neurocline 7y ago
    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.

scarejunba 7y ago

Perhaps that's the trick. The machines are better at all these things because it takes a skilled human to do them. The machines are not so good at the things it doesn't take a skilled human to do (walk, dance, fold clothes).