Finite State Machines and Turing Universal Computation in Cells

View all posters

Kevin Oishi, Eric Klavins

University of Washington, United States

Stages of cell differentiation are often illustrated as a sequence of events and chemical cues that move a cell from one state to another. Differentiated cells send and receive signals to compute functions on their environments and perform complex tasks such as pattern formation. Commonly used models of development in multicelled organisms are consistent with finite state machines as a natural language to specify and program multicelled behaviors. Consider a set of tools such as a library of customizable transcription factors, a collection of small molecules that can diffuse through cell walls, and programmable chemical kinetics. How is a multicellular behavior such as leader election, stripe formation, branching, or microcolony edge detection specified and compiled into a gene regulatory network? Here, we present a design method for implementing arbitrary finite state machines with gene regulatory networks. Adding to this result, we observe that coupling an implementation of finite state machines with growth, division, and cell-cell communication, a heterogeneous microcolony can implement Turing universal computation. When modeled as a Boolean network, gene regulatory networks composed only of constitutively expressed repressing transcription factors are sufficient to implement any finite state machine. We demonstrate this approach in simulation in gro (Jang, Oishi, Egbert, and Klavins, 2012) with leader election and microcolony edge detection examples, and finally with the automatic construction of a gene regulatory network that implements pattern formation as a Turing tape machine in a simulated growing microcolony.