欢迎关注我的专栏( つ??ω??)つ【人工智能通识】
这一篇我们再深入看一下上次的那个复制样例的运行过程。
上次我们提到它的功能是把纸带上连续的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停机状态)：
以下几句可能有助于帮你了解上面的图和表格：
欢迎关注我的专栏( つ??ω??)つ【人工智能通识】
假如您发现文章错误，请不吝留言指正；
假如您觉得有用，请点喜欢；
假如您觉得很有用，欢迎转载~
END