Abstract
Finite-state automata (FSA) are simple computational devices that can nevertheless illustrate interesting behaviours. We propose that FSA can be employed as control circuits for engineered stochastic biological and biomolecular systems. We present an implementation of FSA using counts of chemical species in the range of hundreds to thousands, which is relevant for the counts of many key molecules such as mRNAs in prokaryotic cells. The challenge here is to ensure a robust representation of the current state in the face of stochastic noise. We achieve this by using a multistable approximate majority algorithm to stabilize and store the current state of the system. Arbitrary finite state machines can thus be compiled into robust stochastic chemical automata. We present two variants: one that consumes its input signals to initiate state transitions and one that does not. We characterize the state change dynamics of these systems and demonstrate their application to solve the four-bit binary square root problem. Our work lays the foundation for the use of chemical automata as control circuits in bioengineered systems and biorobotics.