博文
电脑人心 之 计算机能思维吗？（二）图灵的机器（2）构造
||||
那么，图灵机是啥样子的呢？它其实非常简单。图灵的主要构思之一，是考虑人在进行数学或者逻辑演算的时候是如何工作的。把人按照既定规则做计算和推理的这个操作过程加以最简化而得来的。具体而言，图灵机有下列“零部件”。
首先是一根一维的带子，可以把它想象成一根纸带。带子分成确定的格子，每个格子里面可以写上记号，比如‘0’和‘1’，也可以为空，就是说没有写记号或者记号给抹掉了。这根带子是图灵机输入和输出的来源，也是图灵机记录中间结果的“存储器”。所以，这个带子的角色就好像一个人做算术或者逻辑推理时用的草稿纸那样。通常的草稿纸是二维平面的，比如除法演算的规则就告诉我们除数写在被除数左边，商写在被除数上面的横线之上，余数写在被除数相应位的底下，如此等等。但是按照图灵的分析，这种二维的安排，并不是必需的，因为只要有办法把哪个数写在哪里给有章有序地归置好，一维的带子就应该够用了。同时，也不需要太多种类的记号，因为更复杂的记号总可以由简单的给组合出来。比如，‘0’、‘1’和空白，就可以在二进制下做任何运算了。
人做计算时用纸，自然是为了看清纸上的数字，把下一步的结果用比较原子性的操作（比如一位数的加减乘除）一个个算出来，写到纸上，如此一步一步反复直到得到结果。所以就需要和草稿纸交互作用的机制，这在人就是用眼睛看，用手写。同样，图灵机的带子也有相应的‘读’和‘写’的机制。‘读’在这里的意思，就是把带子上特定空格的记号给区分出来：‘0’就是‘0’，‘1’就是‘1’，空白就是空白；‘写’的意思，就是在带子的特定空格放上个‘0’或者‘1’，替换掉了那里原来的记号，或者把那个格子抹成空白。我们平时做算术，在任何一个时刻，要么读和要么写，总是只在一个位置发生，比如读出被除数的某一位，或者写上商数的新的一位。即使我们有可能同时注视或者写出多位数，但这也可以分解成单独注视或者写出某一位。同样，在图灵机里，‘读’和‘写’在任何时间，只在一个空格进行。这样，我们就可以说有个读写头，它就好像磁带录音机的磁头那样，在任何特定的时间总是在带子的一个特定的格子上方。要改变位置的话，就需要沿着带子挪动读写头，每次或左或右挪动一格。同样，如果需要挪多格的话，总可以通过反复挪动来实现。
有一点要说明的，就是图灵机的带子是没有头的，读写头向左或者向右都可以无穷无尽的走下去。更准确地讲，这个意思不是说在任何时候带子的长度是无限的，而是说在任何时候假使读写头往以便走到了带子在当前长度下的最后一格，那么总可以在头上再接上一段带子，让机器继续运行下去。这就好像草稿纸用完了，总可以再添一张。
有了带子（“草稿纸”）跟读写头（眼睛和铅笔或者说磁头），还缺负责计算的组织运作的东东。完成这个事情的，就是所谓控制器。这个可以想象成一个小盒子。盒子有特定的有限数目的状态。在不同的盒子状态下，机器可以有不同的行为，所以这个盒子才叫做控制器。具体状态在盒子里面是如何实现的不重要，比如可以用指针的位置或者用算盘珠子的位置，重要的是状态和状态之间可以分得一清二楚不会混淆。
有了这些基本零部件，我们就可以讨论如何让图灵机干活了。在任何一步上，决定图灵机做什么事情的有两方面的情况：（1）控制器现在的状态（这可以对应于现在的任务做到哪一步了（比如在做加法的话，可以是“刚写了和，现在该写进位了”），（2）读写头下面是什么；图灵机可以做三方面的事情：（3）从当前状态转移进入下一状态，与此同时（4）在当前格子上写个什么记号（包括用空白抹掉当前记号），并（5）让读写头在带子上左移一格、右移一格或是原地不动。所以，图灵机每一步做的事，就是根据它的（1）当前状态qi跟（2）当前读出的记号sj，决定（3）下一状态qij，（4）写出的记号sij，和（5）读写头的移动方向dij。
这样，图灵机的任何一步都可以用一个五元组来描述：(qi，sj，qij，sij，dij)。这里的下标 i 表示控制器的当前状态qi是所有可能状态之一，下标 j 表示当前读到的记号sj是所有的可能记号之一。两个合在一起的 ij 就表示新的状态qij，写出的记号sij，移动的方向dij是由qi和sj共同决定的，或者说这三者分别都是qi和sj的函数。给定特定的一组(qi，sj，qij，sij，dij)，就是给定了图灵机在qi和sj下的行为，所以可以这样的五元组叫做图灵机的“指令”。当qi和sj不同的时候，就是说处于不同状态，读取不同记号的时候，qij，sij，dij相应地也可以取不同的（或者相同的）值，这样我们就有一些不同的五元组。把这些五元组都合到一起，就得到了决定了机器行为的指令表。我们通常想象指令表是存储在控制器里的，读写头是连在控制器上的。这样，在任何时刻，控制器就可以根据它的当前状态和带子上当前格子里的记号，决定图灵机的行为。
这里，有必要强调说明一下图灵机彻底的离散性。具体说来，带子是离散的：一格就是一格；记号是离散的：一个就是一个；控制器的状态是离散的：此状态非彼状态。读操作的区分和写操作的改变是离散的：读写头下面的是‘0’，读到的就是‘0’，写出的是‘1’，格子上面出现的就是‘1’，读的是啥、写的是啥不会有任何模糊之处。读写头移动是离散的：一格就是一格。状态转换是离散的：从状态甲到状态乙，没有中间状态可言，不会有混淆，不会有交叠。时间是离散的：读写操作、读写头移动、状态转化都是原子性的，一步完成，一步就是一步，没有完成了一半这样的说法。
举个具体的例子：二进制串奇偶性的检查。这里所谓的奇偶性是指二进制串里面有奇数个还是偶数个1。二进制串奇偶性这个概念挺有用。比如你和朋友之间发送消息，事先约定所有的消息都是7位，比如0101010，1110110，1111110，如此等等。这三个串里面，前两个有奇数个1，是奇串，后一个有偶数个1，是偶串。假设你们进一步约定，在发送消息前，每个7位的消息串尾巴上再增加一位，叫做“校验位”。这个校验位根据消息串的奇偶性来设置：如果消息串是奇，校验位就是1，否则就是0。这样，上面三个消息串在增加了奇偶校验位之后，就分别是01010101，11101101，11111100。然后你的朋友再把这样的包含校验位的8位的串，比如11101101，发送给你。如果传输正常，那么不管你的朋友发的是那个消息，这个8位的串都应该是偶串。这样，当你每收到一个串的时候，就可以对它进行奇偶性检验。如果你收到了一个偶串，比如11101101，那可能就没有问题（当然也可能有，比如，本来传输的是00101101，结果半路上前两位给反转而变成了11101101）。但是，如果你收到的是个奇串，比如10101101，那你就知道这中间肯定出问题了，至少有一位的0和1（一定有奇数个0和1）给反转过来了。于是，你就可以要求你的朋友重新传一次。通过这种“奇偶校验”，就可以抓住传输中发生的错误。
这个很有用的奇偶性检验，可以用图灵机来实现。把一个二进制串，放到带子上，串的两头的格子都是空白，读写头对准最左边的那一个非空白的数字（‘0’或者‘1’）。机器的任务是扫描并抹掉整个串，如果是个偶串，就在结束运行之前在带子上留下个‘0’，如果是个奇串，就留下个‘1’，而带子的其他格都是空白。
下面这个指令表，就能让图灵机实现奇偶性检验。在运行开始是，初始状态为‘偶’。表中的‘H’的意思是“HALT”，就是停机。遇到这个状态，机器就不再运行了。（所以，H不出现在qi那一列里面）。
下面看看为什么这个指令表能够完成任务。根据读写头当前所遇到的符号sj，首先，如果遇到0，就不改变状态：“偶”还是“偶”（第1行），“奇”还是“奇”（第4行）；其次，如果遇到1，就改变状态，从“偶”到“奇”（第2行），从“奇”到“偶”（第5行）；最后，如果遇到空白，读写头下面的不再是‘0’或者‘1’了，说明整个串都检查完了，这时，就可以根据状态输出0（第3行），或者输出1（第6行），并进入停机状态H。请注意，在整个过程中，除了进入停机状态H的时候，读写头不移动之外，读写头总是在向右移动；此外，除了进入H的那次，每读完一格，就把那格擦掉，所以sij总是空白。
那么，我们通常所谓这个或者那个图灵机，就是指给定了一个如上表那样的指令表。给定了指令表之后，带子上的输入可以变，只要满足初始状态设置和读写头初始位置的条件，一个图灵机就应该可以对任何合法的输入串进行指令表所实现的处理。
跟学习编程序一样，学习理解图灵机如何运作的最好办法跟踪执行一些指令表和自己构造一些完成各种简单任务的指令表，比如做二进制加法、判断一个串是不是“回文”等等。
［声明：此处的图灵机，细节上不同于Turing于1936年提出的，属于现在比较通用的“改进型”。这里是基于明斯基的Computation: Finite and Infinite Machines。奇偶校验的例子，来自该书第120页。］
https://m.sciencenet.cn/blog-453866-365653.html
上一篇：马路认知科学（一）“过马路，左右看”
下一篇：马路认知科学（二）“红灯停，绿灯行”
首先是一根一维的带子，可以把它想象成一根纸带。带子分成确定的格子，每个格子里面可以写上记号，比如‘0’和‘1’，也可以为空，就是说没有写记号或者记号给抹掉了。这根带子是图灵机输入和输出的来源，也是图灵机记录中间结果的“存储器”。所以，这个带子的角色就好像一个人做算术或者逻辑推理时用的草稿纸那样。通常的草稿纸是二维平面的，比如除法演算的规则就告诉我们除数写在被除数左边，商写在被除数上面的横线之上，余数写在被除数相应位的底下，如此等等。但是按照图灵的分析，这种二维的安排，并不是必需的，因为只要有办法把哪个数写在哪里给有章有序地归置好，一维的带子就应该够用了。同时，也不需要太多种类的记号，因为更复杂的记号总可以由简单的给组合出来。比如，‘0’、‘1’和空白，就可以在二进制下做任何运算了。
人做计算时用纸，自然是为了看清纸上的数字，把下一步的结果用比较原子性的操作（比如一位数的加减乘除）一个个算出来，写到纸上，如此一步一步反复直到得到结果。所以就需要和草稿纸交互作用的机制，这在人就是用眼睛看，用手写。同样，图灵机的带子也有相应的‘读’和‘写’的机制。‘读’在这里的意思，就是把带子上特定空格的记号给区分出来：‘0’就是‘0’，‘1’就是‘1’，空白就是空白；‘写’的意思，就是在带子的特定空格放上个‘0’或者‘1’，替换掉了那里原来的记号，或者把那个格子抹成空白。我们平时做算术，在任何一个时刻，要么读和要么写，总是只在一个位置发生，比如读出被除数的某一位，或者写上商数的新的一位。即使我们有可能同时注视或者写出多位数，但这也可以分解成单独注视或者写出某一位。同样，在图灵机里，‘读’和‘写’在任何时间，只在一个空格进行。这样，我们就可以说有个读写头，它就好像磁带录音机的磁头那样，在任何特定的时间总是在带子的一个特定的格子上方。要改变位置的话，就需要沿着带子挪动读写头，每次或左或右挪动一格。同样，如果需要挪多格的话，总可以通过反复挪动来实现。
有一点要说明的，就是图灵机的带子是没有头的，读写头向左或者向右都可以无穷无尽的走下去。更准确地讲，这个意思不是说在任何时候带子的长度是无限的，而是说在任何时候假使读写头往以便走到了带子在当前长度下的最后一格，那么总可以在头上再接上一段带子，让机器继续运行下去。这就好像草稿纸用完了，总可以再添一张。
有了带子（“草稿纸”）跟读写头（眼睛和铅笔或者说磁头），还缺负责计算的组织运作的东东。完成这个事情的，就是所谓控制器。这个可以想象成一个小盒子。盒子有特定的有限数目的状态。在不同的盒子状态下，机器可以有不同的行为，所以这个盒子才叫做控制器。具体状态在盒子里面是如何实现的不重要，比如可以用指针的位置或者用算盘珠子的位置，重要的是状态和状态之间可以分得一清二楚不会混淆。
有了这些基本零部件，我们就可以讨论如何让图灵机干活了。在任何一步上，决定图灵机做什么事情的有两方面的情况：（1）控制器现在的状态（这可以对应于现在的任务做到哪一步了（比如在做加法的话，可以是“刚写了和，现在该写进位了”），（2）读写头下面是什么；图灵机可以做三方面的事情：（3）从当前状态转移进入下一状态，与此同时（4）在当前格子上写个什么记号（包括用空白抹掉当前记号），并（5）让读写头在带子上左移一格、右移一格或是原地不动。所以，图灵机每一步做的事，就是根据它的（1）当前状态qi跟（2）当前读出的记号sj，决定（3）下一状态qij，（4）写出的记号sij，和（5）读写头的移动方向dij。
这样，图灵机的任何一步都可以用一个五元组来描述：(qi，sj，qij，sij，dij)。这里的下标 i 表示控制器的当前状态qi是所有可能状态之一，下标 j 表示当前读到的记号sj是所有的可能记号之一。两个合在一起的 ij 就表示新的状态qij，写出的记号sij，移动的方向dij是由qi和sj共同决定的，或者说这三者分别都是qi和sj的函数。给定特定的一组(qi，sj，qij，sij，dij)，就是给定了图灵机在qi和sj下的行为，所以可以这样的五元组叫做图灵机的“指令”。当qi和sj不同的时候，就是说处于不同状态，读取不同记号的时候，qij，sij，dij相应地也可以取不同的（或者相同的）值，这样我们就有一些不同的五元组。把这些五元组都合到一起，就得到了决定了机器行为的指令表。我们通常想象指令表是存储在控制器里的，读写头是连在控制器上的。这样，在任何时刻，控制器就可以根据它的当前状态和带子上当前格子里的记号，决定图灵机的行为。
这里，有必要强调说明一下图灵机彻底的离散性。具体说来，带子是离散的：一格就是一格；记号是离散的：一个就是一个；控制器的状态是离散的：此状态非彼状态。读操作的区分和写操作的改变是离散的：读写头下面的是‘0’，读到的就是‘0’，写出的是‘1’，格子上面出现的就是‘1’，读的是啥、写的是啥不会有任何模糊之处。读写头移动是离散的：一格就是一格。状态转换是离散的：从状态甲到状态乙，没有中间状态可言，不会有混淆，不会有交叠。时间是离散的：读写操作、读写头移动、状态转化都是原子性的，一步完成，一步就是一步，没有完成了一半这样的说法。
举个具体的例子：二进制串奇偶性的检查。这里所谓的奇偶性是指二进制串里面有奇数个还是偶数个1。二进制串奇偶性这个概念挺有用。比如你和朋友之间发送消息，事先约定所有的消息都是7位，比如0101010，1110110，1111110，如此等等。这三个串里面，前两个有奇数个1，是奇串，后一个有偶数个1，是偶串。假设你们进一步约定，在发送消息前，每个7位的消息串尾巴上再增加一位，叫做“校验位”。这个校验位根据消息串的奇偶性来设置：如果消息串是奇，校验位就是1，否则就是0。这样，上面三个消息串在增加了奇偶校验位之后，就分别是01010101，11101101，11111100。然后你的朋友再把这样的包含校验位的8位的串，比如11101101，发送给你。如果传输正常，那么不管你的朋友发的是那个消息，这个8位的串都应该是偶串。这样，当你每收到一个串的时候，就可以对它进行奇偶性检验。如果你收到了一个偶串，比如11101101，那可能就没有问题（当然也可能有，比如，本来传输的是00101101，结果半路上前两位给反转而变成了11101101）。但是，如果你收到的是个奇串，比如10101101，那你就知道这中间肯定出问题了，至少有一位的0和1（一定有奇数个0和1）给反转过来了。于是，你就可以要求你的朋友重新传一次。通过这种“奇偶校验”，就可以抓住传输中发生的错误。
这个很有用的奇偶性检验，可以用图灵机来实现。把一个二进制串，放到带子上，串的两头的格子都是空白，读写头对准最左边的那一个非空白的数字（‘0’或者‘1’）。机器的任务是扫描并抹掉整个串，如果是个偶串，就在结束运行之前在带子上留下个‘0’，如果是个奇串，就留下个‘1’，而带子的其他格都是空白。
下面这个指令表，就能让图灵机实现奇偶性检验。在运行开始是，初始状态为‘偶’。表中的‘H’的意思是“HALT”，就是停机。遇到这个状态，机器就不再运行了。（所以，H不出现在qi那一列里面）。
─────────────────────────────────
qi sj qij sij dij
─────────────────────────────────
偶 0 偶 空白 右
─────────────────────────────────
偶 1 奇 空白 右
─────────────────────────────────
偶 空白 H 0 -
─────────────────────────────────
奇 0 奇 空白 右
─────────────────────────────────
奇 1 偶 空白 右
─────────────────────────────────
奇 空白 H 1 -
qi sj qij sij dij
─────────────────────────────────
偶 0 偶 空白 右
─────────────────────────────────
偶 1 奇 空白 右
─────────────────────────────────
偶 空白 H 0 -
─────────────────────────────────
奇 0 奇 空白 右
─────────────────────────────────
奇 1 偶 空白 右
─────────────────────────────────
奇 空白 H 1 -
─────────────────────────────────
下面看看为什么这个指令表能够完成任务。根据读写头当前所遇到的符号sj，首先，如果遇到0，就不改变状态：“偶”还是“偶”（第1行），“奇”还是“奇”（第4行）；其次，如果遇到1，就改变状态，从“偶”到“奇”（第2行），从“奇”到“偶”（第5行）；最后，如果遇到空白，读写头下面的不再是‘0’或者‘1’了，说明整个串都检查完了，这时，就可以根据状态输出0（第3行），或者输出1（第6行），并进入停机状态H。请注意，在整个过程中，除了进入停机状态H的时候，读写头不移动之外，读写头总是在向右移动；此外，除了进入H的那次，每读完一格，就把那格擦掉，所以sij总是空白。
那么，我们通常所谓这个或者那个图灵机，就是指给定了一个如上表那样的指令表。给定了指令表之后，带子上的输入可以变，只要满足初始状态设置和读写头初始位置的条件，一个图灵机就应该可以对任何合法的输入串进行指令表所实现的处理。
跟学习编程序一样，学习理解图灵机如何运作的最好办法跟踪执行一些指令表和自己构造一些完成各种简单任务的指令表，比如做二进制加法、判断一个串是不是“回文”等等。
［声明：此处的图灵机，细节上不同于Turing于1936年提出的，属于现在比较通用的“改进型”。这里是基于明斯基的Computation: Finite and Infinite Machines。奇偶校验的例子，来自该书第120页。］
https://m.sciencenet.cn/blog-453866-365653.html
上一篇：马路认知科学（一）“过马路，左右看”
下一篇：马路认知科学（二）“红灯停，绿灯行”
