我的博客已经搬家到 xiongbox.com 欢迎访问熊伟的博客！

本文永久链接 http://xiongbox.com/无限自动机论的简单小结/

1.无限自动机论是研究存储量无限的离散数字系统功能和结构以及两者关系的的理论，是自动机论的次级学科。数字电路这类物理系统，只包含有限个记忆元件，它的存储量是有限的。但是，稍复杂的算法，例如整数乘法所要求的存储量往往是无限的。离散数字系统按照存储量分为两大类：存储量有限的和存储量无限的。后者的数学模型为各种无限自动机。在无限自动机论中，主要研究信息加工系统和计算过程的数学模型、模拟、计算、识别和限制等问题。

2.从计算机的逻辑结构出发，抽象出它的数学模型，将一个自动机看作一个由控制器和它的外部环境组成的系统。控制器为一个有限自动机。外部环境由一种数据结构刻划。控制器从外部环境提取信息（输入），根据这些信息和控制器所处的内部状态，产生改变外部环境的指令（输出）并改变控制器的内部状态。自动机一步一步地重复这种过程，对外部环境中的数据进行处理。按照外部环境及其与控制器的相互作用方式的不同，提出许多种不同的自动机。自动机的外部环境可起存储量无限的存储器的作用，现实的计算机的存储量是有限的，因此自动机是计算机的一种理想的数学模型。

3.图灵机等一般自动机所识别的集恰是递归可枚举集，推广到非确定自动机的情形（即控制器是非确定有限自动机）不增加识别能力。识别能力介于有限自动机和一般自动机之间的机器，被认为更接近现实计算机而受到广泛研究。已提出多种不同的自动机。对每种自动机，按照确定和非确定、数据结构的类型、机器与环境间相互作用的方式以及时间空间限制，可再分为许多类。每一类自动机所识别的集构成一类语言。主要研究的问题是各种限制类型的自动机识别集的刻划、包含关系和代数性质。与形式语言有关的一个结果是，在乔姆斯基分层下的四类形式语言对应四类自动机的识别集：０型语言对应图灵机可识别，１型语言对应非确定线性有界自动机可识别，２型语言对应非确定下推自动机可识别，３型语言对应有限自动机可识别。

4.任一个可计算函数或可识别集，在计算时间和存储空间受限制的情况下是否可计算或可识别的问题，从肯定方面涉及到好的算法的设计问题，从否定方面涉及到问题固有复杂性的下界估计问题。无限自动机的理论有助于理解计算过程的本质方面，在程序设计语言和编译方面都有具体的应用。面向现实计算进行研究仍然是发展的趋势。代数方法将受到更多的注意和发展。