An RNA-based theory of natural universal computation
From MaRDI portal
Publication:2670144
Abstract: Life is confronted with computation problems in a variety of domains including animal behavior, single-cell behavior, and embryonic development. Yet we currently do not know of a naturally existing biological system that is capable of universal computation, i.e., Turing-equivalent in scope. Generic finite-dimensional dynamical systems (which encompass most models of neural networks, intracellular signaling cascades, and gene regulatory networks) fall short of universal computation, but are assumed to be capable of explaining cognition and development. I present a class of models that bridge two concepts from distant fields: combinatory logic (or, equivalently, lambda calculus) and RNA molecular biology. A set of basic RNA editing rules can make it possible to compute any computable function with identical algorithmic complexity to that of Turing machines. The models do not assume extraordinarily complex molecular machinery or any processes that radically differ from what we already know to occur in cells. Distinct independent enzymes can mediate each of the rules and RNA molecules solve the problem of parenthesis matching through their secondary structure. In the most plausible of these models all of the editing rules can be implemented with merely cleavage and ligation operations at fixed positions relative to predefined motifs. This demonstrates that universal computation is well within the reach of molecular biology. It is therefore reasonable to assume that life has evolved - or possibly began with - a universal computer that yet remains to be discovered. The variety of seemingly unrelated computational problems across many scales can potentially be solved using the same RNA-based computation system. Experimental validation of this theory may immensely impact our understanding of memory, cognition, development, disease, evolution, and the early stages of life.
Recommendations
Cites work
- \(\lambda\)-definability and recursiveness
- A Natural Axiomatization of Computability and Proof of Church's Thesis
- Chemical implementation of neural networks and Turing machines.
- Closed-form analytic maps in one and two dimensions can simulate universal Turing machines
- Comparing Computational Power
- Computability with low-dimensional dynamical systems
- Computation with finite stochastic chemical reaction networks
- Efficient Turing-universal computation with DNA polymers
- General-Purpose Computation with Neural Networks: A Survey of Complexity Theoretic Results
- Generalized shifts: unpredictability and undecidability in dynamical systems
- scientific article; zbMATH DE number 2084341 (Why is no real title available?)
- Implementation of Turing machine using DNA strand displacement
- Logical Reversibility of Computation
- Modelling, simulating and verifying Turing-powerful strand displacement systems
- New Computational Paradigms
- New Computational Paradigms
- Noise-robust realization of Turing-complete cellular automata by using neural networks with pattern representation
- On Computable Numbers, with an Application to the Entscheidungsproblem
- Reachability analysis of dynamical systems having piecewise-constant derivatives
- Strand algebras for DNA computing
- Strong Turing completeness of continuous chemical reaction networks and compilation of mixed analog-digital programs
- The Church-Turing Thesis over Arbitrary Domains
- The þ-function in λ-K-conversion
- Turing computability with neural nets
- Universal computation and other capabilities of hybrid and continuous dynamical systems
- Universality in elementary cellular automata
- Unpredictability and undecidability in dynamical systems
Cited in
(4)
This page was built for publication: An RNA-based theory of natural universal computation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2670144)
