Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Turing Completeness of Elementary Reaction Systems under the Differential Semantics 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. Recent results in the theory of analog computability and complexity establish however fundamental links with classical programming. In this paper, we show the Turing completeness of systems of elementary reactions without polymerisation, under the differential semantics. We derive from this result a compiler of mathematical functions into elementary biochemical 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. On Hill functions, we compare 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 Hill type sigmoid input/output functions.
Complete list of metadata

Cited literature [38 references]  Display  Hide  Download

https://hal.inria.fr/hal-01519828
Contributor : François Fages Connect in order to contact the contributor
Submitted on : Tuesday, May 9, 2017 - 1:20:24 PM
Last modification on : Monday, August 3, 2020 - 4:48:02 PM
Long-term archiving on: : Thursday, August 10, 2017 - 1:10:17 PM

File

FLBP17cmsb.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01519828, version 1

Citation

Francois Fages, Guillaume Le Guludec, Olivier Bournez, Amaury Pouly. Turing Completeness of Elementary Reaction Systems under the Differential Semantics and Compilation of Mixed Analog-Digital Programs. 2017. ⟨hal-01519828v1⟩

Share

Metrics

Les métriques sont temporairement indisponibles