《KKW白皮书》第5节 世界游戏机：基于元胞自动机与DNA计算机原理的“生命游戏”

第5节 世界游戏机：基于元胞自动机与DNA计算机原理的“生命游戏”

图灵在设计图灵机的时候，其基本思想是用机器来模拟人们用纸笔进行数学运算的过程，他把这样的过程看作下列两种简单的动作：在纸上写上或擦除某个符号；把注意力从纸的一个位置移动到另一个位置，而在每个阶段，人要决定下一步的动作，依赖于此人当前所关注的纸上某个位置的符号和此人当前思维的状态。这个机器的每一部分都是有限的，但它有一个潜在的无限长的纸带，因此这种机器只是一个理想的设备。图灵认为这样的一台机器就能模拟人类所能进行的任何计算过程。——这种部分有限和潜在无限的机器，与我们上一节所说的融合了有限游戏和无限游戏的“自由游戏”，具有形式和逻辑的内在一致性。

我们常常说“图灵完备”，指的是一系列操作数据的规则（如指令集、编程语言、元胞自动机）可以用来模拟单带图灵机，而一种计算机语言能够实现任意计算的前提条件是:它提供了一套图灵完备的指令集，所有的架构上几乎都存在以下6条指令：

1.在内存上的减法运算: Mem[b]=Mem[b]=Mem[a]

2.与做比较操作: Mem[b]≤0

3.条件跳转: if (TURE) goto c

4.加载内存到寄存器: load Reg,Mem[addr]

5.存储寄存器到内存: store Reg,Mem[addr]

6.系统调用指令:Syscall

但是，我们知道图灵机会受到储存能力的物理限制，是否存在这种物理限制的具有无限存储能力的通用物理机器或编程语言？我们认为，将与图灵计算能力等价的自动元胞机与DNA计算机的原理互相补充，可以实现一种升级版的“生命游戏机”，这种游戏机是具有无限存储与拓展能力的计算机或编程语言，就像生命的繁衍（存储）与进化（拓展）那样。

这里需要解释下什么是元胞自动机、生命游戏和DNA计算机。

自动元胞机(Cellular Automata)，简称CA，也叫点格自动机、分子自动机或单元自动机，是将时间、空间都离散化的动力系统。上世纪 40 年代，自动元胞机由计算机之父冯·诺依曼最早提出，用于模拟自繁殖系统；在20世纪70年代以来随着动力系统理论的发展，S.Wolfram等人开始将自动元胞机方法用于动力系统的研究。自动元胞机为动力学系统理论中有关秩序、紊动、混沌、非对称等系统整体行为与复杂现象的研究提供了一个有效的工具，已广泛应用于系统科学、计算机科学、人工智能、控制科学、生物科学、机器人科学、人类学以及材料科学等众多领域。自动元胞机(CA)的组成可分为以下四个基本部分：

1.元胞（单元、基元）。组成自动元胞机的最基本元素，分布在离散的一维、二维或多维空间的节点上。

2.元胞空间。元胞所分布在的空间网点的集合。网点可用多种形式进行划分，例如二维元胞可按三角形、四方形或六边形等网格划分，理想化的元胞空间通常是无限延展的，但在实际应用中需要规定元胞空间的大小和相应的边界条件。

3.邻居。根据一定的作用方式确定的与当前元胞有直接联系的元胞的集合。在自动元胞机中，这些作用是定义在局部范围内的，即一个元胞下一时刻的状态决定于元胞自身的状态和它的邻居的状态。

4.规则。根据元胞当前状态以及邻居状态确定下一时刻该元胞状态的函数，也称为状态转移函数。CA中每个元胞的演化规则是局部的，仅同周围的元胞有联系，但动力学行为则是全局的，另外 CA的网络、基元的状态和数值是有限的，而且其演化规则是确定的和随机的。

系统中的每一个元胞都取有限的离散状态，根据既定的局部作用规则做同步更新。系统中所有元胞通过简单的相互作用，构成了整个系统的动态演化。与一般的动力学模型相比，自动元胞机模型不是由严格的物理方程和函数确定的，而是靠一系列的元胞及其相互作用规则构成的。凡是满足类似规则的模型都称为自动元胞机模型，因此，自动元胞机是一类模型的统称，或者说自动元胞机是一个方法框架。

生命游戏(Game of Life)是J.H.Conway在 20世纪 60年代末设计的一种计算机游戏，是一个典型的具有产生动态结构能力的元胞自动机模型,能产生各种丰富的图案,其演化规律近似地描述了生物群体的生存繁殖规律。生命游戏模型设计如下:将二维空间划分为M×N个方形网格,每个格子即为一个元胞,每个元胞都可以看成是一个生命体, 都有生或死两种状态,0代表“死”,1代表“生”。每个元胞周围均有8个邻居。元胞与其邻居构成的3×3的网格称为基本单位。元胞的状态是否发生转化,只与其构成的基本单位的状态有关。生命游戏中,元胞的状态转化规则为:

1.若S(t)=1，SN(t)＝2或3，则S(t+1)=1

2.若S(t)=1，SN(t)≠2或3，则S(t+1)=0

3.若S(t)=0，SN(t)＝3，则S(t+1)=1

4.若S(t)=0，SN(t)≠3，则S(t+1)=0

其中,S(t)表示元胞在t时刻的状态;SN(t)表示在邻居元胞中,t时刻状态为“生”的元胞个数。

这个模型足以应对无限二维空间，如果在更高维度的空间进行计算，就会遇到和图灵机类似的物理瓶颈。这时，我们必然需要一个超越二进制的四进制计算机（DNA计算机和量子计算机都是类四进制）来解决维度的问题（跨链问题，图对图的问题），从而解决分形的问题。所谓分形的问题指的是，在游戏的进行中，杂乱无序的细胞会逐渐演化出各种精致、有形的结构（第3节所说的“图”）；这些结构往往有很好的对称性，而且每一代都在变化形状。一些形状已经锁定，不会逐代变化。有时，一些已经成形的结构会因为一些无序细胞的“入侵”而被破坏。但是形状和秩序经常能从杂乱中产生出来。那么，什么是DNA计算机？它有怎样的特点以致于在当下的时代是我们实现KKW“世界游戏机”（也即“生命游戏机”）愿景的必然选择？

第3节开始我们提到了密码学家阿德尔曼是DNA计算机之父，设计这类计算机初衷是由于电子计算机存储量小、运算速度慢、智能化低，而无法用来解决形形色色的NP(non-deterministic polynomial，NP)-完全问题。1994年，阿德尔曼首次提出利DNA对图论中的一个NP-完全问题——有向哈密尔顿路径问题 (directed Hamiltonian path problem，DHPP)进行编码，借助连接、变性、复 性、聚合酶链式反应 (polymerase chain reaction，PCR)扩增、电泳等生物操 作解决了这一问题。这一研究成果很快引起了计算机、数学、分子生物学等领域科学家们的极大兴趣。它的重要意义不仅仅在于算法和速度，更在于采用了一种全新的介质作为计算要件，以生物技术实现了电子计算机无法解决的难题，并开发了DNA计算潜在的巨大并行性。

DNA计算机的基本思想是利用DNA特殊的双螺旋结构和碱基互补配对规律进行信息编码，把运算对象映射成DNA分子链，并在生物酶的作用下生成各种数据池，然后，按照一定的规则将原始问题的数据运算高度并行地映射成DNA分子链的可控生化过程，最后，利用分子生物技术，如聚合酶链式反应PCR、超声波降解、亲和层析、克隆、诱变、分子纯化、电泳、磁珠分离等检测所需的运算结果。DNA计算的核心问题是将编码后的DNA链作为输入信息，在试管内或其他载体上经过一定时间的可控生物化学反应，从反应后的产物中得到全部的最优解（这就是为什么我们说pow机制如果运行在DNA计算机中，会从计算数字变为计算“图”）。DNA计算的最大优点是充分利用海量DNA分子中的遗传密码及其巨大并行性。

和传统的电子计算机相比，DNA计算机有如下突出优点:

1.高度并行性，运算速度快。一周内的运算量相当于所有电子计算机问世以来的总运算量。

2.储存量大。DNA作为信息的载体，其储存容量非常之大，1m³的DNA溶液可存储1万亿亿的二进制数据，远远超过目前所有电子计算机的总储存量。

3.耗能低。DNA计算所消耗的能量只有一台电子计算机完成同样计算所消耗能量的十亿分之一。

4.DNA分子资源丰富。现在从植物和动物中提取DNA技术已经很成熟，而自然界的植物和动物处处可见。

DNA计算机的上述优点及应用背景极大地吸引了不同学科、不同领域的众多科学家，特别是计算机科学、分子生物学、数学、物理学、化学以及信息学等领域的科学家们。DNA计算机有望成为人类科学史上一个新的里程碑，因为 DNA 计算机有可能解决目前在电子计算机上许多无法解决的问题，如密码破译、困难 NP-完全问题以及工程领域中最大的难题——局部极小值问题等，这些问题的解决，可以使得“加密货币”实现其从上世纪80年代以来的所有愿景，值得KKW社区投入充分的资源推动研发早日实现并普及到家用DNA计算机的程度。

因此，我们判断，这种DNA计算机将连同量子计算机和光子计算机等未来计算机一道，成为未来区块链的基础设施，与其他物理计算机不同的是，DNA计算机是一种生化计算机，它所对应的未来区块链形态是：分形分维分布式双螺旋公有链。

我们在第3节最后提到，从点对点（p2p）到图对图（g2g）的协议升级使得区块链进入“分维时代”，那么，在本节的最后我们要说，基于自动元胞机与DNA计算机的互相补充所实现的一种升级版“生命游戏机”，使得区块链进入“分形时代”，从而KKW成为了一台名副其实的“世界游戏机”。但是，在这台游戏机的冰山之下，必须深深扎根着两个坚实的基础：

1.百万个全球社区节点；

2.分形分维分布式双螺旋公有链。

接下来两节把这两个基础说清楚，我们这份非技术白皮书的使命也就完成了。