复杂表现=计算能力?

     观察表明,生命游戏110号基本规则都能从简单的初始位形演化出十分复杂的模式。两种元胞自动机都被证明能够进行通用计算,不严格地说:可以将任何一个计算机程序“编码”在初始位形中,自动机就会在一定时间后输出原程序的运行结果(当然还需要适当的解码)。例如,原则上我们可以用它们来运行任何你喜欢的电脑游戏,只要给予适当的接口。

      Wolfram等人认为,这种强大的计算能力解释了它们的复杂表现,反之亦然,具有类似表现的系统都有通用计算的潜质。他们进一步提出:既然这些通用计算的系统都是相互等价的,宇宙中所有的复杂现象都可以视作起源于110号基本规则这样简单的模型,从而达到一种特殊的大统一关系。

    这种等价关系显然是经验猜测,但将其当做定论认真对待的研究者大有人在。例如,混沌边缘的概念即来自于计算机科学家Langton对元胞自动机的研究,后者的结论是只有参数λ在某个临界点附近的元胞自动机才能进行通用计算。作者用刻意强调这种特性类似统计物理中的相变和临界现象,来试图泛化这一结论。

    可是其实原论文根本就没有作出通用计算的证明,只是证明它们的长期统计特征表现得“像”110号基本规则,也即是不能被归为简单的周期型或无明显规律的随机型而已。但这种程度的相似不足以将对110号规则图灵完备性的证明迁移到它们身上。或许由于Wolfram人为地将类似规则全归为相对重要的一类(即所谓Class 4),误导读者以为这类规则都共享着其中一员——即110号规则的特征。但自此,临界现象和计算能力间就被“复杂表现”给连上了稳固的纽带。

   要严格讨论计算能力的问题,首先要分析通用计算是不是复杂系统独有的显著特征。答案是否定的

  即使是寻常的硬球撞击都和生命游戏或110号基本规则一样能进行通用计算,因为只凭弹性碰撞已经足以构造Toffoli逻辑门了,而这种门能组成的线路是图灵完备的。

  这点的推论之一是很多格点气体模型也可以进行通用计算(C.Moore, 1995),既然格点气体被认为是成功刻画了现实流体的特征(除了个别不现实的对称性缺失),Moore其实证明了:哪怕是生活中无处不在的气流都有生命游戏的计算潜力,后者根本不稀有,也不能作为系统复杂程度的说明。

   类似地,二维以上的伊辛模型也已被证明具备通用计算的能力,可这并不表明伊辛模型所能涵盖的大量体系都有110号基本规则的有趣特征,现实中也没有人随手拿起一块磁铁加热到居里点附近就当CPU用的。

    究其根本,乃是因为虽然我们证明了使体系做出有用计算的初始位形存在,但这类位形在自然环境下出现的概率可能是极低的,属于极端特征,所以从体系的典型表现中看不出来。因此,单独把通用计算这个特征拿出来,是没用的,这个体系或许会把大部分时间都花在平庸无奇的表现上。

    110号基本规则曾被嘲讽为“从未产生过像真实蚯蚓般复杂的现象”,但批评者的理由却是计算只在人工系统中存在,与自然界的复杂现象无关,这就比Wolfram错得更加离谱了。真实的原因是110号规则中这些现象是极度罕见的,以致于我们至今为止都没发现实现它的位形。但就自然界中计算无处不在这件事,Wolfram并没有说错。只不过他没有说:正因为这种无处不在,所以相关现象间可以完全不相似,即使从统计角度看也是如此

    要说明一个自然体系能进行“计算”,需要至少两个条件:

(1)计算是高效的。如果运行一个程序需要设置的体系基本单元(粒子/元胞)数目十分巨大,那么对应该程序的初始位形随机出现的几率就很低。从而只有透过外界的精密操作才能让系统计算该程序。

(2)计算是可逆的。根据Landauer原理,计算非一一的逻辑映射的系统必须是耗散的,于是持续的不可逆计算都需要相适配的外在驱动机制(我的电脑需要以适当的设备供电才能工作),因此通常只能人工实现。

   110号基本规则和生命游戏虽然图灵完备,但它们不是可逆的。

    反过来,能产生复杂表现的体系也不一定能做通用计算,这点即使是限制在元胞自动机内部也是成立的。

   不过,如果一个元胞自动机规则表现复杂,那么严格证明它不能做通用计算会比较困难。

   虽然如此,判断逻辑映射是否一一却相对容易。而证明计算的低效则可以通过高效仿真这种自动机来实现。例如,如果自动机在t步内的行为总可以被运行时间log t的程序完全预测,则该自动机就不可能做高效的通用计算,否则预测它的程序就可以在对数时间内做到这些事,但对数时间不可能实现线性时间的所有任务。

  总之,自然系统的计算能力和复杂表现分开来看都是很有价值的课题,但两者间的联系就未必如此了。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 216,544评论 6 501
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 92,430评论 3 392
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 162,764评论 0 353
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 58,193评论 1 292
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 67,216评论 6 388
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 51,182评论 1 299
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 40,063评论 3 418
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 38,917评论 0 274
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 45,329评论 1 310
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,543评论 2 332
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,722评论 1 348
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 35,425评论 5 343
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 41,019评论 3 326
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,671评论 0 22
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,825评论 1 269
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 47,729评论 2 368
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 44,614评论 2 353

推荐阅读更多精彩内容