论文标题
RNA自动机的计算不可证明性的ANSATZ
An Ansatz for computational undecidability in RNA automata
论文作者
论文摘要
在此Ansatz中，我们将RNA聚合物的理论构造视为一种计算结构的Automata。我们自动机中过渡的基础是可能执行连接或裂解的合理RNA酶。仅限于这些操作，我们构建了增加复杂性的RNA自动机。从有限的自动机（RNA-FA）到Turing Machine等效2-stack PDA（RNA-2PDA）和通用RNA UPDA。对于每个自动机，我们显示酶促反应如何匹配RNA自动机的逻辑操作。 ANSATZ的一个关键主题是RNA自动机配置中的自我参考，该配置利用了程序数据二重性，但导致计算性不可证明性。我们描述了如何在逻辑系统上以及通过构造的任何RNA Automata上将边界置于边界的自指骗子悖论中的计算不可证明性。我们认为，RNA-2PDA自动机的进化空间的扩展可以解释为元系统（类似于图灵的甲骨文）对计算不可证明的层次结构，以类似于图灵的序数逻辑和邮政的近代生成逻辑的持续过程。在此基础上，我们提出了以下假设：RNA Automata中无法确定的构型的分辨率代表了一种新颖的生成机制，并提出了途径，以未来研究生物学自动机。
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.
