忙碌海狸

有一种特殊的 图灵机 称为 忙碌的海狸.

Busy Beaver 是为 P 符号和 Q 状态定义的机器。
其目的是在磁带上写下尽可能多的符号。

让我们以 2 符号和 2 状态 Busy Beaver 为例。

它由 $P\times Q$ 矩阵描述。

 Symbol|      State-1      |      State-2
       | Write Move   Next | Write Move   Next
----------------------------------------------
 0     |    1   R       2  |   1    L      1
 1     |    1   L       2  |   1    R      0

每行对应于磁带上读取的一个符号。
每列对应一个状态并包含一个三元组：
- 在磁带上写下哪个符号
- 在磁带上移动的方向（左或右）
- 下一个状态。 （状态 0 表示 Beaver 停止。）

示例：如果我们在磁带上读取“0”，并且处于状态 2，则在磁带上写入“1”，然后转到状态 1。
我们总是从一个空磁带（填充有“0”）开始，并处于 1 状态。

如果我们运行这个 Busy Beaver，我们会得到以下执行跟踪：

Step Curr Tape            Move Write Next
 0   1    00000{0}000000  R    1     2
 1   2    000001{0}00000  L    1     1
 2   1    00000{1}100000  L    1     2
 3   2    0000{0}1100000  L    1     1
 4   1    000{0}11100000  R    1     2
 5   2    0001{1}1100000  R    1     0

海狸在 6 步后停止，最后磁带包含 4“1”。

这实际上是“最好的”$2\times 2$ Busy Beaver（在磁带上写下更多“1”的那个）。

我们以 $2\times 6$ Busy Beaver 为例，它由以下矩阵定义：

 Symb|     State-1   |     State-2   |   State-3     |   State-4     |   State-5     |   State-6
     |Write Move Next|Write Move Next|Write Move Next|Write Move Next|Write Move Next|Write Move Next
-----------------------------------------------------------------------------------------------------
 0   |   1   L     2 |  1    R     3 |  0    R     6 |  1    L     1 |  0    L     1 |  1    L     5 
 1   |   1   L     1 |  1    R     2 |  1    R     4 |  0    R     5 |  1    R     3 |  1    L     0 

您可以验证该海狸在 13,122,572,797 步骤后是否停止（花了我 400 秒）。

写100000 '1'需要多少步

您将得到：
- 3726 适用于 100 '1' 的步骤
- 315587 适用于 1000 '1' 的步骤

[我的时间：84 秒]