Ah, gotcha. I think this is a bit different to compressibility: if you formalise it as Kolmogorov complexity, then you can have a very compressible algorithm that in fact you can’t compress given time limits, because it’s too hard to figure out how to compress it. This seems more like ‘de facto compressibility’, which might be formalised using the speed prior or a variant.
Looking back on this, the relevant notion isn’t going to be those distributions, but just plain old Kt complexity: the minimum over programs p that take time t to compute the data of len(p)+log(t).
Ah, gotcha. I think this is a bit different to compressibility: if you formalise it as Kolmogorov complexity, then you can have a very compressible algorithm that in fact you can’t compress given time limits, because it’s too hard to figure out how to compress it. This seems more like ‘de facto compressibility’, which might be formalised using the speed prior or a variant.
Looking back on this, the relevant notion isn’t going to be those distributions, but just plain old Kt complexity: the minimum over programs p that take time t to compute the data of len(p)+log(t).