An Ansatz for computational undecidability in RNA automata
| Autor: | Adam J. Svahn, Mikhail Prokopenko |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
FOS: Computer and information sciences
Quantitative Biology::Biomolecules TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES Formal Languages and Automata Theory (cs.FL) Populations and Evolution (q-bio.PE) Computer Science - Formal Languages and Automata Theory Nonlinear Sciences::Cellular Automata and Lattice Gases Agricultural and Biological Sciences (miscellaneous) Quantitative Biology::Genomics Quantitative Biology - Quantitative Methods General Biochemistry Genetics and Molecular Biology Quantitative Biology::Subcellular Processes ComputingMethodologies_PATTERNRECOGNITION TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES Artificial Intelligence FOS: Biological sciences Computer Science (miscellaneous) Quantitative Biology - Populations and Evolution Quantitative Methods (q-bio.QM) Computer Science::Formal Languages and Automata Theory MathematicsofComputing_DISCRETEMATHEMATICS |
| Popis: | In this ansatz we consider theoretical constructions of RNA polymers into automata, a form of computational structure. The bases for transitions in our automata are plausible RNA enzymes that may perform ligation or cleavage. Limited to these operations, we construct RNA automata of increasing complexity; from the Finite Automaton (RNA-FA) to the Turing machine equivalent 2-stack PDA (RNA-2PDA) and the universal RNA-UPDA. For each automaton we show how the enzymatic reactions match the logical operations of the RNA automaton. A critical theme of the ansatz is the self-reference in RNA automata configurations that exploits the program-data duality but results in computational undecidability. We describe how computational undecidability is exemplified in the self-referential Liar paradox that places a boundary on a logical system, and by construction, any RNA automata. We argue that an expansion of the evolutionary space for RNA-2PDA automata can be interpreted as a hierarchical resolution of computational undecidability by a meta-system (akin to Turing’s oracle), in a continual process analogous to Turing’s ordinal logics and Post’s extensible recursively generated logics. On this basis, we put forward the hypothesis that the resolution of undecidable configurations in RNA automata represent a novelty generation mechanism and propose avenues for future investigation of biological automata. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|