Real-Time Computability of Real Numbers by Chemical Reaction Networks

摘要

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 α 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 the fractional part of α at all times t ≥ 1, and the concentrations of all other species are bounded. We show that every algebraic number is 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.