Kolmogorov Complexity and Compression Distance

Re:Kolmogorov Complexity and Compression Distance by causal on Saturday March 30, 2024 @04:49PM (#39878504)

Still confused. What is contradictory about a simple program computing a more complex program? Randomly generating a more complex program does not make the complex program reducible to a random string generator.

[ Parent | on HN ]

Re:Kolmogorov Complexity and Compression Distance by basil-rash on Saturday March 30, 2024 @07:23PM (#39879629)

The complexity cannot be over 10,000,000 if that simple program generated it. That is the precise definition of complexity.

I don’t understand what you mean by reducibility to random strings, randomness has precisely nothing to do with complexity, even if they do tend to go together.

[ Parent | on HN ]

Re:Kolmogorov Complexity and Compression Distance by Dylan16807 on Sunday March 31, 2024 @09:43PM (#39890083)

> Randomly generating a more complex program does not make the complex program reducible to a random string generator.

The complex program probably does something other than generate random strings.

But the complex program is not actually more complex than the generator plus a smidge.

Because anywhere you're using the complex(z), you can replace it with generator()(z).

[ Parent | on HN ]