A unicellular walker controlled by a microtubule-based finite state machine*

10. Cells are complex biochemical systems whose behavior emerges from interactions among myriad molecular components. Computation is often invoked as a general framework for navigating this cellular complexity. However, the manner in which cells might embody computational processes such that theories of computation, including finite state machine models, could be productively applied, remains to be seen. Here we demonstrate finite state machine-like processing embodied in cells using the walking behavior of Euplotes eurystomus, a ciliate that walks across surfaces using fourteen motile appendages (cirri). We found that cellular walking entails highly regulated transitions between a discrete set of gait states. The set of observed transitions decomposes into a small group of high-probability, temporally irreversible transitions forming a cycle and a large group of low-probability time-symmetric transitions, thus revealing stereotypy in sequential patterns of state transitions. Taken together, these findings implicate a finite state machine-like process. Cirri are connected by microtubule bundles (fibers), and we found that the dynamics of cirri involved in different state transitions are associated with the structure of the fiber system. Perturbative experiments revealed that the fibers mediate gait coordination, suggesting a mechanical basis of gait control.