Reminiscent of the old joke where the physicist says "let's assume the horse is a sphere." But while a sphere might be a good model for a horse, it's definitely not a good model for how actual computers currently work.
In other words, the "actual" in the title should be replaced with "theoretical", with a footnote saying "under a theory that is worse than the one you are already using." Of course, nobody would read it then.
While a valid observation, there are other physical limits which affect the analysis. For example, assuming constant density and ever increasing sizes (which it does), at some point the computing machine will turn into a black hole. With DNA storage, the density is about that of water and the maximum storage size will be about 10E8 solar masses or about 6 AU. This is a sphere about 50 light minutes in radius, though of course the gravity well will be seriously distorted by this point and the system will need some added reinforcements to handle the rather immense pressures involved.
Any model which assumes constant density will be subject to the same absolute limit, so Ω notation doesn't apply. There is also an upper limit in information density, due to quantum mechanics.
Two other factors apply. Landauer's principle places a lower theoretical limit of energy consumption of a computation. The digital logic to look up something of index N requires at least log2(N) bits of logic for the addressing. You have to cool this off somehow, and the Stefan-Boltzmann law places a limit on how much you can cool in a vacuum. The only resolution is to slow down the system. That might place a higher constraint on the time analysis.
EDIT: Oops! Quite the other way around. The energy needed to keep the entire system warm, despite S-B cooling, will be a limiting factor. Someone else will need to do the full analysis.
And secondly, this assumes there's no need for error handling. As the address size increases, the error rate per address increases exponentially. This requires more space and more heat in order to bring the error rate down to an acceptable threshold. I don't know how to factor that in.
Therefore, instead of worrying about complex physical constraints which are not relevant to just about any computing issue, algorithms analysis uses a specific RAM model, like the trans-dichotomous model.
2 comments
[ 2.8 ms ] story [ 14.0 ms ] threadIn other words, the "actual" in the title should be replaced with "theoretical", with a footnote saying "under a theory that is worse than the one you are already using." Of course, nobody would read it then.
Any model which assumes constant density will be subject to the same absolute limit, so Ω notation doesn't apply. There is also an upper limit in information density, due to quantum mechanics.
Two other factors apply. Landauer's principle places a lower theoretical limit of energy consumption of a computation. The digital logic to look up something of index N requires at least log2(N) bits of logic for the addressing. You have to cool this off somehow, and the Stefan-Boltzmann law places a limit on how much you can cool in a vacuum. The only resolution is to slow down the system. That might place a higher constraint on the time analysis.
EDIT: Oops! Quite the other way around. The energy needed to keep the entire system warm, despite S-B cooling, will be a limiting factor. Someone else will need to do the full analysis.
And secondly, this assumes there's no need for error handling. As the address size increases, the error rate per address increases exponentially. This requires more space and more heat in order to bring the error rate down to an acceptable threshold. I don't know how to factor that in.
Therefore, instead of worrying about complex physical constraints which are not relevant to just about any computing issue, algorithms analysis uses a specific RAM model, like the trans-dichotomous model.