> But if we ask a similar question: does there exist an algorithm that computes K(s) of string s for arbitrary string s with length < n? The answer is yes! And

> But if we ask a similar question: does there exist an algorithm that computes K(s) of string s for arbitrary string s with length < n? The answer is yes! And there exists such an algorithm for any value of n. of course - n is by definition a finite number! and in fact at infinity, all finite numbers are quite small, actually. A mile might as well be a millimeter, from your chair at the end of the universe. And your scenario is basically just "hilbert's infinite hotel, on a computer" - we can of course add another program simply by moving all the existing programs 1 spot over... and it remains the exact same size of table needed to compute it! I would actually generalize this and just say that most people have poor intuition of how infinities (alephs, etc) and transfinite mathematics work in general. it's not a common subject, it's not a subject with everyday relevance, and it's deeply steeped in the emergent properties of mathematics and category/set theory. Like not only are infinities bigger than any finite number, but some infinities can nevertheless be bigger than other infinities etc - these are not things that are immediately obvious to the 3rd-grade concept of "infinity" that most people stop at. the much more interesting question would be if there exists an n < infinity such that the algorithm can be computed, and of course the answer is no (darn, there goes my turing prize).