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

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 https://en.wikipedia.org/wiki/Interesting_number_paradox [1] https://en.wikipedia.org/wiki/Berry_paradox https://en.wikipedia.org/wiki/Berry_paradox