碎碎念 计算性

tip对于某些系统，要知道它经过 N 步之后是什么状态，没有一种一般性的“捷径”，你必须让系统实际运行相当程度的 N 步。

wolfram将这种系统称为computationally irreducible，如果存在一种方法可以不用逐步运行，就可以直接计算出第N步，那么就可以称之为computationally reducible，就比如：

x(t+1) = x(t) + 1

想要得到 t = 10^12 显然不需要真的执行10^12次，这个是可约的。

米利型状态机

假设一个下同，每一步产生的状态都参与下一步计算，而且不存在都能直接跳到N的一般公式，那么这个是计算不可约，这个有点像mealy型状态机，它的输出依赖于当前状态的输入，而moore型状态机的输出仅仅依赖于当前状态。

Mealy machine 的基本形式可以写成：

$$ \begin{aligned} s_{t+1} &= \delta(s_t, x_t) \ y_t &= \lambda(s_t, x_t) \end{aligned} $$

但是mealy机不等于计算不可约性，因为他是一个有状态的递归系统，我们可以直接得到sn = s0 + n，计算是高度可约的。

指导意义

回到正题，计算不可约对于系统开发指导意义很大，但是并不是对于直接写代码的设计模式，而是一种判断系统应该设计和优化的思维工具。假设你要制作一个动态系统，操作A会导致状态Runtime State，操作B会导致一个状态，然后操作C...

后面的状态取决于前面的执行结果，你不能简单认为整个runtime的规则都知道，那么应该可以一次性计算出整个10000个operation执行完之后的状态。很多系统根本不存在这样的捷径，工程上的思维一般是：

tip 对于具有状态依赖的系统，就应该把演化过程当作系统的一等公民

所以runtime一般设计为：

while (!stopped)
{
    poll();
    dispatch();
    update_state();
}

而不是试图将整个未来状态一次性给计算出来，我们通常关心的是从输入到输出，但是runtime里尽量要关心状态转换。这些状态转换本身就是系统的语义，每个阶段都可能影响系统接下来允许做什么，例如pedding-> cancel -> cancelled，但是running->canncel就不行，所以状态演化不是为了实现这个api而认为添加的东西，而是api行为本身的一部分。不要把系统看作一个从输入得到输出的黑盒！！而要把状态->状态的演化链本身作为系统。

在软件测试里，我们反而会喜欢把他当作黑盒，通常不需要指导内部是怎么实现的，这个叫做黑盒测试，所以一个系统是可以有两种视角的。

架构上，我们要区分可约和不可约，不要认为整个提供不可约，所以就要全部暴力计算，我们需要尽可能将可约和不可约分离开来，将能压缩的地方压缩，不能压缩的地方接受为系统本身的计算过程。