  In this Ansatz we consider theoretical constructions of RNA polymers into
automata, a form of computational structure. The basis 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 which 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.
