Compiling Ordinary (Discrete) Algorithms to Ordinary Differential Equations

David Soloveichik, University of Texas at Austin (Principal Investigator)

Sarfraz Khurshid, University of Texas at Austin (Co-Investigator)

David Doty, University of California, Davis (Co-Investigator) 

Analog computation could surpass digital computation in terms of energy usage, number of parts needed, and parallelism, and is particularly relevant in domains where some numerical error is tolerable (like artificial intelligence or synthetic biology). Importantly, analog computation is uniquely compatible with non-electronic computing hardware such as chemistry. State of the art work in synthetic biology can program a dozen Boolean logic gates in a cell, but the space of meaningful computations with so few Boolean gates is limited. On the other hand, a dozen analog components such as integrators, which can be constructed with similar complexity, can realize much more complex functionalities. We envision applications in environments where electronic microcontrollers cannot go: into a cell, or in vitro biochemical systems such as for controlling molecular self-assembly, or DNA data storage.

Given the history of analog computation dating back to mechanical “differential analyzers”, there are systematic methods to implement ordinary differential equations (ODEs) in mechanics and electronics, and more recently for chemical reaction networks. ODEs are naturally useful for simulations of existing dynamical systems (the emphasis of differential analyzers was on physics simulations). However, ODEs can also execute algorithms more commonly associated with digital electronics, which is the focus of this proposal.

Here we are proposing to create novel strategies for embedding complex algorithmic behavior in analog computation. In particular, these strategies focus on: (1) converting “loop invariants” commonly used in discrete algorithms to analog computation, and (2) programming behavior by specifying an energy function to be minimized. To make these strategies effective, new declarative programming constructs will be developed. Our goal language will allow creating powerful and provably correct ODE modules for analog computation via easy-to-specify high-level goals.

Advances in synthetic biology, DNA nanotechnology, and other related fields allow the engineering of molecules that behave according to programmable rules. Rather than shoehorning existing computational techniques, we seek to develop a novel understanding of “chemical algorithms,” which is likely to include a new appreciation of analog computation.