15 April 2005
Motivated by the intriguing functionality of gene regulatory networks we study chemical reactions (biological) circuits. We observe that those circuits are vastly different when compared to existing computing structures like logic circuits. In particular, the two strikingly different ingredients in biological circuits are feedback in memoryless computation and the stochastic behavior of devices in deterministic systems. Are these two biologically inspired concepts useful in improving the design of existing computing structures? I will provide a positive answer to this question and argue that progress in our understanding of biology depends on the development of new abstractions for reasoning about computation.
M Gibson & J Bruck, "Efficient exact stochastic simulation of chemical systems with many species and many channels", Journal of Physical Chemistry A 104:1876-1889 2000. PDF
M Riedel & J Bruck, "The synthesis of cyclic combinational circuits", 40th Design Automation Conference (DAC), Anaheim, CA, June 2003 (received Best Paper Award). PDF
M Cook & J Bruck, "Implementability among predicates", manuscript 2005. PDF
M Cook, D Soloveichik, E Winfree & J Bruck, "Decidability and chemical reaction networks: only probabilistic systems are Turing universal", manuscript 2005.
current theory lunch schedule