State machines are used as computing devices that integrate input signals and respond with a context-dependent output. Each output represents one possible “state” in which the machine can exist. State machines are order dependent, meaning that the sequential state depends on both the input and the current state. State machines can exist in cells, whereby synthetic gene networks drive the transition between cellular states in an input- and state-dependent manner. This E. coli-based system produces unique gene expression patterns that define the cellular “state” in response to chemical inducer inputs. Both the identity and order of inducers matter, making it possible to distinguish between ‘Input A then Input B’ and ‘Input B then Input A.’ The chemical inducers manipulate the state of the cell by driving the expression of recombinases, which invert or excise sections of DNA (e.g., promoters, terminators, and output genes) based on the orientation of recognition sites. Modulating the assembly of the targeted gene circuit components enables complex and varied states. The gene circuit assembly is modular and can be achieved in one step. In contrast to conditional gene expression methods that require constant induction (e.g., those based on transcription), this system maintains a stable memory even after inputs are withdrawn. Thus, cells need only transient induction in order to be locked into a state, allowing for the implementation of sequential inputs and the interrogation of long-term cellular history.