Abstract
The design and implementation of new-to-nature living systems with human-defined computing capabilities is now a routine process. Cells, such as bacteria, can be rationally modified to respond to a set of inputs and deliver outputs based on algorithmic rules that have been synthetically encoded into their genomes; and the resulting cellular computers are used in various domains, ranging from medical to environmental. With the era of synthetic biology, the last 20 years have seen tremendous advancements in molecular biology and microbiology, allowing us to engineer living systems with unprecedented precision. But while combinatorial functions are currently the main focus of programming living cells, biological systems have so much more to offer. It is now the time to explore, characterize, and exploit the full computing power of living systems. How do they handle stateful computations? What classes of problems can they solve? What is the complexity of gene regulation and evolution as problem-solving processes? These (non-trivial) questions, and many more, demand more attention from the computer science community. This article advocates for leveraging the synergies between theoretical computer science and synthetic biology to create more powerful cellular computers and move beyond conventional Turing computation. The limits of what can be computed with synthetic biological systems are still being explored.