具有非平凡状态和转换的图灵机

图灵机具有： 有限数量的州，其中一个接受，一个拒绝。这项任务显然需要五个州（四个非注入（其中一个必须接受）和一个拒绝）。状态通常被绘制为圆形，每个状态内都有一个标签（州名）。其中一个州是起始国;它标有指向它的箭头。 有限输入字母表。 {0,1}或{a，b}是典型的选择。 有限的磁带字母表，包括一个特殊的空白符号，输入字母表中的所有符号，以及可能更多的符号（但这不是必需的）。 转换功能，为状态和磁带符号的每个组合分配状态，磁带符号和方向。方向可以是L（左）或R（右）。转换被绘制为从一个状态到另一个状态的箭头（或者可能是从状态回到自身的圆形箭头），并且箭头标有两个磁带符号和L或R.显然，您需要六个这样的箭头。 该机器还有一个无限的磁带，分为单元格。在每个单元格中，可以有磁带字母表中的符号。最初在磁带上的符号称为机器的输入。机器有一个读头，总是位于其中一个单元上。假设您有一个从状态A到状态B的过渡箭头，其上带有符号a，b和R.这意味着：“如果机器处于状态A并且磁带头下的符号是a，那么我们应该用b替换该符号，转到状态B，并将读头移动到右边一个单元格。”