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.
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.
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).
Given: TM length of a JS runtime is 1,000,000 cells.
Assume: KC is computable, and TM length of a `function KolmoglorovComplexity(string s)` is 4,000,000 cells.
Known: KC's of values grow infinitely large - only 2^n-1 possible values can ever be encoded by n bits.
Take: function Shortcut() { for (const s in generateEveryStringFromShortestUp()) { if ( KolomoglorovComplexity(s > 10,000,000) ) return s } }
You see that the Shortcut function is encoded in 5,000,135 cells (plus that string generator, but that's small/constant), but it computes a value of arbitrarily large complexity (rather, one cell increase in the program length causes 10x increase in the complexity). A contradiction.