Logically (and therefore thermodynamically) reversible. By Landauer's principle, the only reason a computer must emit heat (and therefore use energy) is to perform irreversible operations. Therefore, if you want a computer that (potentially) uses the minimum energy, it needs to be reversible in this sense.

An irreversible operation is anything that maps many (possible) states to the same state. Setting a bit to zero is irreversible (because it destroys the information about what bit was there previously). An AND gate is irreversible (because both TF and FT map to F). A NOT gate is reversible (because you can infer the input from the output.)

There are universal reversible gates (Toffoli and Fredkin gates are examples, but there are many others), so you can (theoretically) build a (usable) computer whose logical operations are completely reversible.

Does this imply that physical entropy and informational entropy are the same?

Does it imply the computer would not give off heat? Or that a significant amount of the heat generated by a computer is due to information loss?

>Does this imply that physical entropy and informational entropy are the same?

It does, and there is a very strong (but not universally accepted) case that they are the same thing: https://en.wikipedia.org/wiki/Entropy_in_thermodynamics_and_...

Great lay article about it: http://lesswrong.com/lw/o5/the_second_law_of_thermodynamics_...

(Side note: I've long thought you can derive Carnot efficiency based on information-theoretic arguments about the information contained in knowing only the temperature difference between a heat source and a sink.)

>Does it imply the computer would not give off heat? Or that a significant amount of the heat generated by a computer is due to information loss?

Basically, yes. You can't avoid the heat emission from setting a 0 to a 1 on that computer's storage medium, but you would avoid the loss from any of the intermediate computations that typically make CPUs so hot.

I'm not the person who was asking, but thanks for the insightful comments. Makes sense.

Wouldn't a reversible computer that executes need to take up an exponentially large amount of physical space as it executes?

That might work for small problems but it doesn't seem like it would scale. Or rather, it would scale to fill the known universe.

Sorry I haven't really dug into the attached articles yet, but I will.

See the thread about the asymptotic penalties: https://news.ycombinator.com/item?id=14151390

> Does it imply the computer would not give off heat?

The implication goes the other way: if the computer does not give off heat, it must be reversible.

So, in a sense, heat is unrecoverable information.

In some sense that seems to be true.

But I just meant that while it's easy to make a reversible circuit, no tech we have today can make it as energy efficient as might be theoretically possible.

"Reversible" means that the physical processes which implement the computation (e.g. electricity flowing through wires, marbles running down tracks, etc.) can all be run backwards as well as forwards.

Think about pumping water up a hill: we have to spend energy to move it up; but it's reversible: by moving the water back down we receive energy (e.g. hydroelectric). This isn't completely reversible, since we lose a lot of energy to friction and turbulence that we can't get back. Some microscopic systems don't have such losses, e.g. gas molecules will bounce around without losing energy (gases don't spontaneously cool down). Could we use such microscopic systems to implement a computer?

From the computational side, the only logical operation which is irreversible is discarding information, e.g. overwriting some stored value with a different value. As long as we have the same amount of information out as we put in, we can run a computation in reverse: calculating the input, given the output.

Most computations take a big bunch of data as input, and produce some small output (e.g. averaging a single field from a list of records). This clearly throws away information. We can adjust this calculation to be reversible, by outputting the value we want (e.g. that average) as well as a bunch of extra "junk", which encodes all of the input data that we didn't use. Given a pair of an average and some "junk", we can compute the input which gave rise to that pair.

So why do this? If our computation is reversible, we can run our computer forwards, copy out the portion of the result we care about to somewhere else, then run the computer backwards to get it back to the state it started in. This way, we've performed our computation without using up any energy. There may be a slight loss outside the computer, if we store that result by overwriting some previous value in an irreversible way; but even this energy cost depends only on the size of the value we're copying out. We can perform an arbitrarily large amount of computation, e.g. a lengthy brute force search, and as long as the portion of the output we care about (i.e. not the "junk") is small, say a single integer, we can recover almost all of the energy used by that computation.

Don't you need energy for the computer to remember where it has been?

I think the idea is that from the output state and the program used to generate it, you have the information to exactly reverse the process and get back to the original input.

In something like an AND gate, you can't do that. I output 0...what were the two inputs? {0,0}, {0,1}, or {1,0}? And electrically, in 3/4 of the cases, you've got an input being sent to ground, using the electricity when you discard the bit of information.