Search

Recent research into analog computing has introduced new notions of computing real numbers. Huang, Klinge, Lathrop, Li, and Lutz defined a notion of computing real numbers in real-time with chemical reaction networks (CRNs), introducing the classes $\mathbb{R}_\text{LCRN}$ (the class of all Lyapunov CRN-computable real numbers) and $\mathbb{R}_\text{RTCRN}$ (the class of all real-time CRN-computable numbers). In their paper, they show the inclusion of the real algebraic numbers $ALG \subseteq \mathbb{R}_\text{LCRN} \subseteq \mathbb{R}_\text{RTCRN}$ and that $ALG \subsetneqq \mathbb{R}_\text{RTCRN}$ but leave open where the inclusion is proper. In this paper, we resolve this open problem and show $ALG= \mathbb{R}_\text{LCRN} \subsetneqq \mathbb{R}_\text{RTCRN}$. However, their definition of real-time computation is fragile in the sense that it is sensitive to perturbations in initial conditions. To resolve this flaw, we further require a CRN to withstand these perturbations. In doing so, we arrive at a discrete model of memory. This approach has several benefits. First, a bounded CRN may compute values approximately in finite time. Second, a CRN can tolerate small perturbations of its species' concentrations. Third, taking a measurement of a CRN's state only requires precision proportional to the exactness of these approximations. Lastly, if a CRN requires only finite memory, this model and Turing machines are equivalent under real-time simulations., Comment: 15 pages, 1 figure

Electrical engineering and molecular programming share many of the same mathematical foundations. In this paper, we show how to send multiple signals through a single pair of chemical species using modulation and demodulation techniques found in electrical engineering. Key to our construction, we provide chemical implementations of classical linear band-pass and low-pass filters with induced differential equations that are identical to their electrical engineering counterparts. We show how to modulate \emph{arbitrary} independent input signals with different carrier frequencies for transmission through a shared medium. Specific signals in the medium can then be isolated and demodulated using band-pass and low-pass filters. Such programmable chemical band-pass filters also offer a way to monitor chemical systems to verify that they are operating between a prescribed set of frequencies.

We introduce a new motif for constructing robust digital logic circuits using input/output chemical reaction networks. These chemical circuits robustly handle perturbations in input signals, initial concentrations, rate constants, and measurements. In particular, we show that all combinatorial circuits and several sequential circuits enjoy this robustness. Our results complement existing literature in the following three ways: (1) our logic gates read their inputs catalytically which make `fanout' gates unnecessary; (2) formal requirements and rigorous proofs of satisfaction are provided for each circuit; and (3) robustness of every circuit is closed under modular composition.

We explore the class of real numbers that are computed in real time by deterministic chemical reaction networks that are integral in the sense that all their reaction rate constants are positive integers. We say that such a reaction network computes a real number $\alpha$ in real time if it has a designated species $X$ such that, when all species concentrations are set to zero at time $t = 0$, the concentration $x(t)$ of $X$ is within $2^{-t}$ of $|{\alpha}|$ at all times $t \ge 1$, and the concentrations of all other species are bounded. We show that every algebraic number and some transcendental numbers are real time computable by chemical reaction networks in this sense. We discuss possible implications of this for the 1965 Hartmanis-Stearns conjecture, which says that no irrational algebraic number is real time computable by a Turing machine.

Watchdog timers are devices that are commonly used to monitor the health of safety-critical hardware and software systems. Their primary function is to raise an alarm if the monitored systems fail to emit periodic "heartbeats" that signal their well-being. In this paper we design and verify a molecular watchdog timer for monitoring the health of programmed molecular nanosystems. This raises new challenges because our molecular watchdog timer and the system that it monitors both operate in the probabilistic environment of chemical kinetics, where many failures are certain to occur and it is especially hard to detect the absence of a signal. Our molecular watchdog timer is the result of an incremental design process that uses goal-oriented requirements engineering, simulation, stochastic analysis, and software verification tools. We demonstrate the molecular watchdog's functionality by having it monitor a molecular oscillator. Both the molecular watchdog timer and the oscillator are implemented as chemical reaction networks, which are the current programming language of choice for many molecular programming applications.

We present a uniform method for translating an arbitrary nondeterministic finite automaton (NFA) into a deterministic mass action input/output chemical reaction network (I/O CRN) that simulates it. The I/O CRN receives its input as a continuous time signal consisting of concentrations of chemical species that vary to represent the NFA's input string in a natural way. The I/O CRN exploits the inherent parallelism of chemical kinetics to simulate the NFA in real time with a number of chemical species that is linear in the size of the NFA. We prove that the simulation is correct and that it is robust with respect to perturbations of the input signal, the initial concentrations of species, the output (decision), and the rate constants of the reactions of the I/O CRN.