Computing and memory in living cells are central to encoding next-generation therapies and studying in situ biology, but existing strategies have limited encoding capacity and are challenging to scale. To overcome this bottleneck, we developed a highly scalable, robust and compact platform for encoding logic and memory operations in living bacterial and human cells. This platform, named DOMINO for DNA-based Ordered Memory and Iteration Network Operator, converts DNA in living cells into an addressable, readable, and writable computation and storage medium via a single-nucleotide resolution read-write head that enables dynamic and highly efficient DNA manipulation. We demonstrate that the order and combination of DNA writing events can be programmed by biological cues and multiple molecular recorders can be coordinated to encode a wide range of order-independent, sequential, and temporal logic and memory operations. Furthermore, we show that these operators can be used to perform both digital and analog computation, and record signaling dynamics and cellular states in a long-term, autonomous, and minimally disruptive fashion. Finally, we show that the platform can be functionalized with gene regulatory modules and interfaced with cellular circuits to continuously monitor cellular phenotypes and engineer gene circuits with artificial learning capacities. We envision that highly scalable, compact, and modular DOMINO operators will lay the foundation for building robust and sophisticated synthetic gene circuits for numerous biotechnological and biomedical applications.