状态机：如何构建稳定的婚姻 _状态

相关：
第一数学归纳法 vs 第二数学归纳法 vs 良序定理
【状态机：如何构建稳定的婚姻】第二数学归纳法：硬币问题和堆垛游戏
第一数学归纳法：施塔特中心的地板砖
良序原理：算术基本定理的证明
在这篇博文中我会依次复习一下状态机的定义、不变性原理、部分正确性和可终结性这四个和状态机相关的知识，并举出一些有意思的例子辅以说明，最后解决一个关于稳定婚姻的有趣问题。
0. 什么是状态机
状态机是对“step-by-step“过程的一种抽象模型。
由于计算机程序本身就是一种确定的”step-by-step“过程，所以状态机在计算机科学领域用的很普遍。其中最重要的一个用途就是证明在程序运行的过程中某一些属性能够确定被保持，这些属性也被称为”不变量“ 。在实际生活中有很多”不变量“，例如飞机自动飞行的过程中要保证高度值不能低于1KM，或者核电站在运行的过程中内芯温度不能高于1K摄氏度等等。
1. 状态机的状态与转换
从集合论的角度来看，状态机就是将一个二维关系映射到一个集合上——这个集合的元素叫做”状态“，他们之间的关系称为”转换“，p转换为q写为p -> q 。一个状态机的所有可能转换被称为转换图，每一个状态机都有一个设计的”起始状态“ 。
下面举一个简单的例子，有一个从0到99的累加器，当累加器的状态达到99后再进行累加就会发生溢出：

文章插图
将这个累加器用公式表示就是：

文章插图
如果一个状态机的状态是有限的，我们就称其为有限状态机，例如上面这个例子。相反，如果状态有无穷多个，我们就称其为无限状态机，如果上面这个累加器不设置溢出的话就会变成一个无线状态机。在实际使用时，转太极的状态转换可能会有一些输入输出，转换时对不同的状态也会有不同的花费或者几率，这篇博文中不考虑这些因素。
2. 不变性原理
如果一个状态能够在状态机的某次执行中出现，我们就称之为”可到达的“ 。如果P是一个状态机的不变量，那么无论何时P(n)成立，当状态n -> r后，P(r)也成立。特别地，如果对于一个状态机的起始状态P(n)成立，那么对于任何可到达的状态r，P(r)都成立。
可以看出，不变性原理就是适用于状态机的归纳法 ——如果某个谓语在一开始成立，那么就推出在接下来的所有步骤中它均成立。
下面举一个例子，在《虎胆龙威3》这部电影中，恐怖分子在一个喷泉旁放置了炸弹，并提供了一个5加仑的桶和一个3加仑的桶，如果拆弹人员能够利用这两个桶准确的得到4加仑的水并放在一旁的秤上，炸弹就不会爆炸。

文章插图

文章插图
这个问题看起来也不难，一个小学生也能马上想出来，例如这样一个解法：将3加仑桶装满，全部倒入5加仑桶中，然后再将3加仑装满，倒入5加仑桶中直到5加仑桶满，然后倒掉5加仑桶里的水。这时3加仑桶里有1加仑水，将这1加仑的水倒入刚刚清空的5加仑桶中，然后装满3加仑桶并全部倒入5加仑桶中，这时5加仑桶中的水就是4加仑了。
那么，对于任何两个容积的水桶这个问题都是有解的吗？如果我们将5加仑的水桶换成9加仑的水桶，还能拆除炸弹吗？显然是不行的，因为我们每次的操作都只能是3的整数倍，所以结果也一定是3的整数倍，也就不可能得到4这个结果了。下面我们利用不变性原理来证明这一点：