2009-01-07 / 17:55 /

Conservative logic is a comprehensive model of computation which explicitly reflects a number of fundamental principles of physics…

Edward Fredkin and Tommaso Toffoli, Conservative Logic p. 1

Axioms for computation that are based on noninvertible primitives can only reflect aspects of macroscopic physics. While they offer enough expressive power for dealing in a formal way with what can eventually be computed by any physical means, they may deprive us of essential tools for discussing how best to compute in particular, whether and how the kT barrier can be overcome-since many relevant aspects of microscopic physics are totally out of their reach. To remedy these eficiencies, the axioms of computation must be told some of the “facts of life” of the microscopic world. This is one of the goals of conservative logic.

Edward Fredkin and Tommaso Toffoli, Conservative Logic p. 3

Via the LtU Inspiring papers thread comes Fredkin and Toffoli’s 2001 paper: Conservative Logic [PDF] (local cache since I couldn’t find an official site with a download; thanks to Strange Paths for having a copy of the PDF). The paper 1) presents a model of computation based on physics-inspired axioms, 2) demonstrates that the model is computationally universal and then 3) gives an example implemented using billiard balls. Well, technically perfectly elastic collisions of spherical bodies constrained to a 2-dimensional plane, but still fun.

It reminded me of Neil Gershenfeld‘s Programming Bits and Atoms talk. Specifically both changed my concepts of computation: Gershenfeld shows a bunch of examples of asynchronous logic automata (sorry for the crap link to a google index, I haven’t read enough to find a good reference; let me know if you find one) and also demonstrates physical logic gates built from plastic tubing and air bubbles. Given that Toffoli was cranking out papers in the late 70’s, I wouldn’t be surprised if Gershenfeld draws from his work.

Beyond the cool factor, both works have practical outcomes. Gershenfeld shows proof of concepts like the “paintable computer”: a computational surface that runs a Postscript interpreter. He also demonstrates a(nother) linear-time sorting algorithm that depends on the ALA property that transmission is also storage (cells store values, transmission is merely the passing of values down a chain of cells). Fredkin and Toffoli make no such claims, but since a primitive of Conservative Logic is the unit wire–an element that both stores and transmits a value–the same should hold.

Fredkin and Toffoli’s emphasis on conservative physics principles leads to another huge benefit: “The central result of conservative logic is that it is ideally possible to build sequential circuits with zero internal power dissipation.” Nice.

But, really, my interest is in the combination of computer nerdery with physics nerdery (I spent years doing integrals studying physics). This is the stuff inspires me when I feel like a programming career is nothing more than CRUD web interfaces; you might even say reading these papers prevents my architecture from sucking.

In a similar vein, I recommend The Feynman Lectures on Computation and Scott Aaronson’s blog. Aaronson’s blog is a cornucopia of technical things I don’t fully understand, including one of my favorite blog posts of 2008: Time: Different from space.