[kamkha]

In their example, you're not giving S as an input to K — instead, you're using K to write another program P which iterates over all possible strings and returns the first whose complexity is some value ("2 million" in their example).

That program P will certainly be longer than K (as it contains K), but not much longer — it's adding to K only the instructions needed to iterate over strings and define the threshold complexity ("2 million"). P will then produce that "2 million"-complexity output, but it didn't need any input and thus the complexity of its output is truly just the length of P (which is smaller than "2 million"). It eventually stumbles upon S by going through all possible strings, and didn't need S to be provided.

The main idea of the proof is very similar to the interesting-number paradox [0] or the Berry paradox [1].

[0] https://en.wikipedia.org/wiki/Interesting_number_paradox

[1] https://en.wikipedia.org/wiki/Berry_paradox

[margalabargala]

Got it, this makes sense, and continues to make more sense the more I think about it.

I appreciate you taking the time to break this down for me.