LESSWRONG
LW

Comment Permalink

Quoting from your linked post:

Anything you can compute using an infinite amount of negentropy, time T, and space S, can be computed using only about S negentropy if you are willing to spend a little bit of extra space and time (S log T and T^1.5, for example, or S and 2^S * T). So future universes may be constrained by available space and time rather than negentropy,

I don't understand the conclusion here. It sounds like the set of potential computations we can do is a (somewhat complicated) function of available time, space, and negentropy. Given a fixed amount of time and space, we can do more computations if we had more negentropy, right? So in what sense would we not be constrained by negentropy?

paulfchristiano13y110

In general, a source of unlimited negentropy buys you only a small polynomial increase in the available time and space. So negentropy does matter, but the total amount of computation you can do is dominated by the available space and time rather than the available negentropy.

In the limit where you have exponentially more time than space (say, the universe turns out to be some arbitrary reversible bounded cellular automaton) then entropy does no good at all.

See in context

38 Negentropy Overrated?

by paulfchristiano

29th Dec 2011

1 min read

38

This post may be interesting to some LWers.

In summary: it looks like our universe can support reversible computers which don't create entropy. Reversible computers can simulate irreversible computers, with pretty mild time and space blowup. So if moral value comes from computation, negentropy probably won't be such an important resource for distant future folks, and if the universe lasts a long time we may be able to simulate astronomically long-lived civilizations (easily 10^(10^25) clock cycles, using current estimates and neglecting other obstructions).

Has this been discussed before, and/or is there some reason that it doesn't work or isn't relevant? I suspect that this consideration won't matter in the long run, but it is at least interesting and seems to significantly deflate (long-run) concerns about entropy.

Physics

Personal Blog

38

Mentioned in

6Does reversible computation let you compute the complexity class PSPACE as efficiently as normal computers compute the complexity class P?

New Comment

32 comments, sorted by

top scoring

Click to highlight new comments since: Today at 5:18 PM

[-]Wei Dai13y120

Quoting from your linked post:

Anything you can compute using an infinite amount of negentropy, time T, and space S, can be computed using only about S negentropy if you are willing to spend a little bit of extra space and time (S log T and T^1.5, for example, or S and 2^S * T). So future universes may be constrained by available space and time rather than negentropy,

[-]paulfchristiano13y110

In the limit where you have exponentially more time than space (say, the universe turns out to be some arbitrary reversible bounded cellular automaton) then entropy does no good at all.

[-]Wei Dai13y60

In the limit where you have exponentially more time than space (say, the universe turns out to be some arbitrary reversible bounded cellular automaton) then entropy does no good at all.

Ok, I see, but this assumes that once you've completed a computation, a second execution of it has no moral value, right? (Because more negentropy would allow you to drive the reversible computation forward faster and complete more executions in the same available time.)

[-]paulfchristiano13y20

Yes--if over the course of your computation you explore on a fraction X of all possible states of the computer, a supply of infinite negentropy would allow you to run the computation something like 1/X faster.

[-]JGWeissman13y70

Before discussing application to such hard problems as simulating brains, I would like to see an example of a short irreversible program, it reversible equivalent, and a trace through running each one that demonstrates the advantage of the reversible program.

[-]paulfchristiano13y100

I want to calculate f^128(X) (mod N), where f is a polynomial and f^128 is f composed with itself 128 times.

First I calculate f(X) (mod N). Now my workspace is:

X, f(X), garbage.

I copy out the f(X) to some scratch space. Now my workspace is:

X, f(X), garbage, f(X).

Now I reverse my original computation to clear the garbage.

X, 0, 0, f(X).

Now I repeat this process to compute f(f(X)).

X, f(f(X)), garbage, f(X).

Now copy out f(f(X)) and uncompute.

X, 0, 0, f(X), f(f(X)).

Now I repeat my calculation of f(X), but backwards.

X, 0, 0, 0, f(f(X)).

Now I repeat my computation of f(f(X)), but starting from f(f(X)) instead of from X.

X, 0, 0, 0, f(f(X)), f(f(f(f(X))))

Now I reverse my computation of f(f(X)):

X, 0, 0, 0, 0, f(f(f(f(X))))

And so on.

I end up with

X, 0, 0, 0, 0, 0, 0, 0, 0, 0, f^128(X).

after about 2100 steps.

I've used 11 times more memory than required to compute f. But on the flipside, I've generated no waste heat, while just applying f over and over again would have generated 128 times the waste heat required to compute f.

[-]JGWeissman13y40

1. First I calculate f(X) (mod N). Now my workspace is:

X, f(X), garbage-1.

2. I copy out the f(X) to some scratch space. Now my workspace is:

X, f(X), garbage-2, f(X).

3. Now I reverse my original computation to clear the garbage.

X, 0, 0, f(X).

Is garbage-1 the same as garbage-2? If so, how do you copy f(X) in step 2 without introducing more garbage? If not, how do you reverse the computation in step 3?

[-]paulfchristiano13y80

You can copy something reversibly (into fresh memory) without creating garbage by a using a CNOT (controlled not).

[-]Dmytry13y70

The interesting issue with reversible computation is that you do not need complete reversibility to reap nearly all the energy saving benefits of reversible computation. For example, a CPU built on perfect reversible logic, which would run normal irreversibly computing software, would still have ridiculously low energy requirements compared to today's CPUs, as most of the irreversibility happens on the very low level (think intermediate steps when adding two numbers, think loss of state of each transistor in CPU at every clock cycle) and at the level of software the number of erased bits per cycle is actually rather small. edit: and can probably be further minimized by optimizing compiler without changing behaviour of program in any way or changing it's memory requirements by more than a constant factor

[-]timtyler13y60

Has this been discussed before, and/or is there some reason that it doesn't work or isn't relevant?

I go over some of the issues here. One of the points as a taster:

However, in order to attain the supposed benefits of reversible computation, the reversible machine must actually be run backwards to attain its original state. If this step is not taken, then typically the machine becomes clogged up with digital heat i.e. entropy, and is thus rendered unable to perform further useful work.

[-]paulfchristiano13y50

I am talking about very long term applications, which (it seems?) you aren't trying to address.

For example: yes, to run a reversible computer without waste heat you need to actually uncompute intermediate results. This introduces time overhead which is generally unacceptable for real applications in the modern world, where negentropy is abundant. But what does this have to do with the long term capability of the universe for computation?

[-]timtyler13y50

Reversible computing is good news for power consumption and heat dissipation (including in the long term) - but not great news - bacause of the reasons I go over in my article.

If you think that actually running things backwards is actually an attractive answer, perhaps think some more about how you are going to correct all errors and prevent an error catastrophe upon reversal - and about how you are going to propagate the "reverse now" signal in a reversible manner.

[-]paulfchristiano13y40

perhaps think some more about how you are going to correct all errors and prevent an error catastrophe upon reversal

The normal way. This generates waste heat, but at a rate which depends on the error rate of your components. Under our current understanding of physics, this can be driven essentially to zero in the long run. Even if it can't, it can at least be driven down until we encounter some as-yet-unknown fundamental physical limitation. If we imagine people living in a reversible CA, or any other laws of physics which we can understand, then we can see how they could build an error-free computer once they had a theory of everything. Do you suspect our universe is more complicated, so that such an understanding is impossible? What do you think determines the quantitative bound on achievable error rate?

and about how you are going to propagate the "reverse now" signal in a reversible manner.

I don't understand this objection. I can write down reversible circuits which coordinate with only a constant factor penalty (it is trivial if I don't care about the constant--just CNOT in a 'reverse' bit to each gate from a central controller, and then make each gate perform its operation in reverse if the bit is set, tripling the number of gates). What fundamental non-idealness of reality are you appealing to here, that would prevent a straightforward solution?

[-]timtyler13y00

perhaps think some more about how you are going to correct all errors and prevent an error catastrophe upon reversal

The normal way. This generates waste heat, but at a rate which depends on the error rate of your components. Under our current understanding of physics, this can be driven essentially to zero in the long run.

It seems to me that with hardware error correction, you have to pay for your error rate with heat. If you want to recover your machine by running it backwards you need a very low hardware error rate - which is correspondingly expensive in terms of heat dissipation.

If we imagine people living in a reversible CA, or any other laws of physics which we can understand, then we can see how they could build an error-free computer once they had a theory of everything.

I am not clear how having a TOE will help with cosmic rays and thermal noise. Of course you can deal with thermal noise using a fridge - but then your fridge needs a power supply...

and about how you are going to propagate the "reverse now" signal in a reversible manner.

I don't understand this objection. I can write down reversible circuits which coordinate with only a constant factor penalty (it is trivial if I don't care about the constant--just CNOT in a 'reverse' bit to each gate from a central controller, and then make each gate perform its operation in reverse if the bit is set, tripling the number of gates).

Propagating a "reverse" signal through a large system and getting the components to synchronously reverse course is not exactly trivial. It's also hard to do reversibly, since the "reverse" signal itself tends to dissipate at the edges of the system. - though as you say, that's a one-off cost.

You proposed "tripling of the number of gates". Plus the machine has twice the runtime because of the "running backwards" business. Reversibility has some costs, it seems...

I am pretty sceptical about the idea that the future will see reversible computers that people will bother to run backwards. Instead, I expect that we will see more of the strategies mentioned in my article.

[-]Sniffnoy13y20

I think if you realistically want to run a reversible computer, you need to uncompute regardless, because otherwise your space is non-reusable, becoming only as useful as time.

[-]gwern13y10

This sounds right to me. Reversible computing means you can get closer to the energy limit set by Landauer's principle, but you still don't drive the negentropy cost per bit to zero.

[-]paulfchristiano13y150

You get the energy limit set by Landauer's principle without reversible computing. Reversible computing completely circumvents Landauer's principle (although there may be other limitations).

[-]gwern13y10

I don't follow. You still have to pay for erasing and changing your bits, regardless of whether you use reversible computing and do the erasure at the end, or whether you do it during the computation as in irreversible computing.

[-]paulfchristiano13y20

You generally uncompute intermediate results in reversible computation, rather than erasing them: if you produced some garbage by starting from a low entropy state and running the computation C forward, you can get rid of the garbage by just running C backwards (perhaps first copying whatever output you care about, so that it doesn't get destroyed).

[-]gwern13y20

perhaps first copying whatever output you care about, so that it doesn't get destroyed

Well, yeah. You're going to use up negentropy for that - where are you copying to? Reversible computing just means you spend less negentropy. (Feel like I've said this before.)

[-]paulfchristiano13y220

Yes, you just produce less entropy. But you produce a lot less entropy and it is completely unrelated to Landauer's principle.

Suppose I want to calculate a 1TB document created by a googol person civilization running for a googol googol years. I only have to produce a TB of entropy, not more than a googol googol googol bits (as I would have to if I used irreversible computing naively).

[-]Vladimir_Nesov13y180

Very nice! So you don't just cheaply compute-and-uncompute a lot of independent worlds, you can allow them to leave an arbitrarily-difficult-to-produce trace on the future worlds. Given how much entropy we really have, sufficiently small persons for example can be spared from uncomputation.

In particular, a person can live in an incrementally computed-and-uncomputed virtual world that is being regularly reversed to its initial state, with the effect that only the person consumes entropy, and the whole arbitrarily complicated world has zero entropic footprint. The world could also be optimized game-save-style over person-time, starting from an initial state, but going forward, so that some version of the person does all the updating, and so carries the excess entropy. Alternatively, improvements to the world could be carried out by discarded copies. Think of software downloaded from the distant future...

Or more generally, this is just time travel, where you can transport sufficiently small things (and people) to the past (or between timelines) and change things the next time over. You travel forwards in time by computing, backwards by uncomputing, you can take some luggage with you, you can climb up a different timeline by observing without interference, and you can intervene and change a timeline any time you want. The network of people navigating baseline network of virtual worlds builds up a second level (implementing meta-time), which itself can be navigated and intervened-in by other observers, and so forth. Sounds like a Greg Egan novel (that wasn't written yet).

[-]Douglas_Knight13y20

I think this article needs the terms "P" and "PSPACE": reversible computing can apply PSPACE algorithms, while normal computers are limited to P by Landauer's principle. Yes, there's nothing true in that sentence that's not already explicit in the article, but abstractions are very useful for organizing understanding.

[-]Dmytry13y10

Other thing that may be interesting to note. You can describe reversible algorithms in straight C or C++ . Instead of the assignment operator, you need to use operators ^= , += , -= which are reversible, and you would need a compiler that would be intelligent about wiping the temporary variables in the expressions by reversion of the statement. The multiplications are slightly tricky but a+=b*c can be implemented in a reversible manner.

I am a game engine programmer (with background in special effects / simulation) and it seems to me that I could easily write a neural network simulator (fairly basic) which would make use of reversible computation and would use about 4x the memory but would have a hundred million times lower power consumption for 10^14 synapses. Essentially it will only wipe as much data per step as is the input and output of conscious being, which is much smaller than the state ( assuming 1 megapixel vision and 10 000 muscles.) The exercise seems pretty trivial to me; the calculation structure would vaguely resemble a Feistel network (I drew my inspiration from it), and it would be able to run the being in reverse using some constant-size extra data that is carried along with the being, if a log of the being's original 'sensory input' is recorded.

[+]Will_Newsome13y-100

Moderation Log

32Comments