License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DNA.29.9
URN: urn:nbn:de:0030-drops-187920
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18792/
Luchsinger, Austin ;
Doty, David ;
Soloveichik, David
Optimal Information Encoding in Chemical Reaction Networks
Abstract
Discrete chemical reaction networks formalize the interactions of molecular species in a well-mixed 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 Turing-universal 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 "space-aware" version of the Kolmogorov complexity of x, defined as K̃s(x) = min_p {|p|/log|p| + 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 information-theoretically optimal for incompressible information. Our work provides one answer to the question of how succinctly chemical self-organization 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:1--9:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-297-6},
ISSN = {1868-8969},
year = {2023},
volume = {276},
editor = {Chen, Ho-Lin and Evans, Constantine G.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18792},
URN = {urn:nbn:de:0030-drops-187920},
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 |
