Abstract
Discrete chemical reaction networks formalize the interactions of molecular species in a wellmixed solution as stochastic events. Given their basic mathematical and physical role, the computational power of chemical reaction networks has been widely studied in the molecular programming and distributed computing communities. While for Turinguniversal systems there is a universal measure of optimal information encoding based on Kolmogorov complexity, chemical reaction networks are not Turing universal unless error and unbounded molecular counts are permitted. Nonetheless, here we show that the optimal number of reactions to generate a specific count x ∈ ℕ with probability 1 is asymptotically equal to a "spaceaware" version of the Kolmogorov complexity of x, defined as K̃s(x) = min_p {p/logp + log(space(?(p))) : ?(p) = x}, where p is a program for universal Turing machine ?. This version of Kolmogorov complexity incorporates not just the length of the shortest program for generating x, but also the space usage of that program. Probability 1 computation is captured by the standard notion of stable computation from distributed computing, but we limit our consideration to chemical reaction networks obeying a stronger constraint: they "know when they are done" in the sense that they produce a special species to indicate completion. As part of our results, we develop a module for encoding and unpacking any b bits of information via O(b/log{b}) reactions, which is informationtheoretically optimal for incompressible information. Our work provides one answer to the question of how succinctly chemical selforganization can be encoded  in the sense of generating precise molecular counts of species as the desired state.
BibTeX  Entry
@InProceedings{luchsinger_et_al:LIPIcs.DNA.29.9,
author = {Luchsinger, Austin and Doty, David and Soloveichik, David},
title = {{Optimal Information Encoding in Chemical Reaction Networks}},
booktitle = {29th International Conference on DNA Computing and Molecular Programming (DNA 29)},
pages = {9:19:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772976},
ISSN = {18688969},
year = {2023},
volume = {276},
editor = {Chen, HoLin and Evans, Constantine G.},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18792},
URN = {urn:nbn:de:0030drops187920},
doi = {10.4230/LIPIcs.DNA.29.9},
annote = {Keywords: chemical reaction networks, Kolmogorov complexity, stable computation}
}
Keywords: 

chemical reaction networks, Kolmogorov complexity, stable computation 
Collection: 

29th International Conference on DNA Computing and Molecular Programming (DNA 29) 
Issue Date: 

2023 
Date of publication: 

04.09.2023 