关于自动机功能的一些问题

【摘要】 <正> 本文旨在讨论自动机功能函数类的性质。在第一节中,我们证明了自动机与图灵机器的等价性。由于图灵机器理论与别的能行性理论,例如递归函数论是等价的,所以,我们可以充分利用数理逻辑中已有的工具来一般地研究自动机的功能问题。在第二节中我们初步考察了单一自动机的功能。所谓一个自动机是单一的,如果它的每一个境都是单一的,即该境的输入位数和输出位数至少有一个是0。已经证明:单一自动机更多还原