Chapter 9: Fundamental Physics

Section 2: The Notion of Reversibility

Reversible computation

Typical practical computers—and computer languages—are not even close to reversible: many inputs can lead to the same output, and there is no unique way to undo the steps of a computation. But despite early confusion (see page 1020), it has been known since at least the 1970s that there is nothing in principle which prevents computation from being reversible. And indeed—just like with the cellular automata in this section—most of the systems in Chapter 11 that exhibit universal computation can readily be made reversible with only slight overhead.

From Stephen Wolfram: A New Kind of Science [citation]