A Constructibility Theorem for Protein-Only Turing-Complete Computation: Sequential-Head Reduction via NAND-Cooperative Networks and Protein-Templated Memory Primitives

We construct a formal computational model — the Protein Computational Substrate (PCS) — whose primitives are restricted to protein-mediated operations on a passive DNA medium. We prove two principal results: (i) any PCS satisfying five explicit axioms (NAND universality, head-local write, head-local read, unbounded tape extension, and head coherence) simulates an arbitrary Turing machine via the standard sequential-head reduction, and (ii) head coherence (A5), under a precise "independent-position" formalization of its negation, acts as a structural separator between the FSA and TM computational classes within the framework — relaxing A5 in this sense collapses the PCS to a finite-state automaton even when the other primitives are individually preserved. The first result is a specialization of the chemical-Turing universality lineage (Bennett 1982; Hjelmfelt–Weinberger–Ross 1991, 1992; Rothemund 1995; Magnasco 1997; Shapiro 2012; Soloveichik 2008, 2010; among others) to a strictly protein-only substrate. The second result provides, to our knowledge, one of the first explicit axiomatic separations of this kind within a biomolecular computation framework, and is consistent with the observation that prior in-cell recombinase state machines (Roquet et al. 2016; Benenson–Shapiro 2001) realize FSAs. The overall theorem is a constructibility result in the spirit of Turing's 1936 construction: it identifies a minimal set of protein-only primitives sufficient for universal computation without claiming that any extant organism realizes such a configuration. Each axiom is shown to be ingredient-consistent with known classes of proteins — the necessary component primitives are independently established (cooperative allosteric enzymes for NAND [1, 2]; the Drt3b component of the DRT3 antiphage defense system, in which a protein-templated poly(AC) DNA strand is synthesized from active-site residues of the protein itself [3], as the existence proof for protein-templated DNA write; sequence-specific DNA-binding proteins for read; DNA polymerase for tape extension) — but no claim is made that any single integrated system satisfying all five axioms simultaneously has been constructed or observed. The integration of these primitives into a single operating substrate is open and forms the central question for synthetic biology that the construction makes explicit. We separate the mathematical content of the theorem (rigorous) from the biological-instantiation question (open). The memory-primitive lemma is presented as an abstract specification, with concrete realizations deferred to companion work.