更改

添加99字节 、 2022年1月12日 (三) 17:35
V1.1_20220112_修订
第6行: 第6行:     
注意:页面的美观和整理后续会由编辑部的成员处理,在审校任务中并不涉及。
 
注意:页面的美观和整理后续会由编辑部的成员处理,在审校任务中并不涉及。
 +
    
{{Short description|Self replicating cellular automata}}
 
{{Short description|Self replicating cellular automata}}
第123行: 第124行:  
== Implementations ==
 
== Implementations ==
   −
= 实现 =
+
= 实例 =
 
In automata theory, the concept of a ''universal constructor'' is non-trivial because of the existence of [[Garden of Eden (cellular automaton)|Garden of Eden patterns]]. But a simple definition is that a universal constructor is able to construct any finite pattern of non-excited (quiescent) cells.
 
In automata theory, the concept of a ''universal constructor'' is non-trivial because of the existence of [[Garden of Eden (cellular automaton)|Garden of Eden patterns]]. But a simple definition is that a universal constructor is able to construct any finite pattern of non-excited (quiescent) cells.
   第130行: 第131行:  
在自动机理论中,由于伊甸园模式的存在,普遍构造函数的概念是非平凡的。但一个简单的定义是,通用构造函数能够构造任何非激发(静止)细胞的有限模式。
 
在自动机理论中,由于伊甸园模式的存在,普遍构造函数的概念是非平凡的。但一个简单的定义是,通用构造函数能够构造任何非激发(静止)细胞的有限模式。
   −
'''''【终译版】'''''在自动机理论中,由于伊甸园模式的存在,''通用构造器''的概念非常重要。但一个简单的定义是,''通用构造器''能够构造任何有限模式的非激发(静止)细胞。
+
'''''【终译版】'''''在自动机理论中,由于伊甸园模式的存在,''通用构造器'' 的概念非常重要。但一个简单的定义是,''通用构造器'' 能够构造任何有限模式的非激发(静止)细胞。
    
[[Arthur Burks]] and others extended the work of von Neumann, giving a much clearer and complete set of details regarding the design and operation of von Neumann's self-replicator. The work of J. W. Thatcher is particularly noteworthy, for he greatly simplified the design. Still, their work did not yield a complete design, cell by cell, of a configuration capable of demonstrating self-replication.
 
[[Arthur Burks]] and others extended the work of von Neumann, giving a much clearer and complete set of details regarding the design and operation of von Neumann's self-replicator. The work of J. W. Thatcher is particularly noteworthy, for he greatly simplified the design. Still, their work did not yield a complete design, cell by cell, of a configuration capable of demonstrating self-replication.
第146行: 第147行:  
Renato Nobili 和 Umberto Pesavento 在1995年发表了第一个完全实现的自我复制细胞自动机,比 von Neumann 的工作晚了近50年。他们使用了32态细胞自动机,而不是冯诺依曼最初的29态规范,扩展了它,以便更容易的信号交叉,显式存储功能和更紧凑的设计。他们还发布了原始29状态 CA 中的一个通用构造函数的实现,但是没有一个能够完成复制——配置不能复制它的磁带,也不能触发它的后代; 配置只能构造。
 
Renato Nobili 和 Umberto Pesavento 在1995年发表了第一个完全实现的自我复制细胞自动机,比 von Neumann 的工作晚了近50年。他们使用了32态细胞自动机,而不是冯诺依曼最初的29态规范,扩展了它,以便更容易的信号交叉,显式存储功能和更紧凑的设计。他们还发布了原始29状态 CA 中的一个通用构造函数的实现,但是没有一个能够完成复制——配置不能复制它的磁带,也不能触发它的后代; 配置只能构造。
   −
'''''【终译版】'''''1995 年,Renato Nobili和 Umberto Pesavento 发表了第一个完全实现的自复制元胞自动机,距冯·诺依曼的提出已近 50 年。他们使用 32 态元胞自动机代替冯诺依曼最初的29态规则,通过对其进行了扩展,实现了更轻松的信号交叉、显式记忆功能和更紧凑的设计。他们还在最初的 29 态 CA 中发布了一个通用构造器的实现,但它不能完全复制——机器不能复制它的磁带,也不能激发它构建的后代;机器只能构建。<ref name="NobiliPesavento1996" /><ref name="Automata2008" />
+
'''''【终译版】'''''1995 年,Renato Nobili和 Umberto Pesavento 发表了第一个完全实现的自复制元胞自动机,距冯·诺依曼的提出已近 50 年。他们使用 32 态元胞自动机代替冯诺依曼最初的29态规则,通过对其进行了扩展,实现了更轻松的信号交叉、显式记忆功能和更紧凑的设计。他们还在最初的 29 态 CA 中发布了一个通用构造器的实现,但它不能完全复制——机器不能复制它的磁带,也不能激发它构建的后代,只能构建不包含“描述文件”的机器。<ref name="NobiliPesavento1996" /><ref name="Automata2008" />
    
In 2004, D. Mange et al. reported an implementation of a self-replicator that is consistent with the designs of von Neumann.<ref name=":1">{{Citation|journal=Proceedings of the IEEE| title=A Macroscopic View of Self-replication| volume=92| issue=12| first1=Daniel| last1=Mange|last2=Stauffer|first2=A.|last3=Peparaolo|first3=L.|last4=Tempesti|first4=G.| pages=1929–1945| year=2004|doi=10.1109/JPROC.2004.837631| s2cid=22500865}}</ref>
 
In 2004, D. Mange et al. reported an implementation of a self-replicator that is consistent with the designs of von Neumann.<ref name=":1">{{Citation|journal=Proceedings of the IEEE| title=A Macroscopic View of Self-replication| volume=92| issue=12| first1=Daniel| last1=Mange|last2=Stauffer|first2=A.|last3=Peparaolo|first3=L.|last4=Tempesti|first4=G.| pages=1929–1945| year=2004|doi=10.1109/JPROC.2004.837631| s2cid=22500865}}</ref>
第170行: 第171行:  
2008年,威廉 · r · 巴克利发表了两个构型,它们是冯 · 诺依曼原始的29态 CA 中的自复制因子。巴克利认为,冯 · 诺依曼29态细胞自动机中的信号交叉对于自复制因子的构造是不必要的。巴克利还指出,出于进化的目的,每个复制因子在复制之后都应该返回到原来的结构,以便(理论上)能够复制多个副本。正如发表的,1995年的诺比利-佩斯旺托设计没有满足这一要求,但2007年的诺比利设计做到了,巴克利的配置也是如此。
 
2008年,威廉 · r · 巴克利发表了两个构型,它们是冯 · 诺依曼原始的29态 CA 中的自复制因子。巴克利认为,冯 · 诺依曼29态细胞自动机中的信号交叉对于自复制因子的构造是不必要的。巴克利还指出,出于进化的目的,每个复制因子在复制之后都应该返回到原来的结构,以便(理论上)能够复制多个副本。正如发表的,1995年的诺比利-佩斯旺托设计没有满足这一要求,但2007年的诺比利设计做到了,巴克利的配置也是如此。
   −
'''''【终译版】'''''2008 年,威廉·R·巴克利 (William R. Buckley) 发表了两种配置,它们是冯·诺依曼最初的 29态 CA 中的自我复制器。<ref name="Automata2008" />巴克利声称冯诺依曼 29 态元胞自动机内的信号交叉对于构建自我复制器不是必需的。他还指出,为了进化的目的,每个复制器在复制后都应该恢复到原来的配置,以便能够在理论上制造多个副本。正如发表的那样,1995 年的 Nobili-Pesavento 设计不满足这一要求,但 2007 年 Nobili的设计以及Buckley的配置却满足了这一要求。
+
'''''【终译版】'''''2008 年,威廉·R·巴克利 (William R. Buckley) 发表了两种结构,它们是冯·诺依曼最初的 29态 CA 中的自我复制器。<ref name="Automata2008" />巴克利声称冯诺依曼 29 态元胞自动机内的信号交互对于构建自复制机不是必需的。他还指出,为了进化的目的,每个自复制机在复制后都应该恢复到原来的结构,以便能够在理论上制造多个副本。正如发表的那样,1995 年的 Nobili-Pesavento 设计不满足这一要求,但 2007 年 Nobili的设计以及Buckley的结构却满足了这一要求。
      第179行: 第180行:  
2009年,Buckley 与 Golly 一起发表了 von Neumann 29州元胞自动机的第三种配置,它既可以执行整体自我复制,也可以通过部分构造执行自我复制。这种结构还表明,在冯 · 诺依曼29态细胞自动机中,信号交叉对于自复制因子的构造是不必要的。
 
2009年,Buckley 与 Golly 一起发表了 von Neumann 29州元胞自动机的第三种配置,它既可以执行整体自我复制,也可以通过部分构造执行自我复制。这种结构还表明,在冯 · 诺依曼29态细胞自动机中,信号交叉对于自复制因子的构造是不必要的。
   −
'''''【终译版】'''''2009 年,Buckley 与Golly 一起发布了 von Neumann 29 态元胞自动机的第三种配置,它可以执行整体自我复制,也可以通过部分构造进行自我复制。这种配置还表明,在冯诺依曼 29 态元胞自动机中构建自我复制器不需要信号交叉。
+
'''''【终译版】'''''2009 年,Buckley 与Golly 一起发布了 von Neumann 29 态元胞自动机的第三种结构,它可以执行整体自我复制,也可以通过部分构造进行自我复制。这种结构还表明,在冯诺依曼 29 态元胞自动机中构建自我复制器不需要信号交互。
    
C. L. Nehaniv in 2002, and also Y. Takada et al. in 2004, proposed a universal constructor directly implemented upon an asynchronous cellular automaton, rather than upon a synchronous cellular automaton.
 
C. L. Nehaniv in 2002, and also Y. Takada et al. in 2004, proposed a universal constructor directly implemented upon an asynchronous cellular automaton, rather than upon a synchronous cellular automaton.
第194行: 第195行:  
=== Comparison of implementations ===
 
=== Comparison of implementations ===
   −
=== 各实现间的比较 ===  
+
==='''''【终译版】'''''各实例间的比较 ===  
    
{| class="wikitable sortable" style="text-align:center"
 
{| class="wikitable sortable" style="text-align:center"
第399行: 第400行:  
正如冯 · 诺依曼所定义的,宇宙结构只需要被动构型的结构。因此,普遍建构的概念只不过是一种文学(或者,在这里,是数学)手段。它促进了其他的证明,如一个机器构造良好可能参与自我复制,而通用建设本身只是假定在最小的情况下。在这个标准下,通用结构是微不足道的。因此,虽然这里给出的所有构型都可以构造任何被动构型,但没有一种构型可以构造戈尔曼设计的实时交叉器官。
 
正如冯 · 诺依曼所定义的,宇宙结构只需要被动构型的结构。因此,普遍建构的概念只不过是一种文学(或者,在这里,是数学)手段。它促进了其他的证明,如一个机器构造良好可能参与自我复制,而通用建设本身只是假定在最小的情况下。在这个标准下,通用结构是微不足道的。因此,虽然这里给出的所有构型都可以构造任何被动构型,但没有一种构型可以构造戈尔曼设计的实时交叉器官。
   −
'''''【终译版】'''''正如冯诺依曼所定义的,通用构造过程只需要被动构造的配置。因此,''通用构造器''的概念只不过是一种设想(或是数学)结构。尽管它有助于其他的证明,比如构造良好的机器有可能会自我复制,但通用构造过程本身只是在最简单情况下的设想。此标准下的通用构造概念是不值一提的。因此,尽管这里给出的所有配置都可以构建任何被动配置,但没有一个可以构建 Gorman 设计的''实时交叉器官''(Real-Time Crossing Organ)。<ref name="Automata2008" />
+
'''''【终译版】'''''正如冯诺依曼所定义的,通用构造过程的产物只包含被动“被”构建的结构。因此,''通用构造器'' 的概念只不过是一种设想(或是数学)结构。尽管它有助于其他的证明,比如构造良好的机器有可能会自我复制,但通用构造过程本身只是在最简单情况下的设想。此标准下的通用构造概念是不值一提的。因此,尽管这里给出的所有结构都可以构建出新的相似结构(新结构仅能被动的“被”构建),但没有一个可以实现Gorman 设计的''实时交互机制''(Real-Time Crossing Organ)。<ref name="Automata2008" />
    
= 实用性和计算成本 =
 
= 实用性和计算成本 =
第408行: 第409行:  
冯 · 诺依曼的自复制机的所有实现都需要相当多的资源才能在计算机上运行。例如,在上面显示的 Nobili-Pesavento 32状态实现中,虽然机器的主体只有6329个非空单元(在一个97x170的矩形内) ,但它需要一个145315个单元长的磁带,并且需要630亿个时间步进才能复制。一个以每秒1000个时间/步的速度运行的模拟器需要两年多的时间才能完成第一次复制。1995年,当第一个实现发表时,作者们还没有看到他们自己的机器复制。然而,在2008年,hashlife 算法被扩展到支持 Golly 中的29状态和32状态规则集。在现代的桌面 PC 上,复制现在只需要几分钟,尽管需要大量的内存。
 
冯 · 诺依曼的自复制机的所有实现都需要相当多的资源才能在计算机上运行。例如,在上面显示的 Nobili-Pesavento 32状态实现中,虽然机器的主体只有6329个非空单元(在一个97x170的矩形内) ,但它需要一个145315个单元长的磁带,并且需要630亿个时间步进才能复制。一个以每秒1000个时间/步的速度运行的模拟器需要两年多的时间才能完成第一次复制。1995年,当第一个实现发表时,作者们还没有看到他们自己的机器复制。然而,在2008年,hashlife 算法被扩展到支持 Golly 中的29状态和32状态规则集。在现代的桌面 PC 上,复制现在只需要几分钟,尽管需要大量的内存。
   −
'''''【终译版】'''''冯诺依曼的自复制机的实现都需要相当多的资源才能在计算机上运行。例如,在上面给出的 Nobili-Pesavento 32 态实例中,虽然机器主体只有 6,329 个非空单元(在 97x170 大小的矩形内),但它需要一个长 145,315 个单元的磁带,需要 63十亿个时间步来复制。以每秒 1,000 个时间步长运行的模拟器需要 2 年多的时间来制作第一个副本。1995 年,当第一个实例发布时,作者还没有看到他自己的机器复制。然而,在 2008 年,hashlife算法被扩展到支持Golly 中的 29 态和 32 态规则集. 在现代台式 PC 上。在现代的桌面 PC 上,尽管需要大量的内存,但复制只需要几分钟。
+
'''''【终译版】'''''冯诺依曼的自复制机的实现都需要相当多的资源才能在计算机上运行。例如,在上面给出的 Nobili-Pesavento 32 态实例中,虽然机器主体只有 6,329 个非空单元(在 97x170 大小的矩形内),但它需要一个长 145,315 个单元的磁带,需要 63十亿个时间步来复制。以每秒 1,000 个时间步长运行的模拟器需要 2 年多的时间来制作第一个副本。1995 年,当第一个实例发布时,作者还没有看到他自己的机器复制。然而,在 2008 年,hashlife算法被扩展到支持Golly 中的 29 态和 32 态规则集。在现代的桌面 PC 上,尽管需要大量的内存,但复制只需要几分钟。
    
= 动画画廊 =
 
= 动画画廊 =
35

个编辑