人工智能通识-科普-图灵机3
2019-02-17 本文已影响27人
zhyuzh3d
欢迎关注我的专栏( つ•̀ω•́)つ【人工智能通识】
这一篇我们再深入看一下上次的那个复制样例的运行过程。
图灵复制机详解
上次我们提到它的功能是把纸带上连续的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状态。
欢迎关注我的专栏( つ•̀ω•́)つ【人工智能通识】
每个人的智能新时代
如果您发现文章错误，请不吝留言指正；
如果您觉得有用，请点喜欢；
如果您觉得很有用，欢迎转载~
END
