3 ms·
Similar to how the interesting number paradox relies on a "shortcut statement" to force-up the number of non-interest, If Kolmogorov complexity were computable
by explaininjs 3y ago
Similar to how the interesting number paradox relies on a "shortcut statement" to force-up the number of non-interest, If Kolmogorov complexity were computable you could create a "shortcut program" to force-down the shortest length of the program:
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.
- causal 3y agoStill 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.
- basil-rash 3y agoThe 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.
- Dylan16807 3y ago> 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).