I hate to say it, but this seems like an empty triviality. People have already mentioned the old post of Eliezer's. People have also touched on the fact that a human brain seems more complex (read:inefficient and arbitrary) than I would expect a good self-improving AGI to be. This at least suggests that the OP does little to illuminate the problem.

If we want to talk about technicalities of dubious relevance, I don't think the definition of Kolmogorov complexity logically requires what you need it to mean. The Turing machine does not need to list "all possible strings" in order to evade the problem; technically it just has to output something other than the solution in addition to the string S. This may turn out to matter somehow when it comes to the credibility of option #2, eg by allowing empirical tests.