为什么康威的生命游戏被归类为通用机器？

Question

我最近在阅读关于人工生命的文章,并且发表了声明,"康威的生命游戏展示了足够的复杂性,被归类为通用机器." 我只是粗略地了解通用机器是什么,维基百科只让我接近理解,就像维基百科一样.我想知道是否有人可以对这个非常性感的陈述有所了解？

对我而言,康威的"生命游戏"似乎是一种可爱的分心,带来了一些巨大的影响:我无法在那和计算器之间实现飞跃？这甚至是我应该做的飞跃吗？

Answer 1

Paul Rendell 在Life中实施了图灵机.滑翔机代表信号,它们之间的相互作用是门和逻辑,它们共同构成了实现图灵机的更大组件.

基本上,任何可以实现AND,OR和NOT的自动机械都可以以足够复杂的方式组合在一起,以完成图灵.它不是一种有用的计算方法,但它符合标准.

"一个周期需要11040代." 大声笑 (7认同)
@Ziggy有人在GoL中构建了RISC指令集计算机，并用它编写了俄罗斯方块https://codegolf.stackexchange.com/questions/11880/build-a-working-game-of-tetris-in-conways-game生命？s = 1 | 2.0058 (2认同)
简直太神奇了。头脑=吹。 (2认同)

Answer 2

你可以在Conway的生活中建造一台图灵机 - 虽然它会非常可怕.

关键在于滑翔机(以及相关模式) - 它们沿着比赛场地(缓慢地)移动,因此可以表示比特流(1的滑翔机的存在以及0的缺席).可以构建其他模式以接收两个滑翔器流(以直角)并发射对应于原始两个流的AND/OR /等的另一个比特流.

编辑:LogiCell网站上有更多内容.

Answer 3

康威的"生活"可以更进一步:它不仅可以构建一个实现通用图灵机的生活模式,还可以建立一个冯诺依曼"通用构造函数:" http://conwaylife.com/wiki/Universal_constructor

由于"通用构造函数"可以编程构建任何细胞模式,包括其自身的副本,因此Coway的"生命"能够"自我复制",而不仅仅是通用计算.

Greg Egan在他的奇幻科幻小说/ Permutation City /中获得了这一点.对于那些对意识的计算意义,心灵上传的社会影响或细胞自动机感兴趣的人,我认为这本书是必读的.一个主要的情节点依赖于这种通用构造函数的存在,这是很棒的. (3认同)

Answer 4

我强烈推荐 Poundstone 的《递归宇宙》这本书。绝版了，但你可能会找到一本，也许在一个好的图书馆里。这几乎都是关于康威生命的力量，以及宇宙中可以存在的具有那套自然法则的事物，包括自我复制的实体和 IIRC，达尔文进化论。