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.
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.