Speaker:Dawn Nye

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.

Lastly, we develop a generalized version of the discrete Fourier transform. Although it shows promise for future analysis of specialized chemical reaction networks, here we use it to state a new definition of algorithmic randomness. The definition we provide is a derivative of the martingale definition provided by Schnorr. 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 a function are uniformly bounded.

Committee: James Lathrop (co-major professor), Jack Lutz (co-major professor), Pavan Aduri, Andrew Miner and Eric Weber.

Join on Zoom: https://iastate.zoom.us/j/96630001635?pwd=ZVhvRlFjQXJNVGJFRnEvckFJTkQrQ…