4 ms·
Do away with your heat dissipation problem by going to reversible computing, and you aren't restricted to surface atoms anymore. The black hole argument goes w
by DennisP 15y ago
Do away with your heat dissipation problem by going to reversible computing, and you aren't restricted to surface atoms anymore.
The black hole argument goes way beyond that, though. It's the ultimate physical limit of the universe, rather than what's potentially practical or imaginable. Even a computer built of neutronium might not reach that limit.
- IsTom 15y agoLong live the UL-class computations!
- DennisP 15y agoI googled but didn't find anything I understood. Can you explain without giving a course in computation theory?
- IsTom 15y agoYou can think about decision problems (such that you answer "yes" or "no" to a question) as trying to find a path in (very specific) a graph. UL consists (in a hand-waving fashion) of problems that can be stated in such way by undirected graphs of polynomial size. Roughly it means "if I'm in state s and can go to s' I can also go back from s' to s", which is a reversible computation -- reversible processes are not required by thermodynamics to create heat.
- bobbydavid 15y agoIn my experience, UL is "unambiguous log", decision problems that require no more than logarithmic space, and also have a single unique proof (if it exists). It seems like UL-computers would be optimized for finding the path through the maze to the cheese, but log space is a pretty severe restriction...
- IsTom 15y agoUndirected st-connectivity is UL complete (and by showing that it's in L it was shown that UL = L). Logarithmic space is just an arbitrary constraint. It could be polynomial or exp-space.
- bobbydavid 15y agoCould you explain a bit more about the black hole argument?
- DennisP 15y agoWish I could, I don't really know any more than what Steuard posted. Perhaps he could expand on it a bit, if he sees this.
- Steuard 15y agoHere's some napkin math on the black hole argument. Information is essentially equivalent to entropy: the entropy S = k * log M, where k is Boltzmann's constant and log M is the number of bits encoding the information. Now, it turns out to be fundamentally impossible to store more entropy in any region of space than would be contained in a black hole of the same size: S_max = (k A c^3)/(4 G hbar), where A is the "surface area" of the region, c is the speed of light, G is Newton's gravitational constant, and hbar is Planck's constant. That means the maximum number of bits of information in a region of space is (A c^3)/(4 G hbar), or about A * (10^69 1/m^2). Our solar system is maybe 1 light year in size: about 10^16 m, so its "surface area" is 4pi r^2 ~ 10^33 m^2. That means that the solar system can hold at most 10^102 bits of information. If Moore's law says that computer memory doubles in capacity every 2 years, then they'll go up by a factor of 1000 about every 20 years. We currently have computers that hold about 10^12 bits of information, so just 90*20 = 1800 years would get up to that absolute limit, regardless of what technology we used, unless our single computer was bigger than a light year in radius.
- deleted 15y ago[deleted]
- Steuard 15y agoWhoops! I had a feeling I was being careless at the end there. It should have been 30x20 years rather than 90x20, so just 600 years until Moore's law is absolutely finished regardless of technology. (That shouldn't feel all that much closer, but it does.)