每个计算机系统都是一个状态机

这是我计划发布的关于TLA+的一系列帖子中的第一篇。

首先，让我们来看一个很有哲理的问题--什么是计算机？我是在我的电脑上写这篇文章的，我的电脑有32 GB的RAM和8个2.4 GHz的内核。你很可能也在电脑(或智能手机，也是一台电脑)上阅读这篇文章。如今我们周围都是电脑(智能手机、笔记本电脑、游戏机、智能扬声器、智能家居设备等)。但是什么是计算机呢？

你桌上现在放着数十亿个晶体管的东西就是电脑吗？嗯，那是指你桌上的电脑，或者更广泛地说，是这类电脑的一类。但这当然不能描述所有的计算机。如果我把十亿个晶体管扔进垃圾桶，垃圾桶就不是电脑了。

计算机是由一组以特定方式连接起来的晶体管组成的吗？这可以描述某些体系结构的计算机，例如x86。但这肯定不能描述不同体系结构的所有计算机。我们需要抽象。也许我们不应该看计算机的物理存在。而是用它能做什么来描述和定义一台计算机。你可能已经猜到了，计算机就是图灵机。图灵机描述并定义了世界上所有计算机的所有可能行为。

本·埃特尔有一段非常好的视频来解释图灵机。所以任何算法，程序，分布式系统，你所能想象到的最复杂的系统交互，都可以被描述为一个状态机，它可以由图灵机实现。这在直觉上也是有道理的。从物理上讲，计算机只不过是各种状态的存储器，以及基于所有状态(程序计数器、寄存器值、RAM、进位标志等)的组合逻辑。用于状态转换。

图灵机可以做任何可以计算的事情。图灵机可以用状态机来描述。因此，自然地，状态机足以描述任何可计算的东西。行为可以用编程语言来描述，但往往过于具体。状态机在描述系统行为方面非常灵活和易于使用。

我们可以将这个程序行为描述为两个变量的状态机：A和PC(代表程序计数器)。示例运行可以是<；a：10，PC：Start>；->；<；a：11，PC：Midd>；->；<；a：11，PC：Done>；。描述其行为的状态机如下所示：

如果PC==START：A=GET_RANDOM_NUMBER()ELSE IF PC==MEDER：A+=1ELSE：HALT

您不应该像Python那样自上而下地执行程序。事实上，这根本不是你要运行的程序。它是一个规范，它只指定了该状态机的状态转换。

Python(用您最喜欢的语言替换)也可以用来描述程序行为。只是程序中的状态更难管理和描述，因为它们的表示方式不同。对于上面这个简单的python程序，有堆、栈、程序计数器等隐藏状态。状态机中的状态只是变量。它是一致的，这使得它更容易用于描述行为。