我对这还不是很了解。这里主要引用Scott Aronson和其他几位数学家的工作，
首先，我们需要了解二进制图灵机（Binary Turing Machine）。这是一种抽象设备，作用于一个由1和0构成的无限长的纸带上。
这台机器有一个内部状态，它读取一个单元，然后根据其状态和所读内容写入1或0，然后向左或右移动，并转换到一个新状态。也可能停止计算。
为了表示机器的所有行为，我们使用一个状态表。这是一个四态机器，因为它有四个不同的状态（不包括停止状态）。对于状态和读取值的每一种组合，都有三种动作：写入的值，如何移动，以及转换到什么状态。
