63

我最近在阅读关于人工生命的文章，偶然发现了这样的说法，“康威的生命游戏展示了足够的复杂性，可以被归类为通用机器。” 我对什么是通用机器只有一个粗略的了解，而维基百科只是让我与维基百科一样接近理解。我想知道是否有人可以对这个非常性感的声明有所了解？

对我来说，康威的生命游戏似乎是一种可爱的消遣，具有一些巨大的影响：我无法在它和计算器之间进行跳跃？这甚至是我应该做出的飞跃吗？

4

5 回答 5

55

Paul Rendell在 Life 中实现了图灵机。滑翔机代表信号，它们之间的交互是门和逻辑，它们一起可以创建更大的组件来实现图灵机。

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

于 2008-12-27T13:31:23.767 回答
41

你可以从康威的生活中建造一台图灵机——尽管这将是非常可怕的。

关键在于滑翔机（和相关模式）——它们沿着比赛场地（缓慢地）移动，因此可以表示比特流（1 表示滑翔机的存在，0 表示没有滑翔机）。可以构建其他模式以接收两个滑翔机流（以直角）并发出另一个对应于原始两个流的 AND/OR/etc 的比特流。

编辑： LogiCell 网站上有更多关于此的内容。

于 2008-12-27T12:41:27.953 回答
15

康威的“生命”可以更进一步：不仅可以构建实现通用图灵机的生命模式，还可以构建冯诺依曼“通用构造器”：http ://conwaylife.com/wiki/Universal_constructor

由于可以对“通用构造器”进行编程以构造任何模式的细胞，包括其自身的副本，因此 Coway 的“生命”能够“自我复制”，而不仅仅是通用计算。

于 2012-01-13T03:37:39.610 回答
11

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

于 2008-12-27T14:53:24.130 回答
4

而保罗查普曼实际上构建了一个具有生命游戏的通用图灵机：http ://www.igblan.free-online.co.uk/igblan/ca/通过构建“通用明斯基注册机”。

该图案是在 30x30 方格的格子上构建的。轻型宇宙飞船 (LWSS) 用于在具有 P60 逻辑的组件之间进行通信（寄存器除外 - 见下文）。一个 LWSS 需要 60 代才能穿过一个格子正方形。因此，每 60 代，任何组件间 LWSS（脉冲）都相对于它所在的正方形处于相同位置，允许旋转

.

于 2010-02-11T14:21:27.177 回答