Learning how to effectively program complex biochemical systems may one day enable the creation of such engineering marvels as houses that grow from a seed, nanoscale robots that recycle trash by decomposing it into reusable components, and molecular automata that seek out and destroy cancerous cells. The young field of Molecular Programming believes that computer-theoretic abstractions will prove invaluable for understanding and controlling complex chemical and biological systems.
I give an overview of the "Computer Science" of Molecular Programming, focusing on algorithmic self-assembly and formalized chemical reaction networks. Algorithmic self-assembly abstracts the process of crystallization and relates it to Wang tiling. I will describe the connection between the minimal number of types of tiles that assemble into a shape and the shape's Kolmogorov complexity. In formalized chemical reactions, molecules change state upon interacting with each other in a well-mixed solution. I will cover some decidability/undecidability results, a surprising connection to primitive recursive functions, the computational complexity of computing reachability, and other questions.