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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Computability of Real Functions with Oracle Pointer Machines Implies Real-Time Simulation of Chemical Reaction Networks

  • Saptarshi Biswas

摘要

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.