How do computers compute?

Question

This is a kind of follow-up to a question I asked on superuser, where I asked for the definitions of a 'distinghuisable state' and a 'memory cell'. My questions where properly answered, but I was still confused about a certain matter.

I'm reading this little paper, and in particular these sentences:

To perform useful computation, we need to irreversibly change distinguishable states of memory cell(s) .... So the energy required to write information into one binary memory bit is $E_{bit}= k_BT \ln2$

So my interpretation of this is that the author says that to compute, you need to change the state of bits ($ 0 \rightarrow 1$, $1 \rightarrow 0$) in order to compute.

But is that actually a reasonable statement? I'm not really interested in the rest of the paper, only this part. Do computers (I'm not talking about supercomputers, or future computers which use qubits and whatnot, but just your average computer) compute using bits with 2 dinstinghuisable states?

I actually was able to find this so-called 'SNL-expression' somewhere else, namely this pdf, on page 223; it's actually a part of MIT's ocw.

Answer 1

I'm not entirely sure if I understood the question the way it was intended, but what computers do is that they operate on electricity, so they don't have two discrete logical values $0$ and $1$ per se. What they do have is electricity with voltage, and they are made to operate as if there were two logical values $0$ and $1$ if the voltage at a gate is below a certain threshold (for $0$; for example, below 0.5mV) or above another threshold (for $1$, for example, above 2.5mV) with a reasonable distance between those two threshold values. Anything in between will give the processor undefined behaviour.

What processors then do is operate on the logical values $0$ and $1$ that were abstracted from the continuous voltages. The hardware implements functions using boolean logic, meaning functions of the kind $\{0,1\}^n \to \{0,1\}^m$. For an introduction to how these things are implemented in hardware, see for example the material found here. It starts out with boolean logic, and by chapter 4 p. 3 everything needed to build an adder (meaning a circuit that implements addition) has been explained. It's a total of 23 pages to read until then, so you can decide if you would like to spend the hour or two it takes to read through it (and another hour to reread for understanding).

The circuits that don't have a way to store values are called combinational circuits, and those are used to implement the most basic functions in hardware (for example, addition, multiplication, logical operations like OR, AND, XOR for binary vectors). Circuits that can store values are called sequential circuits, and they utilize techniques where the input of gates are interdependent, and the circuits have well defined stable states. For an introduction to that, see for example here. Don' be disappointed if you can't quickly grasp that - I for one had a bit of trouble with comprehending sequential circuits initially.

For a small summary on how circuits are built from the elemental building blocks called transistors, see for example here. It only summarizes the working of transistors without all the electromechanics that go into it. Basically a transistor has a source (input) where we can apply a voltage, a gate where we can apply a voltage to control whether the input is inverted or not, and a drain (output). Depending on what type of transistor we use, the gate allows transmission from source to drain if we apply a $0$ (for nMOS transistors) or a $1$ (for pMOS transistors) to the gate.

Note that all of this is actually not computer science related, it's electrical engineering. If you would like to find out more about circuits in depth, I would advise you to ask on electronics.SE.

Answer 2

I suggest you start by reading about reversible computing. In principle, if we could make sure that all of our computations were reversible, we could circumvent that physical limit. In principle, all computations can be made reversible by keeping track of extra information about the inputs or the states the computation went through.

In practice, there's a problem: to make computation reversible, we have to keep around extra useless garbage bits that exist only to enable reversibility. The more computation we do, the more these bits accumulate. Eventually, you're going to want to erase those bits (or somehow avoid storing them forever). At that point, you're going to incur the thermal cost, so we're back to a need to make irreversible changes, with the corresponding unavoidable energy costs.

There's a lot more one can say about this, and a lot of sophisticated thinking about the subject. I'm just scratching the surface, but the key phrase "reversible computing" should be enough to help you find additional literature and research and writing on this topic.

All of this is highly theoretical right now, as modern computing technology consumes much more power than the the lower bounds suggested by physics. At this point, the main barrier to reducing energy computation is engineering, not fundamental physical barriers. But you could imagine that if the engineering advances far enough, eventually (someday) the barrier to reducing energy costs further might be these sorts of physical limits.