An RNA-based theory of natural universal computation

DOI10.1016/J.JTBI.2021.110984zbMATH Open1483.92063arXiv2008.08814OpenAlexW4205665557MaRDI QIDQ2670144FDOQ2670144

Authors: Hessameddin Akhlaghpour 

Publication date: 10 March 2022

Published in: Journal of Theoretical Biology (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/2008.08814

Recommendations

• scientific article; zbMATH DE number 1241373
• Programming in biomolecular computation
• Computational mechanisms in genetic regulation by RNA
• scientific article; zbMATH DE number 1072534
• scientific article; zbMATH DE number 1738652

zbMATH Keywords

combinatory logicRNAuniversal computationlambda calculussecondary structureChurch-Turing thesisjunk DNAmolecular engramTuring-completenessTuring-equivalence

Mathematics Subject Classification ID

Biochemistry, molecular biology (92C40) Biologically inspired models of computation (DNA computing, membrane computing, etc.) (68Q07)

Cites Work

• Efficient Turing-universal computation with DNA polymers
• Universality in elementary cellular automata
• Logical Reversibility of Computation
• Computation with finite stochastic chemical reaction networks
• Chemical implementation of neural networks and Turing machines.
• Strand algebras for DNA computing
• On Computable Numbers, with an Application to the Entscheidungsproblem
• Modelling, simulating and verifying Turing-powerful strand displacement systems
• The þ-function in λ-K-conversion
• Computability with low-dimensional dynamical systems
• Reachability analysis of dynamical systems having piecewise-constant derivatives
• Closed-form analytic maps in one and two dimensions can simulate universal Turing machines
• Unpredictability and undecidability in dynamical systems
• New Computational Paradigms
• Universal computation and other capabilities of hybrid and continuous dynamical systems
• General-Purpose Computation with Neural Networks: A Survey of Complexity Theoretic Results
• A Natural Axiomatization of Computability and Proof of Church's Thesis
• Noise-robust realization of Turing-complete cellular automata by using neural networks with pattern representation
• Turing computability with neural nets
• Title not available (Why is that?)
• Generalized shifts: unpredictability and undecidability in dynamical systems
• The Church-Turing Thesis over Arbitrary Domains
• New Computational Paradigms
• \(\lambda\)-definability and recursiveness
• Implementation of Turing machine using DNA strand displacement
• Strong Turing completeness of continuous chemical reaction networks and compilation of mixed analog-digital programs
• Comparing Computational Power

Cited In (3)

• Algebraic characterization of RNA operations for DNA-based computation
• Tunable epigenetic catalysis: programming real-time cognitive machines
• Computational mechanisms in genetic regulation by RNA

Uses Software

• ViennaRNA
• VARNA

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)