自动机及其归约

【摘要】 <正> §0 引言 电子数字计算机是一种自动机器。它的巨大用途已为人所共知。人们找出求解问题的算法后,往往借助于电子数字计算机来实现或近似地实现这一算法,从而获得所需的解答。电子数字计算机所能完成的算法决定着它的功能。显然,无论是电子数字计算机的设计或者使用,都要求对它的功能问题加以研究。例如这样一些问题:有什么办法去规范、简化电子数字计算机的逻辑结构而不减弱它的功能?现有类型电子数字计算机的功能到底有多大?在目前技术条件下,有什么拓广其功能的、可行的设计途径?等等。为了研究这些问题,首先必须提出恰当的(数学的)自动机概念。更多还原