3 ms·

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 pro

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.
- inimino 7y ago
  Kolmogorov complexity is just the standard name for a concept that's useful across machine learning, AI, compression, etc. It's not just a definition in some obscure result in complexity theory. OP was simply saying that, in any general-purpose programming language (where all possible programs are expressible and none are unfairly favored) the solution to problem B will inevitably be longer than problem A. This is quite a bit more precise than just saying "a more complicated problem", and if you have the intuition behind it, there's no reason not to use the term.
  - YeGoblynQueenne 7y ago
    I'm not convinced but we've taken this far enough I think. Thank you for an insightful conversation.
    - inimino 7y ago
      Thank you too!

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.

inimino 7y ago
Kolmogorov complexity is just the standard name for a concept that's useful across machine learning, AI, compression, etc. It's not just a definition in some obscure result in complexity theory. OP was simply saying that, in any general-purpose programming language (where all possible programs are expressible and none are unfairly favored) the solution to problem B will inevitably be longer than problem A. This is quite a bit more precise than just saying "a more complicated problem", and if you have the intuition behind it, there's no reason not to use the term.
- YeGoblynQueenne 7y ago
  I'm not convinced but we've taken this far enough I think. Thank you for an insightful conversation.
  - inimino 7y ago
    Thank you too!