康托生命游戏与通用图灵机

时间:2024-03-03 14:11:55
PS:今年春天时的一篇读书笔记
 
正文:
好开心,一年多来再次能看到厘清这么多疑问的书。
丹尼尔丹尼特的《*的进化》:但我们谈论*时我们谈些什么?*并非天赋,它又是如何一步步进化的?
*意志如何与一个决定论的世界相容?

这里有一个非常有趣的游戏,这个简单的模型可以如此有力,帮我们思考决定论下是如何产生“避免者”的。可以厘清思考道路上众多的障碍中的第一个:决定论是如何不意味着“不可避免”的。(CH2)

康托生命游戏(Conway\'s Game of Life)
康托生命生活在一个二维的平面世界中。想象一个二维像素网格,每个像素的状态可以是开或关。  每个像素有八个邻居:四个紧邻(东西南北),四个对角相邻。世界状态随每次钟表滴答而改变,并遵循如下简单的规则:
生命物理学:对于网格中的每一格,清点它8个邻居中在当前时刻有几个状态为“开”。如果答案是2,该格在下一刻保持其当前状态(“开”或“关”)。如果答案是3,该格在下一刻状态为“开”。其他所有情况下,该格在下一刻状态为“关” 。
就这么多啦~

就这点规则能做些什么事??不妨前往传送门:wiki词条, 一个基于JAVA的动画模拟
可以是一个静止的生命。
Game of life boat.svg

可以是一个周期变动的生命。
Game of life beacon.gif

还可以演变出会移动的滑翔机(下图中往东南方向移动的小块)及生产它的工厂(右上角),也可以看作一把枪发射子弹。
 

更令人震惊的是,游戏的创始人康威和他的学生们证明了在这个二维世界中存在包含了通用图灵机(Universal Turing Machine)。为啥令人震惊,因为一台通用图灵机理论上能计算任何可计算函数,我们现在用的个人PC,到超级计算机都是通用图灵机的一种。
Universal Turing machine.svg
这里有一个具体实现——保罗.伦德尔(Paul Rendell):传送门 他的图灵机大概是长这样滴:


我们还可以走的更远,康威他们还成功设计了一个自我复制结构,会通过产生自身的更多拷贝而在空平面上殖民,就像培养皿里的细菌,每个包含了一个通用图灵机。不过这么复杂的家伙要长多大?他们估计是在10^13像素这个数量级。

再走远一些,离开了设计者上帝们,这些复杂的结构能否自发出现 ?如果我们引入变异,上面的大家伙还能否正常的复制,再考虑选择的力量,我们的二维世界又会朝怎样发展?这里又涉及到进化的问题,且放下不表。

康托的二维世界只是基于如此简单的规则,却可以演变出类生命的模式,他们可以避免受到某些特定的伤害(发生),而使自身尽可能久的存在。在这样一个决定论的世界,他们也有了一定程度的“避免性”,也即我们一开头所要厘清的第一个障碍:决定论并不意味着“不可避免”。(被决定的避免仍是避免)