Oracle Pointer Machines for Simulating Chemical Reaction Network

This talk discusses the computational power of Oracle Storage Modification Machines (OSMM) in comparison to Deterministic Chemical Reaction Networks (CRN), particularly in the context of computing algebraic irrational and transcendental numbers in real time. Building on foundational results—Hartmanis and Stearns conjecture on the limitations of Turing Machines (1965), Brent’s use of Newton’s method (1976), and Schönhage’s optimization of multiplication via SMMs (1979)—this work introduces OSMMs as a more efficient alternative to the Oracle Turing Machine model proposed by Ko and Friedman in 1982. Sequential and Parallel OSMM variants are presented, offering sparse and dense computation frameworks respectively. These models compute real functions 𝑓 ∈ 𝐶[0,1], with a modulus of continuity 𝑚(𝑛), in 𝑂(𝑛 + log (𝑚(𝑛))) operations, improving upon previous bounds. Furthermore, OSMMs simulate RealTime CRNs (RTCRNs), determining species concentration trajectories in 𝑂(𝑡) operations, where 𝑡 is a time-related precision parameter. This implies that OSMMs can compute any number an RTCRN can, in linear time.

The talk concludes with future directions, including the exploration of reverse simulation, where CRNs simulate SMMs, and the broader implications for reversible computing. These avenues aim to deepen our understanding of analog-digital computational equivalence and open new pathways for exploring efficient real-time computation.

Committee: Dr. Jack Lutz (major professor), Dr. James Lathrop, Dr. Rana Parshad, Dr. Samik Basu, and Dr. Ruoyu Wu