Strong Turing Completeness of Continuous Chemical Reaction Networks and Compilation of Mixed Analog-Digital Programs

Abstract : When seeking to understand how computation is carried out in the cell to maintain itself in its environment, process signals and make decisions, the continuous nature of protein interaction processes forces us to consider also analog computation models and mixed analog-digital computation programs. However, recent results in the theory of analog computability and complexity establish fundamental links with classical programming. In this paper, we derive from these results the strong (uniform computability) Turing completeness of chemical reaction networks over a finite set of molecular species under the differential semantics , solving a long standing open problem. Furthermore we derive from the proof a compiler of mathematical functions into elementary chemical reactions. We illustrate the reaction code generated by our compiler on trigonometric functions, and on various sigmoid functions which can serve as markers of presence or absence for implementing program control instructions in the cell and imperative programs. Then we start comparing our compiler-generated circuits to the natural circuit of the MAPK signaling network, which plays the role of an analog-digital converter in the cell with a Hill type sigmoid input/output functions.
Type de document :
Communication dans un congrès
J. Feret and H. Koeppl. CMSB 2017 - 15th International Conference on Computational Methods in Systems Biology, Sep 2017, Darmstadt, Germany. Lecture Notes in Computer Science (10545), pp.108-127, Proceedings of the fiveteen international conference on Computational Methods in Systems Biology, CMSB 2017. 〈http://www.etit.tu-darmstadt.de/cmsb2017/cmsb_2/index.en.jsp〉
Liste complète des métadonnées

Littérature citée [50 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01519828
Contributeur : François Fages <>
Soumis le : mardi 29 août 2017 - 09:42:19
Dernière modification le : jeudi 12 avril 2018 - 01:48:14

Fichier

FLBP17cmsb.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01519828, version 3

Citation

François Fages, Guillaume Le Guludec, Olivier Bournez, Amaury Pouly. Strong Turing Completeness of Continuous Chemical Reaction Networks and Compilation of Mixed Analog-Digital Programs. J. Feret and H. Koeppl. CMSB 2017 - 15th International Conference on Computational Methods in Systems Biology, Sep 2017, Darmstadt, Germany. Lecture Notes in Computer Science (10545), pp.108-127, Proceedings of the fiveteen international conference on Computational Methods in Systems Biology, CMSB 2017. 〈http://www.etit.tu-darmstadt.de/cmsb2017/cmsb_2/index.en.jsp〉. 〈hal-01519828v3〉

Partager

Métriques

Consultations de la notice

340

Téléchargements de fichiers

140