So, the precise statement would be that whatever weight you assign each program, if
f(n) := sum of the weights of all programs of length n
F(n) := sum of f(k) for all k < n
then limit as n goes to infinity of F(n) must be finite (if the weights are normalized, then the limit must be 1) and thus limit as n goes to infinity of f(n) must be zero. In fact, by the ratio test, the limit of f(n)/f(n+1) must be greater than or equal to one. Since there are 2^n programs of size n, that means that if
a(n) := average weight of programs of size n
then limit as n goes to infinity of a(n)/a(n+1) must be greater than or equal to 2
We are therefore highly constrained as far as the average weight for programs of size n, but less so for the maximum weight. For instance, we could have a weighting system such that for all n, there is some program of size n with weight (.999^n)/10000. We could even have a weighting system such that for all k, there is some n > k such that there is a program of length n and weight (.9999^log(log (log n) ) )/10
Do I have that correct?
PS I believe that you meant “monotonic”, rather than “monotonous” :)
So, the precise statement would be that whatever weight you assign each program, if f(n) := sum of the weights of all programs of length n F(n) := sum of f(k) for all k < n then limit as n goes to infinity of F(n) must be finite (if the weights are normalized, then the limit must be 1) and thus limit as n goes to infinity of f(n) must be zero. In fact, by the ratio test, the limit of f(n)/f(n+1) must be greater than or equal to one. Since there are 2^n programs of size n, that means that if a(n) := average weight of programs of size n then limit as n goes to infinity of a(n)/a(n+1) must be greater than or equal to 2
We are therefore highly constrained as far as the average weight for programs of size n, but less so for the maximum weight. For instance, we could have a weighting system such that for all n, there is some program of size n with weight (.999^n)/10000. We could even have a weighting system such that for all k, there is some n > k such that there is a program of length n and weight (.9999^log(log (log n) ) )/10
Do I have that correct?
PS I believe that you meant “monotonic”, rather than “monotonous” :)
The limit is >=1 if it exists, but it doesn’t have to exist. And the lim inf can be arbitrarily close to zero.
Ditto.