这一篇我们再深入看一下上次的那个复制样例的运行过程.
图灵复制机详解
上次我们提到它的功能是把纸带上连续的 1 向左隔一个零复制一份, 比如把 0000011110 变为 01111011110. 通过下面的动图可以看到上次案例的执行情况.
它的基本思路是把右边连续的 1 逐个添加到左边.
00001...111[1]0, 把最右边的 1 变为 0, 得到→
00001...111[0]0, 向左跳过所有的 1, 跳过中间的 0→
00[0]01...11100,(向左跳过所有的 1 到达 1 左侧的 0, 第一遍忽略此步)→
00[0]01...11100, 把左侧这个 0 变为 1, 并准备掉头向右, 得到→
00[1]01...11100, 向右, 跳过所有的 1(第一遍只有 1 个 1)和中间的 0→
0010[1]...11100, 向右, 跳过所有的 1, 到达 1 右侧的 0→
00101...111[0]0, 把右侧这个 0 变为 1, 并掉头向左一位, 得到→
00101...11[1]10, 这个 1 变为 0, 与步骤 1 相同→
00101...11[0]10, 向左跳过所有的 1, 跳过中间的 0, 与步骤 2 相同→
00[1]01...11010, 向左再跳过所有的 1 到达 1 左侧的 0, 与步骤 3 相同→
0[0]101...11010, 把左侧这个 0 变为 1, 并准备掉头向右, 与步骤 4 相同→
0[1]101...11010, 向右, 跳过所有的 1 和中间的 0, 与步骤 5 相同→
0110[1]...11010, 向右, 跳过所有的 1, 到达 1 右侧的 0, 与步骤 6 相同→
01101...11[0]10, 把右侧这个 0 变为 1, 并掉头向左一位, 与步骤 7 相同→
01101...1[1]110, 这个 1 变为 0, 与步骤 1 和 8 相同→
01101...1[0]010,.... 如此循环→
- .....
- 00111..110[1]...11110
, 直到中间 0 右侧最后的 1→
00111..110[0]...11110
, 按步骤 1 和 8 将它变为 0, 现在中间两个 0 相邻→
0[0]111..11001...11110
, 按步骤 2~4 向左, 把左侧 0 变为 1, 准备掉头向右→
01111..11001...11110
, 按步骤 5 向右(步骤 6 忽略), 到达中间 0 右侧的 0→
01111..11[0]11...11110
, 按步骤 7 把右侧这个 0 变为 1, 并掉头向左一位→
01111..11[0]11...11110
, 如果发现这个位置是 0(就是中间 0), 那么就结束→
从上面的过程中我们可以知道这个图灵机可以把纸带上任意多个连续的 1 向左隔 0 复制出一份来, 主要包含的步骤如下图所示:
你可以对照上一篇的图灵规则表来理解(上图中并没包含第 1 条规则 S1-0 和最后一条 H 停机状态):
以下几句可能有助于帮你理解上面的图和表格:
S2 和 S4 相似, S3 和 S5 相似.
只有第 2 条 S1-1 把 0 变 1, 但有两条把 1 变 0, 它们是第 5 条 S3-0 和第 9 条 S5-0.
对于当前状态和下一状态一致, 而且也没有 P 改写的, 其实是循环, 不断地向前走, 一直走到连续 1 结束出现 0, 就会跳转到 Sx-0 规则. 第 4,6,8,10 都属于这类.
改写并掉头 (第 5 条 S3-0 和第 9 条 S5-0) 或者不该写不掉头(第 3 条 S2-0 和第 7 条 S4-0).
从第 9 条 S5-0 会转到 S1 看, 如果中间连续两个 0, 即 00, 第 9 条处于右侧 0[0], 那么就会向左转到左侧[0]0, 即到达第一条导致停机 H 状态.
来源: http://www.jianshu.com/p/4f3a1a394d45