撞球计算机（续）

陈凯

20世纪80年代初，爱德华·富莱德金（Edward Fredkin）和托玛索·托佛利（Tommaso Toffoli）构建了一种撞球逻辑门，这种逻辑门不依赖于电子元件，而是靠球的撞击与反弹来实现逻辑运算。这种纯机械的计算装置是如何运行的呢？笔者并非打桌球的好手，所以就借用Java程序来模拟球的撞击，这个Java程序的源代码可在http：//jameslin.name/bball/免费下载到。

两个球在桌子上滚动，图1中箭头标出了运动的初始方向，两个球撞击到一起，或碰到斜面时，都会因反弹改变其运动路径，其行为完全符合牛顿运动定律。两个球完整的运动路径用粗线画出后大致是如图2所示的。

要注意的是，模拟器中小球是沿网格的线条前进的（如图3），要想让球相互撞击改变路径，需要把斜面安置到恰到好处的位置。显然，必须在输入A端和输入B端均有球时，输出O才会有球滚出，这就是一个与门。不过，撞球逻辑门与众不同的地方是，输入B端的小球虽然没有滚到输出端，但人们可以根据其最终到达的位置，与输出O一起反向推导出小球初始的位置和运动方向，整个过程是可逆转的，人们称此类逻辑门为可逆逻辑门。传统的逻辑门在得到结果后，原始的输入信息就被丢弃了，由于输出信息少于输入信息，信息的损失将以热的形式耗散到环境中。例如，当一个与门得到计算结果是False后，人们无法再回溯计算前的情况究竟是怎样的，除非另外耗费能量将初始状态存储下来。因此，如果使用可逆逻辑门来搭建计算装置，可以大大减少计算过程中所产生的热量。大家若有兴趣，可以在这个撞球与门的基础上稍做修改，使其成为一个撞球或门，试试看吧。

撞球计算机有一些有趣的变种，神户大学的研究者发现大群基氏和尚蟹聚集在一起时，其行为很像是撞球，一是成群的蟹在爬行时会保持完美的直线队形，若碰到墙壁，则会贴着墙壁边缘走。二是当两个蟹群在汇聚后，会形成新的前进方向。于是研究者就找来许多螃蟹，把它们放在规定的路径中，以构建出逻辑门。图4分别是螃蟹或门和螃蟹与门。研究者在构造与门时颇费了一番周折，因为只有当两列螃蟹同时汇聚到五叉路口时，对列方向才会发生改变。（答案在本期找）