numbers - 图灵机 - 生成数字序列

Question

http://morphett.info/turing/turing.html

我将如何创建一个循环数字序列，例如：

01011011101111011111...

所以基本上添加一个零，然后添加 1，然后添加一个零，然后在之前的数量上添加 1。

Answer 1

写01在磁带上。向右移动一格。如果您正在查看零，请向左扫描，直到您看到零。向右移动一格。如果您正在查看 1，请将其替换为 2，然后向右移动直到看到 0；然后继续向右移动，直到你又一个零。将此零替换为一。然后，向后移动，直到看到两个。用一个替换两个。向右移动一个；如果您正在查看一个，请重复替换为两个并再次返回的过程。最终，您将耗尽之前的 1，因此当您向右移动 1 时，您看到的是 0。在这种情况下，向右移动到下一个零，并将其替换为一。循环整个过程（减去“写入01部分”）以获得更长的字符串。

这背后的直觉很简单。如果您向右移动并看到一个零，则向左移动两个零，复制您找到的零之后的最后一个零和倒数第二个零之间的所有 1，然后再添加一个。这两个用于跟踪您在复制的字符串中的位置。基本思想是合理的，但是您应该尝试为此写出状态和转换以使其严谨。

例子：

>
^
>0
 ^
>01
  ^
>010
   ^
>010
 ^
>010
  ^
>020
   ^
>0200
    ^
>0201
   ^
>0201
  ^
>0101
   ^
>0101
    ^
>01010
     ^
>010110
      ^