Practical Computation with Chemical Reaction Networks and Algorithmic Randomness
Recent research in analog computing has relied heavily on the ability to create and initialize a chemical reaction network (CRN) precisely as specified. For example, Huang, Klinge, Lathrop, Li, and Lutz defined a notion of computing real numbers in real-time with chemical reaction networks (CRNs) that is fragile in the sense that any small perturbation from its intended construction will cause it to fail. In practice, it is unrealistic to assume the infinite precision such requires. Many theorems are thus proven about the CRN model rather than the reality the model is intended to reflect. Here, we require a CRN to withstand these perturbations and explore the consequences of this restriction. In doing so, we arrive at a paradoxically discrete model of analog computation. This approach has several advantages. First, a CRN may compute values in finite time. Second, a CRN may tolerate error in its construction. Third, a measurement of a CRN's state only requires precision proportional to the exactness of the approximations. Lastly, if a CRN requires only finite memory, this model and Turing machines are equivalent under real-time simulation.
Further, we show a key limitation of a CRN's ability to compute even with exact values. We prove that no CRN, given an arbitrary real value α, can transform α into its binary expansion. This is true both exactly and in approximation of either input or output. It can, however, convert a measure one subset of [0,1) (and hence almost all real numbers) that is totally disconnected in the limit as permitted error goes to zero.
Lastly, we present a generalized version of the weighted discrete Fourier transform. In particular, we provide an orthonormal basis for the underlying product space and give the weighted discrete Fourier transform and the usual tools of Fourier analysis in terms of it. Using this generalization, we state a new characterization of algorithmic randomness. The definition we provide is a derivative of the martingale definition provided by Schnorr in terms of submartingales (martingales which are subadditive). We show that a sequence S is random if, as with a martingale, a broader class of well behaved functions cannot succeed on S. By well behaved, we mean that the Fourier coefficients we extract from such a function are uniformly bounded. As a ready derivative of this new characterization, we also provide the analogous definition of Hausdorff dimension to demonstrate its wide applicability.
Committee: James Lathrop (Major Professor), Jack Lutz (Major Professor), Pavan Aduri, Andrew Miner, Eric Weber
Join on Zoom: Zoom