Computability of Real Functions with Oracle Pointer Machines Implies Real-Time Simulation of Chemical Reaction Networks
摘要
According to Hartmanis and Stearns conjecture (1965), algebraic irrational numbers cannot be computed by a Turing Machine (TM) in real-time (O(n)). Brent (1976) demonstrated that Newton’s method can find the square root of a floating-point number in O(M(n)) operations, with M(n) being cost of multiplying two n-bit integers. Further, Schönhage (1979) showed that a Storage Modification Machine (SMM) can reduce the cost of multiplication to O(n) operations, implying real-time computability of square-roots. In 2018, Huang et al. proved that a Deterministic Chemical Reaction Network (analog computation) could compute all algebraic irrational numbers in real-time. In this regard, this work explores the relationship between these two computing models. To answer this question, this work introduces the concept of Oracle SMM, which computes real functions more efficiently than the Oracle TM model established by Ko and Friedman (1982). In contrast to their results, this work shows that a real function \(f\in \mathcal {C}[0,1]\) , with the modulus of continuity \( m(n) \) , can be computed by an oracle SMM in \(O(\lceil \log (m(n))\rceil )\) rather than \( O(n+1)+O(m(n+1)) \) operations, where \( n \) represents the precision parameter. The proposed model further simulates any real-time CRN, i.e., find trajectory points of species concentration in O(t) many operations, where t defines the precision parameter proportional to time. As a result, this work implies that an Oracle SMM in O(t) operations can compute any algebraic irrational or transcendental number that a real-time CRN computes to a precision of t-bits.