计算机的简单理论模型到有限状态机

1. 起源

自动机是计算机的简单理论模型，通常将自动机分为有限自动机和图灵机。尽管有限自动机更简单，但在定义图灵机之后数年，这个概念才被提出来。

沃伦·麦卡洛克当时正在研究脑部创伤治疗精神病人，他想研究出一种解释大脑如何工作的理论。沃尔特·皮茨最初被培养成为一位逻辑学学者，但是却在全新的数学生物物理学领域发表论文。两人于1942年相识，认识到他们对相同类型的问题感兴趣，于是开始联手研究彼此取长补短。他们发表了第一篇论文"神经活动中内在的思想逻辑演算"（A Logical Calculus of Ideas Immanent in Nervous Activity），在这篇论文中，他们借助细胞对神经元进行了建模。虽然每个细胞都有多个输入，但只有一个输出。一个细胞的输出必须成为另一个细胞的输入，输入的类型有两种——抑制的和兴奋的。如果兴奋的输入超过了一定阈值，且没有抑制输入，细胞将会被激活。虽然细胞的集合和它们之间的连接被两人称为神经网络，但他们没有意识到，这是大脑实际运作的简化模型，通过研究神经网络可以得知神经网络如何处理逻辑活动。他们的网络模型与神经元和人类的大脑具备相同的特征，因此他们希望自己的研究能够揭示人类逻辑推理的奥秘。

他们的论文引起了计算机专家约翰·冯·诺依曼和著名的数学家、哲学家诺伯特·维纳的注意，两位学者对这篇论文印象深刻。维纳看到了其中蕴含的力量，他意识到，这一观点具有广泛的适应性，可以发展出控制论。控制论将催生可以学习的机器的理念，反过来也会孕育人工智能。冯·诺依曼认识到，麦卡洛克和皮茨对细胞和细胞间连接的描述，同样可以应用到电子组件和计算中。他在《关于EDVAC的报告》（First draft of a report on the EDVAC）一文中对此进行了详细的描述，正是这篇论文奠定了现代计算机构建的基石。

另一个受到麦卡洛克和皮茨影响的人是马文·明斯基，1954年明斯基在他的博士论文中对神经网络进行了研究，展示了如何使用这些网络对自动机进行全面的描述。明斯基的著作《计算：有限和无限机器》是这一领域的经典之作，高屋建瓴地描述了自动机和计算理论。通过对比物理学，明斯基在这本书的前言中解释了这种使用理论机器研究的理论为什么能够发挥作用。

与物理学使用统计定义事件的方法不同，我们是用逻辑定义的计算或表达式。它们被联系在一起，不是通过几何或能量性质，而是通过它们与类似机器或类似定义之间的关系。我们能够使用机器组件进行简单的交互，应用最显而易见的逻辑命题。面对等价的现实物理机器时，我们必须解决极端复杂的分析等式。

自动机被划分为两类：一类具有有限内存，另一类具有无限内存下面只研究有限的一类。

2.有限状态机

有限状态机（Finite State Machine，FSM）是一种抽象的机制， 它包括有限数量的状态。因此FSM是一个状态集，值的一个有限集合。

闸机是一个常见的状态机，这是《敏捷软件开发——原则、模式与实战》一书中展示的一个经典示例。在这里，将以香港地铁站的闸机为例介绍有限状态机，其用例文本摘要如下：

通常闸机默认是关闭的，当闸机收到有效卡信息时，则打开闸机；当乘客通过后，则关闭闸机。如果有人非法通过，则闸机会发出连续的"滴、滴、滴……"报警声；如果闸机已经打开，而乘客还在刷卡，则闸机会发出"滴"的声音提示乘客，并显示"票价和余额，闸机已经打开，请通过，谢谢！"

FSM会响应"事件"而改变状态，即将每个"事件"实现为一个函数，当"事件"发生时，就意味着调用了一个函数。FSM也执行动作产生输出，所执行的动作是当前状态和输入事件的一个函数，其目的是执行系统的任务。

事件是指在某个时刻发生的事情，比如，闸机的"刷卡（card）"事件和"通过（pass）"事件，状态是系统的状态。事件表示时间点，状态表示时间段，状态对应对象接收的两次事件之间的时间间隔。比如，闸机可能处于的状态：Locked状态和Unlocked状态。

转换是从一个状态转移为另一个状态的路径，引发它的事件被称为事件触发器，简称触发。而转换可以触发动作——表示对象的某个方法的调用，比如，当事件card发生时，闸机从Locked状态转换为Unlocked状态并