博文
电脑人心 之 计算机能思维吗？（二）图灵的机器（3）"通用性"
|||
上次讲到图灵机的构造，就这么简单的一种安排［link］，图灵认为它是体现了“有效过程”，并通过证明一系列的结果来论证这一点，其中最有名的两个结果无疑是“通用性”和“可计算性”（毋宁说是“不可计算性”）。前一个结果是正面的、肯定性的结果，是说咱们可以构造一个图灵机（就是说构造一个指令表了），叫做“通用图灵机”。
这个通用图灵机──我们可以把它叫做U──完全按照任何普通的图灵机那样运行，就像上次我们讲到的那样：每一步不过是根据当前状态和读写头下当前的符号，按照指令表里面的相应指令，决定新的状态、写出的记号和读写头移动的方向。可是，放到这个图灵机的带子上的输入，其组织比较特别，分为两部分，一部分是任何某个图灵机M（其实就是说M的指令表了）的编码，另一部分是给M的输入m。
U能做的事情呢，就是说如果本来M在输入为m的情况下，最后停机并在带子上留下输出m'，那么U在以M的指令表编码和m联合组成的输入下，最后停机并在带子上留下输出m'；反之，如果本来M在输入为m的情况下，不停机，那么U在相应的以M指令表编码和m的联合输入下，也不停机。就是说，在任何输入m下，U跟M的指令编码部分──这可以视为是U的程序──联合起来，都可以跟M本身在m输入下表现得一样。当然，这里的一样，或者说“等价”，只是从输入输出关系和停机与否而言，也就是说如果我们忽略中间过程里状态和纸带的在每一步上的具体变化的话。（换句话说，这其实是一种非常“行为主义”的等价。）
咱们来简单看看为什么构造这样一个U是可能的。基本的思路是让U来模拟M的每一步。
首先，任何一个图灵机M都可以用一个有限的记号串来编码。这是因为，除了带子之外，图灵机的任何其他方面都是有限的：（1）带子上记号的种类是有限的。比如，上面咱们一直就只考虑了‘0’和‘1’两种，即使加上空白的化，也才三种；而即使用上所有的UNICODE字符，包括全部汉字，也还是有限的。（2）可能的状态数是有限的。（3）读写头的可能移动是有限的：向左、向右或者不动。这样的话，由于构成指令表的任何五元组都是由状态、记号和读写头移动的可能情况组合而成的，指令表也就是必然是有限的。这就意味着，M的指令表可以用有限长度的编码来代表。
其次，输入是很简单的，我们可以不失一般性地假设U和M用的记号是相同的，这样的话，就可以直接把M的输入m放到U的带子上。
第三，M有自己的控制器，控制器不光包括了上面讨论了的指令表，还有M在当前的状态。请注意，这里我们不能根据M的不同，每次有个新的M时，都相应改变U的状态集合。那样的话，U就不再有“通用性”了。可是，我们可以用U自己的带子！具体而言，我们可以在U的带子上面开辟出特定的一块来专门记录M当前的状态。这里可以采取跟M的指令表编码时采取同样的状态编码。这样的话，每次M的状态改变时，U就可以把自己带子上的专用记录区加以相应更新。
最后，在任何特定时刻，M的读写头也在一个特定的位置，所以U也需要跟踪M的读写头的位置。这里可以采用插入一个特殊的记号的方式。比如把‘#’放在U自己带子上对应于M的输入输出记号串的那部分里M的读写头当前所在空格的右边那一格。
有了这些编码M的指令表、输入与状态，以及跟踪M的控制器状态和读写头位置方面的准备，我们就可以考虑U如何去执行（编码后的）M的指令表。
根据U自己带子上对M的控制器状态和读写头位置的记录，可以很容易得到M（如果它自己在运行的话）的当前状态和当前输入记号。拿到了这些之后，就可以根据它们去找出U的带子上那条编码后的相应的M的指令。这里需要图灵机能够进行有限记号串的匹配操作。这个大家想想，应该不难。
找到指令后，就剩下三件事情了：（1）状态转换，这个其实只需要U把找到的指令里的新状态拷贝到的自己带子上记录M状态的那片专用记录区就可以；（2）写出记号，这个只要在带子上用‘#’标出的，M的读写头当前位置处（就是‘#’的右边），把格子里的旧记号用找到的M的指令里的新记号替换就可以；（3）模拟M读写头的移动，这个需要改变特殊记号‘#’的位置，就是说让它和它左边或者右边的邻居格子里的记号交换就可以。
咱们这里只是粗粗勾勒了一下通用图灵机的构造，省略了很多细节，不过由此也应该可以看出构造通用图灵机是可能的。
至于说这个通用性结果的意义，主流的说法是它很了不起，表明了可以有一个图灵机可以做任何其他图灵机可以做的事情。这个结果，或者说这种理解，在历史上曾经刺激了McCulloch和Pitts的开创性的神经网络研究。
不过，俺觉得，这个所谓“通用性”，其实真正的意义在于引入了编程的概念，甚至基本框架。因为要说U可以做任何其他图灵机M可以做的事情，其实是不准确的，因为U总还是需要M的指令表的，就像前面提到的，做M所做的事情的，其实总是U和M的指令表编码的组合。所以，其实U的真正意义在于设立了一个编程框架，这样的话，就不用在物理地去构造M，而只要在U的带子上构造M的指令表编码就行了。所以，“通用性”这个名字很有欺骗性，其实质其实是可编程性。
https://blog.sciencenet.cn/blog-453866-366335.html
上一篇：马路认知科学（二）“红灯停，绿灯行”
下一篇：马路认知科学（三）如何不被“路杀”？
这个通用图灵机──我们可以把它叫做U──完全按照任何普通的图灵机那样运行，就像上次我们讲到的那样：每一步不过是根据当前状态和读写头下当前的符号，按照指令表里面的相应指令，决定新的状态、写出的记号和读写头移动的方向。可是，放到这个图灵机的带子上的输入，其组织比较特别，分为两部分，一部分是任何某个图灵机M（其实就是说M的指令表了）的编码，另一部分是给M的输入m。
U能做的事情呢，就是说如果本来M在输入为m的情况下，最后停机并在带子上留下输出m'，那么U在以M的指令表编码和m联合组成的输入下，最后停机并在带子上留下输出m'；反之，如果本来M在输入为m的情况下，不停机，那么U在相应的以M指令表编码和m的联合输入下，也不停机。就是说，在任何输入m下，U跟M的指令编码部分──这可以视为是U的程序──联合起来，都可以跟M本身在m输入下表现得一样。当然，这里的一样，或者说“等价”，只是从输入输出关系和停机与否而言，也就是说如果我们忽略中间过程里状态和纸带的在每一步上的具体变化的话。（换句话说，这其实是一种非常“行为主义”的等价。）
咱们来简单看看为什么构造这样一个U是可能的。基本的思路是让U来模拟M的每一步。
首先，任何一个图灵机M都可以用一个有限的记号串来编码。这是因为，除了带子之外，图灵机的任何其他方面都是有限的：（1）带子上记号的种类是有限的。比如，上面咱们一直就只考虑了‘0’和‘1’两种，即使加上空白的化，也才三种；而即使用上所有的UNICODE字符，包括全部汉字，也还是有限的。（2）可能的状态数是有限的。（3）读写头的可能移动是有限的：向左、向右或者不动。这样的话，由于构成指令表的任何五元组都是由状态、记号和读写头移动的可能情况组合而成的，指令表也就是必然是有限的。这就意味着，M的指令表可以用有限长度的编码来代表。
其次，输入是很简单的，我们可以不失一般性地假设U和M用的记号是相同的，这样的话，就可以直接把M的输入m放到U的带子上。
第三，M有自己的控制器，控制器不光包括了上面讨论了的指令表，还有M在当前的状态。请注意，这里我们不能根据M的不同，每次有个新的M时，都相应改变U的状态集合。那样的话，U就不再有“通用性”了。可是，我们可以用U自己的带子！具体而言，我们可以在U的带子上面开辟出特定的一块来专门记录M当前的状态。这里可以采取跟M的指令表编码时采取同样的状态编码。这样的话，每次M的状态改变时，U就可以把自己带子上的专用记录区加以相应更新。
最后，在任何特定时刻，M的读写头也在一个特定的位置，所以U也需要跟踪M的读写头的位置。这里可以采用插入一个特殊的记号的方式。比如把‘#’放在U自己带子上对应于M的输入输出记号串的那部分里M的读写头当前所在空格的右边那一格。
有了这些编码M的指令表、输入与状态，以及跟踪M的控制器状态和读写头位置方面的准备，我们就可以考虑U如何去执行（编码后的）M的指令表。
根据U自己带子上对M的控制器状态和读写头位置的记录，可以很容易得到M（如果它自己在运行的话）的当前状态和当前输入记号。拿到了这些之后，就可以根据它们去找出U的带子上那条编码后的相应的M的指令。这里需要图灵机能够进行有限记号串的匹配操作。这个大家想想，应该不难。
找到指令后，就剩下三件事情了：（1）状态转换，这个其实只需要U把找到的指令里的新状态拷贝到的自己带子上记录M状态的那片专用记录区就可以；（2）写出记号，这个只要在带子上用‘#’标出的，M的读写头当前位置处（就是‘#’的右边），把格子里的旧记号用找到的M的指令里的新记号替换就可以；（3）模拟M读写头的移动，这个需要改变特殊记号‘#’的位置，就是说让它和它左边或者右边的邻居格子里的记号交换就可以。
咱们这里只是粗粗勾勒了一下通用图灵机的构造，省略了很多细节，不过由此也应该可以看出构造通用图灵机是可能的。
至于说这个通用性结果的意义，主流的说法是它很了不起，表明了可以有一个图灵机可以做任何其他图灵机可以做的事情。这个结果，或者说这种理解，在历史上曾经刺激了McCulloch和Pitts的开创性的神经网络研究。
不过，俺觉得，这个所谓“通用性”，其实真正的意义在于引入了编程的概念，甚至基本框架。因为要说U可以做任何其他图灵机M可以做的事情，其实是不准确的，因为U总还是需要M的指令表的，就像前面提到的，做M所做的事情的，其实总是U和M的指令表编码的组合。所以，其实U的真正意义在于设立了一个编程框架，这样的话，就不用在物理地去构造M，而只要在U的带子上构造M的指令表编码就行了。所以，“通用性”这个名字很有欺骗性，其实质其实是可编程性。
https://blog.sciencenet.cn/blog-453866-366335.html
上一篇：马路认知科学（二）“红灯停，绿灯行”
下一篇：马路认知科学（三）如何不被“路杀”？
