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

Question

请给我一些关于如何进行此

绘制图灵机（使用 Sipser 表示法）的想法，该图灵机具有至少 4 个非平凡（即，非拒绝）状态和至少 6 个非平凡（即，不是到拒绝状态）转换。

Answer 1

图灵机具有：

• 有限数量的状态，其中一个接受，一个拒绝。该任务显然需要五种状态（四种不拒绝（其中一种必须接受）和一种拒绝）。州通常绘制为圆圈，每个圆圈内都有一个标签（州名称）。其中一个状态是起始状态；它标有指向它的箭头。
• 有限的输入字母表。 {0, 1} 或 {a, b} 是典型的选择。
• 有限的磁带字母表，其中包括特殊的空白符号、输入字母表中的所有符号，以及可能更多的符号（但这不是必需的）。
• 转换函数，为状态和磁带符号的每个组合分配状态、磁带符号和方向。方向可以是L（左）或R（右）。转换被绘制为从一种状态到另一种状态的箭头（或者可能是从一种状态返回到自身的圆形箭头），并且该箭头标有两个磁带符号以及 L 或 R。显然，您需要六个这样的箭头。

该机器还有一个无限磁带，被分成多个单元。在每个单元格中，可以有一个来自磁带字母表的符号。最初位于磁带上的符号称为机器的输入。机器有一个读取头，始终位于其中一个单元上方。假设您有一个从状态 A 到状态 B 的转换箭头，其上带有符号 a、b 和 R。这意味着：“如果机器处于状态 A 并且磁头下方的符号是 a，那么我们应该用 b 替换该符号，进入状态 B，并将读取头向右移动一个单元。”