The relevant value of K here is something like the total number of bits of information embodied in, and available to, the whole human race, including whatever other bits of the universe we may happen to recruit for our use. So K might be extremely large.

Now let me remind you that the size and (in ordinary informal terms) complexity, and indeed the speed, of a hypothetical Thinking Device scarcely influence its Kolmogorov complexity. If it takes some number of bits to specify a machine with 3^^^3 bits of memory or 3^^^3 artificial neurons, it takes only a few bits more to replace 3^^^3 with 3^^^^3.

So I'm going to go with "option 1, for all practical purposes". All it requires is that there be a recipe for How To Think that can be stated in (let's say) not too many orders of magnitude more space than the entire intellectual output of the human race to date, given that we're allowed to equip it with essentially-arbitrary amounts of actual hardware, such that other ways of thinking aren't in principle more powerful in the sense that they do better no matter how much hardware one throws at ours. That seems pretty plausible to me.

Eliezer wrote a blog post about this question!

An important remark: a program that is better at a task is not necessearily more complex than a program that is worse. Case in point, AlphaGo: definitely better than almost every human at go, but definitely less complex than a human mind.

Anyway, accepting the premise:

1 is demonstrably false, for any reasonable definition of intelligence (a Turing machine that can solve a problem that another TM cannot solve);

2 is surely true, given that a program can increase in complexity given more memory and a way to do unsupervised learning;

3 is too dependent to the implementation detail to judge, but it may be trivially true for a sufficiently large gap to reach.

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.

Keep in mind that adding a 'random number' instruction to a turing machine allows it to create output of infinite complexity, and that pretty much all compute hardware these days contains a hard RNG based on quantum randomness.

An interesting question.

If we write an N-bit program that runs without interacting with the world, then no matter what programming language we use, there are only about 2^N possible outputs. But it this program has made O bits of observations and has taken A bits of past actions in the environment, there are more like 2^(N+O+A) possible outcomes - and O and A can be huge compared to N. (Although that number is an overestimate - what we should add to N is the entropy of (O,A).)

So in terms of the K-complexity of artifacts that an AI can build, or output it can produce, the complexity can be incredibly (though not infinitely) high thanks to the AI's ability to interact with the environment. The real world's limits on memory and computational time will probably be stricter bounds than the limit on K-complexity.

But there's still only 2^N programs we can write. One might hype this fact up by saying that any AI worth its salt can do things too complex to have been pre-programmed. Or one might be pessimistic about it - if we want the AI to have complicated properties across a broad range of environments, that complexity is probably going to have to come from the code, and even slightly wrong code could throw us into a completely different region of the 2^(N+O+A) possible outcomes.

What what sorts of output strings are you missing?

Calculating Kolmogorov complexities is hard because because it is hard differentiate between programs that run a long time and halt and programs that run a long time and never halt.

If God gave you a 1.01 MB text file and told you "This program computes BB(1000000)", then you could easily write a program to find the Kolmogorov complexity of any string less then 1 MB.

kolmogorov_map = defaultdict(lambda x : infinity)

for all strings *p* less than 1000000:

    run *p* for at most BB(1000000) steps

    save output to *o*

    if (*p* halted and kolmogorov_map[*o*] > len(p):

        kolmogorov_map[*o*] = len(p) # found smaller program

    else:
        # *p* does not ever ever halt and has no output

Replace BB(1000000) with a smaller number, say A(Graham's number, Graham's number), and this calculator works for all programs which halt in less than A(Graham's number, Graham's number) steps. That includes pretty much every program I care about! For instance, it includes every program which could run under known physics in the age of the universe.

It is an interesting way of looking at the maximal potential of AIs. It could be that Oracle Machines are possible in this universe, but an AI built by humans cannot self-improve to that point because of the bound you are describing.

I feel that the phrasing "we have reached the upper bound on complexity" and later "can rise many orders of magnitude" gives a potentially misleading intuition about how limiting this bound is. Do you agree that this bound does not prevent us from building "paperclipping" AIs?