Re:Physical Limits to Computation (2000) [pdf]
by amelius on Monday June 01, 2015 @07:29AM
(#9637815)
So after 2^(2^35) steps my computer has certainly finished its computation. The state it is now in can be described by 0 bits of information, a priori. The question is, how is this useful in any way? :)
Re:Physical Limits to Computation (2000) [pdf]
by lisper on Monday June 01, 2015 @10:30AM
(#9638792)
You're missing the point, which is that a physical computer in this universe could enumerate no more than 2^500 distinct states. How is this useful? Well, for example, it lets you put hard upper bounds on the size of crpyto keys. For symmetric crypto, assuming your algorithm is a CSPRNG, you will never need a key larger than 512 bits no matter how advanced computer technology gets.
Re:Physical Limits to Computation (2000) [pdf]
by amelius on Monday June 01, 2015 @05:14PM
(#9642204)
Is that true? Cracking a key is a highly parallellizable operation, where little communication is needed between processors. Would your statement still hold here?
Re:Physical Limits to Computation (2000) [pdf]
by lisper on Monday June 01, 2015 @05:29PM
(#9642296)
Yes. Just look at the details of the calculation. It makes very (very!) liberal assumptions, and produces a very loose upper bound, i.e. 2^500 is almost certainly a gross overestimate of what is actually achievable even given arbitrarily advanced technology. The point here is that even a very loose upper bound is still quite small.
Nope. It seemed like too trivial a result to try to publish it (though maybe someone has -- I don't know).
> the observable universe is in one of at least 2^X possible states
That's right, but it completely misses the point. Yes, your computer has 2^(2^35) possible (maybe "potential" would be a less misleading term) states, but the number of states that it will ever actually be in is bounded by the number of clock cycles the computer undergoes during its lifetime. If your computer runs at 1 GHz continuously for 10 years, it will have been in at most ~10^17 = 2^56 states. In the lifetime of the universe, your computer will only ever be in a tiny tiny fraction of its potential states.