News for hackers. Stuff that matters.
Re:Physical Limits to Computation (2000) [pdf] by lisper on Sunday May 31, 2015 @05:57PM (#9635725)
Yes: the speed of light. Individual particles can't interact with each other at the Planck frequency. So this model treats every particle as if it were a self-contained computer that encodes information in whatever degrees of freedom it has. Note that this model says nothing about how many bits are in each computed state. It only counts the total number of states that the universe could potentially compute. That number is ~2^500.
Re:Physical Limits to Computation (2000) [pdf] by amelius on Sunday May 31, 2015 @06:51PM (#9635920)
Do you have a reference for this?

It would seem to me that if the observable universe has X particles, and each particle has two states, then the observable universe is in one of at least 2^X possible states, since light has had the opportunity to cross from one side of the observable universe to the other (or it could be off by only a factor of two, considering that the observer is somewhere in the middle).

Or look at it from another perspective. My computer has 4GB of ram. That is 2^35 bits, and thus it has 2^(2^35) possible states (huge!) Since my computer is only a small part of the universe, the universe must have a much larger number of possible states.

Re:Physical Limits to Computation (2000) [pdf] by lisper on Monday June 01, 2015 @02:21AM (#9637021)
> Do you have a reference for this?

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.

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.