Chemical Reaction Networks: Computability, Complextiy, and Randomness
In this thesis we study the computational power of chemical reaction networks (CRNs), under both the deterministic and stochastic semantics of the model. We explore the class of real numbers that are computed in real time by deterministic CRNs. We develop the elements of the theory of algorithmic randomness in continuous-time Markov chains with the aim of applying to stochastic CRNs, which are essentially special cases of CTMCs.
We first introduce the notion of computing a real number in real time. We show that every algebraic number is computable by chemical reaction networks in real time. We also show the real-time equivalent of CRNs and general purpose analog computers (GPACs), which are seemingly more powerful that CRNs. As a by-product of this fact, we give simple and natural constructions for some famous transcendental numbers.
Next we extend the above work to population protocols. We generalize the notion of numbers computed by large population protocols (LLPs) (Bournez, Fraigniaud, and Koegler, 2012). They proved that large population protocols can only compute exactly the algebraic numbers. However, their definition comes with an extra restriction: the systems must have finitely many fixed points. We relax the finitary restriction and show that we can now compute transcendental numbers.
Our last work is on algorithmic randomness in continuous-time Markov chains. We first define the randomness of trajectories in terms of a new kind of martingale (algorithmic betting strategy). After that we prove equivalent characterizations in terms of constructive measure theory and Kolmogorov complexity. As a preliminary application we prove that, in any stochastic chemical reaction network, every random trajectory with bounded molecular counts has the non-Zeno property that infinitely many reactions do not occur in any finite interval of time.
Committee: Jack Lutz (major professor), Pavan Aduri, Soma Chaudhuri, David Fernandez-Baca, James Lathrop, Timothy McNicholl