在9种状态下进行复制操作？

Question

有一排长长的单元格。每个单元格包含0或1。一台机器紧接在一系列不间断1的右边，后面紧跟着一系列不间断的0。在下图中，机器用黄线表示。它紧接在三个三个1后面跟多个0的序列的右边。

机器的任务是复制1的副本。完成后，必须用一个包含0的单元格将副本与原件分开。机器的最后放置位置在原件1的右侧。下图显示了机器完成其复制任务后的单元格。

[在每一步骤中，机器必须决定是向左移动一个单元格还是向右移动一个单元格，以及是否向当前定位的单元格写入0或1。机器看不到相邻单元格中的内容。它只能看到当前单元格中的值。机器完全根据当前单元格的值以及之前做出的决定来做出决定。

我能够编程机器以使用九种状态（S0 – S8）执行复制操作。

问题：机器是否可以在少于九种状态下执行复制操作？

以上图形仅显示一个示例，其中复制了三个1。当然，机器必须能够执行任意数量的1的复印操作。

下图显示了所需的九种状态。但是首先，这是对图中使用的表示法的解释：

这里是策略：如上所述，必须复制1。如何知道已经复制了1，剩下要复制的1？将最左边的1移到左边的一个单元格，然后复制它。重复下一个最左边的1。依此类推。将复制一系列移位1，并保留一系列尚未移位和复制的1。一旦不再有未移动的1，机器就完成了。状态0是最终状态。状态1是起始状态。

Answer 1

输入：0 ^ a 1 ^ b 0 ^ c，a + c> = b + 1

输出：0 ^ z 1 ^ b 0 1 ^ b，b + z + 1 = a + c

策略：

1. 将1 ^ b移动到磁带的背面
2. 立即复制1 ^ b到左侧
3. 清理

状态：

• q0：向左扫描，直到看到1；如果磁带开始，则继续状态q3。否则，将1更改为0，然后继续进行q1
• q1：向右扫描直到空白或1；然后，向左移动并继续进入状态q2
• q2：将0更改为1，向左转到并继续q0
• q3：立即扫描，直到找到1；如果您这样做，请将1更改为2，向左移动并继续执行步骤q4；否则继续状态q6
• q4：向左扫描，直到找到0；然后，向右移动并继续进入状态q5
• q5：向左扫描，直到找到0；执行此操作时，将其更改为2，向右移动，然后继续状态q3
• q6：向左扫描，直到找到一个空白，然后将所有2更改为1。然后，停止接受。

[如果您将暂停接受视为自己的状态，则它有8个状态，因此它至少比您给出的状态好1个（如果此状态有效）。这是我看到它处理您的示例的方式：

   0000001110: q0
-> 0000001101: q0, q1, q2, q0
-> 0000001011: q0, q1, q2, q0
-> 0000000111: q0, q1, q2, q0
-> 0000020211: q0, q3, q4, q5, q3
-> 0000220221: q3, q4, q5, q3
-> 0002220222: q3, q4, q5, q3
-> 0001110111: q3, q6, halt-accept