万能表使用教程:为什么康威的生命游戏可以被归类为万能机器

我最近正在阅读有关人工生命的文章,并遇到了以下声明:"Conway’s Game of Life demonstrates enough complexity to be classified as a universal machine."我只是对universal machine的含义有了粗略的了解,而 Wikipedia 仅使我像 Wikipedia 一样接近理解。我想知道是否有人可以阐明这个非常性感的声明?

Conway's Game of Life对我来说,似乎是一个可爱的分心,有一些巨大的影响:我不能在它和计算器之间跨越?这甚至是我应该做的飞跃吗?

56

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

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

42

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

关键是在滑翔机(以及相关模式)中-它们沿着运动场(缓慢)移动,因此可以表示比特流(滑翔机的存在为 1,而滑翔机的不存在为 0)。可以构建其他模式以容纳两个滑翔机流(成直角),并发出另一个与原始两个流的 AND / OR / 等相对应的比特流。

编辑:有更多关于这个LogiCell web site

15

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

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

11

我强烈推荐庞德斯通的《递归宇宙》一书。,但您可能可以在一个好的图书馆中找到副本。它几乎与康威生命的力量以及具有该自然法则的宇宙中可能存在的事物有关,包括自我复制的实体和 IIRC,达尔文进化论。

本站系公益性非盈利分享网址,本文来自用户投稿,不代表边看边学立场,如若转载,请注明出处

(30)
Penal is e:复合赋值E1op=E2不等同于E1=E1opE2
上一篇
Outlook无法连接到服务器:我无法连接到 Outlook服务器
下一篇

相关推荐

发表评论

登录 后才能评论

评论列表(77条)