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

2020-06-06 01:55:58

这是我计划发布的关于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程序,有堆、栈、程序计数器等隐藏状态。状态机中的状态只是变量。它是一致的,这使得它更容易用于描述行为。