“自复制自动机”的版本间的差异

来自集智百科 - 复杂系统|人工智能|复杂科学|复杂网络|自组织
跳到导航 跳到搜索
(V0.2_20220109_图片+初步翻译)
(V0.21_20220109)
第21行: 第21行:
 
约翰·冯·诺伊曼的通用构造器是细胞自动机(CA)环境中的自我复制机械。它是在20世纪40年代设计的,当时没有使用计算机。机器的基本细节发表在冯 · 诺依曼的《自复制自动机理论》一书中,该书由冯 · 诺依曼死后的亚瑟 · w · 伯克斯于1966年完成。虽然通常不像冯 · 诺依曼的其他著作那样广为人知,但它被认为是自动机理论、复杂系统和人工生命的基础。事实上,诺贝尔奖获得者悉尼 · 布伦纳认为冯 · 诺依曼关于自我复制自动机的工作(以及图灵关于计算机的工作)对生物学理论同样重要,它允许我们“约束我们关于自然和人工机器的思想”。
 
约翰·冯·诺伊曼的通用构造器是细胞自动机(CA)环境中的自我复制机械。它是在20世纪40年代设计的,当时没有使用计算机。机器的基本细节发表在冯 · 诺依曼的《自复制自动机理论》一书中,该书由冯 · 诺依曼死后的亚瑟 · w · 伯克斯于1966年完成。虽然通常不像冯 · 诺依曼的其他著作那样广为人知,但它被认为是自动机理论、复杂系统和人工生命的基础。事实上,诺贝尔奖获得者悉尼 · 布伦纳认为冯 · 诺依曼关于自我复制自动机的工作(以及图灵关于计算机的工作)对生物学理论同样重要,它允许我们“约束我们关于自然和人工机器的思想”。
  
'''''【终译版】'''''约翰·冯·诺依曼(John von Neumann)的'''通用构造器'''是一个细胞自动机(CA)环境中的自我复制结构。它是在20世纪40年代没有使用计算机的情况下设计的。自动机的基本细节发表在了冯·诺依曼的著作''《自复制自动机理论》中,''该书由亚瑟 · 伯克斯(Arthur W. Burks)于冯·诺依曼去世后的1966 年完成。虽然自复制自动机不像冯诺依曼的其他成就那样广为人知,但它被认为是自动机理论(automata theory)、复杂系统(complex systems)和人工生命的基础。并且,诺贝尔奖得主悉尼布伦纳(Sydney Brenner)认为冯诺依曼提出的自复制自动机(以及计算机)也是生物学理论的核心,让我们能够梳理我们对自然和人造机器的认识。
+
'''''【终译版】'''''约翰·冯·诺依曼(John von Neumann)的'''通用构造器'''是一个细胞自动机(CA)环境中的自我复制结构。它是在20世纪40年代没有使用计算机的情况下设计的。自动机的基本细节发表在了冯·诺依曼的著作''《自复制自动机理论》中,''该书由亚瑟 · 伯克斯(Arthur W. Burks)于冯·诺依曼去世后的1966 年完成。<ref name="TSRA" />虽然自复制自动机不像冯诺依曼的其他成就那样广为人知,但它被认为是自动机理论(automata theory)、复杂系统(complex systems)和人工生命的基础。<ref name="McMullin2000" /><ref name="Rocha1998" />并且,诺贝尔奖得主悉尼布伦纳(Sydney Brenner)认为冯诺依曼提出的自复制自动机(以及计算机)也是生物学理论的核心,让我们能够梳理我们对自然和人造机器的认识。<ref name="Brenner2012" />
  
 
Von Neumann's goal, as specified in his lectures at the University of Illinois in 1949,<ref name="TSRA"/> was to design a machine whose complexity could grow automatically akin to biological organisms under [[Natural Selection|natural selection]]. He asked what is the ''threshold of complexity'' that must be crossed for machines to be able to evolve.<ref name=Rocha1998/> His answer was to specify an abstract machine which, when run, would replicate itself. In his design, the self-replicating machine consists of three parts: a "description" of ('blueprint' or program for) itself, a ''universal constructor'' mechanism that can read any description and construct the machine (sans description) encoded in that description, and a ''universal copy machine'' that can make copies of any description. After the universal constructor has been used to construct a new machine encoded in the description, the copy machine is used to create a copy of that description, and this copy is passed on to the new machine, resulting in a working replication of the original machine that can keep on reproducing. Some machines will do this backwards, copying the description and then building a machine. Crucially, the self-reproducing machine can evolve by accumulating mutations of the description, not the machine itself, thus gaining the ability to grow in complexity.<ref name=Rocha1998/><ref name=Brenner2012/>
 
Von Neumann's goal, as specified in his lectures at the University of Illinois in 1949,<ref name="TSRA"/> was to design a machine whose complexity could grow automatically akin to biological organisms under [[Natural Selection|natural selection]]. He asked what is the ''threshold of complexity'' that must be crossed for machines to be able to evolve.<ref name=Rocha1998/> His answer was to specify an abstract machine which, when run, would replicate itself. In his design, the self-replicating machine consists of three parts: a "description" of ('blueprint' or program for) itself, a ''universal constructor'' mechanism that can read any description and construct the machine (sans description) encoded in that description, and a ''universal copy machine'' that can make copies of any description. After the universal constructor has been used to construct a new machine encoded in the description, the copy machine is used to create a copy of that description, and this copy is passed on to the new machine, resulting in a working replication of the original machine that can keep on reproducing. Some machines will do this backwards, copying the description and then building a machine. Crucially, the self-reproducing machine can evolve by accumulating mutations of the description, not the machine itself, thus gaining the ability to grow in complexity.<ref name=Rocha1998/><ref name=Brenner2012/>
第29行: 第29行:
 
1949年,冯 · 诺依曼在伊利诺伊大学厄巴纳-香槟分校的演讲中明确指出,他的目标是设计一种机器,其复杂性可以自动增长,类似于自然选择下的生物有机体。他问,机器要想进化,必须跨越多大的复杂性门槛。他的答案是指定一个抽象的机器,当运行时,它会自我复制。在他的设计中,自我复制机械包括3个部分: 一个对(‘蓝图’或程序)本身的“描述”,一个可以读取任何描述并构造机器的通用构造机制(无描述) ,以及一个可以复制任何描述的通用复印机。在使用通用构造函数构造描述中编码的新机器之后,使用复制机器创建描述的副本,并将该副本传递给新机器,从而生成可以继续复制的原始机器的工作复制。有些机器会向后执行此操作,复制描述,然后构建一台机器。至关重要的是,自我复制机器可以通过不断累积描述的突变而不是机器本身来进化,从而获得在复杂性中增长的能力。
 
1949年,冯 · 诺依曼在伊利诺伊大学厄巴纳-香槟分校的演讲中明确指出,他的目标是设计一种机器,其复杂性可以自动增长,类似于自然选择下的生物有机体。他问,机器要想进化,必须跨越多大的复杂性门槛。他的答案是指定一个抽象的机器,当运行时,它会自我复制。在他的设计中,自我复制机械包括3个部分: 一个对(‘蓝图’或程序)本身的“描述”,一个可以读取任何描述并构造机器的通用构造机制(无描述) ,以及一个可以复制任何描述的通用复印机。在使用通用构造函数构造描述中编码的新机器之后,使用复制机器创建描述的副本,并将该副本传递给新机器,从而生成可以继续复制的原始机器的工作复制。有些机器会向后执行此操作,复制描述,然后构建一台机器。至关重要的是,自我复制机器可以通过不断累积描述的突变而不是机器本身来进化,从而获得在复杂性中增长的能力。
  
'''''【终译版】'''''1949年,冯 · 诺依曼在伊利诺伊大学厄巴纳-香槟分校的演讲中提到,他的目标是设计一种复杂性可以自动增长,类似于自然选择下有机生命体的机器。在被问到机器要跨越''多高的复杂性阈值才''能够进化时,他给出了一个在运行中会自我复制的抽象机器模型(self-replicating machine)。自复制机由三部分组成:1、一个关于自身的“描述”(蓝图或编码);2、可以阅读任何描述并基于描述构建机器的''通用构造''机制(universal constructor mechanism),该机制本身无具体描述;3、可以复制任何描述的复制机(copy machine)。在''通用构造''机制基于描述构建新机器后,复制机用于生成该描述的副本,并将该副本传递给新机器,从而产生原始机器的工作复制可以继续繁殖。有些机器会倒着做,复制描述,然后建造一台机器。至关重要的是,自我复制机器可以通过积累描述的突变而不是机器本身来进化,从而获得了增加复杂性的能力。
+
'''''【终译版】'''''1949年,冯 · 诺依曼在伊利诺伊大学厄巴纳-香槟分校的演讲中提到,<ref name="TSRA" />他的目标是设计一种复杂性可以自动增长,类似于自然选择下有机生命体的机器。在被问到机器要跨越''多高的复杂性阈值才''能够进化时,<ref name="Rocha1998" />他给出了一个在运行中会自我复制的抽象机器模型(self-replicating machine)。自复制机由三部分组成:1、一个关于自身的“描述”(蓝图或编码);2、可以阅读任何描述并基于描述构建机器的''通用构造''机制(universal constructor mechanism),该机制本身无具体描述;3、可以复制任何描述的复制机(copy machine)。在''通用构造''机制基于描述构建新机器后,复制机用于生成该描述的副本,并将该副本传递给新机器,从而产生原始机器的工作复制可以继续繁殖。有些机器会倒着做,复制描述,然后建造一台机器。至关重要的是,自我复制机器可以通过积累描述的突变而不是机器本身来进化,从而获得了增加复杂性的能力。<ref name="Rocha1998" /><ref name="Brenner2012" />
  
 
To define his machine in more detail, von Neumann invented the concept of a [[cellular automata|cellular automaton]]. The [[Von Neumann cellular automaton|one he used]] consists of a two-dimensional grid of cells, each of which can be in one of 29 states at any point in time. At each timestep, each cell updates its state depending on the states of the surrounding cells at the prior timestep. The rules governing these updates are identical for all cells.
 
To define his machine in more detail, von Neumann invented the concept of a [[cellular automata|cellular automaton]]. The [[Von Neumann cellular automaton|one he used]] consists of a two-dimensional grid of cells, each of which can be in one of 29 states at any point in time. At each timestep, each cell updates its state depending on the states of the surrounding cells at the prior timestep. The rules governing these updates are identical for all cells.
第37行: 第37行:
 
为了更详细地定义他的机器,von Neumann 发明了细胞自动机的概念。他使用的那个由一个二维的细胞网格组成,每个细胞在任何时间点都可以处于29种状态之一。在每个时间步骤中,每个单元根据前一个时间步骤中周围单元的状态更新其状态。管理这些更新的规则对所有单元格都是相同的。
 
为了更详细地定义他的机器,von Neumann 发明了细胞自动机的概念。他使用的那个由一个二维的细胞网格组成,每个细胞在任何时间点都可以处于29种状态之一。在每个时间步骤中,每个单元根据前一个时间步骤中周围单元的状态更新其状态。管理这些更新的规则对所有单元格都是相同的。
  
'''''【终译版】'''''为了更详细地定义他的机器,冯诺依曼发明了元胞自动机的概念。在他所使用的一个包括细胞,其中的每一个可以在任何时间点在29个状态中的一个的二维网格。在每个时间步,每个单元格都根据前一个时间步长的周围单元格的状态更新其状态。管理这些更新的规则对于所有单元都是相同的。
+
'''''【终译版】'''''为了更详细地定义他的机器,冯诺依曼发明了元胞自动机(cellular automaton)的概念。在他所使用的一个包括细胞,其中的每一个可以在任何时间点在29个状态中的一个的二维网格。在每个时间步,每个单元格都根据前一个时间步长的周围单元格的状态更新其状态。管理这些更新的规则对于所有单元都是相同的。
  
 
The universal constructor is a certain pattern of cell states in this cellular automaton. It contains one line of cells that serve as the description (akin to [[Turing machine|Turing's tape]]), encoding a sequence of instructions that serve as a 'blueprint' for the machine. The machine reads these instructions one by one and performs the corresponding actions. The instructions direct the machine to use its 'construction arm' (another automaton that functions like an [[Operating System]]<ref name=Rocha1998/>) to build a copy of the machine, without the description tape, at some other location in the cell grid. The description cannot contain instructions to build an equally long description tape, just as a container cannot contain a container of the same size. Therefore, the machine includes the separate copy machine which reads the description tape and passes a copy to the newly constructed machine. The resulting new set of universal constructor and copy machines plus description tape is identical to the old one, and it proceeds to replicate again.
 
The universal constructor is a certain pattern of cell states in this cellular automaton. It contains one line of cells that serve as the description (akin to [[Turing machine|Turing's tape]]), encoding a sequence of instructions that serve as a 'blueprint' for the machine. The machine reads these instructions one by one and performs the corresponding actions. The instructions direct the machine to use its 'construction arm' (another automaton that functions like an [[Operating System]]<ref name=Rocha1998/>) to build a copy of the machine, without the description tape, at some other location in the cell grid. The description cannot contain instructions to build an equally long description tape, just as a container cannot contain a container of the same size. Therefore, the machine includes the separate copy machine which reads the description tape and passes a copy to the newly constructed machine. The resulting new set of universal constructor and copy machines plus description tape is identical to the old one, and it proceeds to replicate again.
第51行: 第51行:
 
= 目的  =  
 
= 目的  =  
  
[[File:Von Neuman Self-replication 2.jpg|thumb|400px|right|Von Neumann's System of Self-Replication Automata with the ability to evolve (Figure adapted from [[Luis M. Rocha|Luis Rocha]]'s Lecture Notes at Indiana University<ref name=Rocha_lec_notes>{{citation |last=Rocha|first=Luis M.| year=2015 |title=Lecture Notes of I-485-Biologically Inspired Computing Course, Indiana University|chapter=Chapter 6. Von Neumann and Natural Selection.|chapter-url=https://homes.luddy.indiana.edu/rocha/academics/i-bic/pdfs/ibic_lecnotes_c6.pdf|url=https://homes.luddy.indiana.edu/rocha/academics/i-bic/pdfs/ibic_lecnotes.pdf}}</ref>). i) the self-replicating system is composed of several automata plus a separate description (an encoding formalized as a [[Turing Machine|Turing 'tape']]) of all the automata: Universal Constructor (A), Universal Copier (B), Operating System (C), extra functions not involved with replication (D), and separate description Φ(A,B,C,D) encoding all automata. ii) (Top) Universal Constructor produces (decodes) automata from their description (''active'' mode of description); (Bottom) Universal Copier copies description of automata (''passive'' mode of description); Mutations Φ(D') to description Φ(D) (not changes in automaton D directly) propagate to the set of automata produced in next generation, allowing (automata + description) system to continue replicating and evolving (D → D').<ref name=Rocha1998/> The active process of construction from a description parallels [[Translation (biology)|DNA translation]], the passive process of copying the description parallels [[DNA replication]], and inheritance of mutated descriptions parallels [[Mutation|Vertical inheritance of DNA mutations]] in Biology,<ref name=Rocha1998/><ref name=Brenner2012/> and were proposed by Von Neumann before the discovery of the structure of the DNA molecule and how it is separately translated and replicated in the Cell.<ref name=Rocha_lec_notes/>|链接=Special:FilePath/Von_Neuman_Self-replication_2.jpg]]
+
[[File:Von Neuman Self-replication 2.jpg|thumb|400px|right|Von Neumann's System of Self-Replication Automata with the ability to evolve (Figure adapted from [[Luis M. Rocha|Luis Rocha]]'s Lecture Notes at Indiana University<ref name=Rocha_lec_notes>{{citation |last=Rocha|first=Luis M.| year=2015 |title=Lecture Notes of I-485-Biologically Inspired Computing Course, Indiana University|chapter=Chapter 6. Von Neumann and Natural Selection.|chapter-url=https://homes.luddy.indiana.edu/rocha/academics/i-bic/pdfs/ibic_lecnotes_c6.pdf|url=https://homes.luddy.indiana.edu/rocha/academics/i-bic/pdfs/ibic_lecnotes.pdf}}</ref>). i) the self-replicating system is composed of several automata plus a separate description (an encoding formalized as a [[Turing Machine|Turing 'tape']]) of all the automata: Universal Constructor (A), Universal Copier (B), Operating System (C), extra functions not involved with replication (D), and separate description Φ(A,B,C,D) encoding all automata. ii) (Top) Universal Constructor produces (decodes) automata from their description (''active'' mode of description); (Bottom) Universal Copier copies description of automata (''passive'' mode of description); Mutations Φ(D') to description Φ(D) (not changes in automaton D directly) propagate to the set of automata produced in next generation, allowing (automata + description) system to continue replicating and evolving (D → D').<ref name=Rocha1998/> The active process of construction from a description parallels [[Translation (biology)|DNA translation]], the passive process of copying the description parallels [[DNA replication]], and inheritance of mutated descriptions parallels [[Mutation|Vertical inheritance of DNA mutations]] in Biology,<ref name=Rocha1998/><ref name=Brenner2012/> and were proposed by Von Neumann before the discovery of the structure of the DNA molecule and how it is separately translated and replicated in the Cell.<ref name=Rocha_lec_notes/>'''''【终译版】'''''Von Neumann 的具有进化能力的自我复制自动机系统(图改编自Luis Rocha在印第安纳大学的讲义)。i) 自我复制系统由几个自动机加上所有自动机的单独描述(形式化为图灵“磁带”的编码)组成:通用构造器(A),通用复印机(B),操作系统(C),不涉及复制的额外功能 (D),以及编码所有自动机的单独描述 Φ(A,B,C,D)。ii)(上)通用构造函数从它们的描述中产生(解码)自动机(描述的''主动''模式);(下)Universal Copier 复制自动机的描述(''被动''描述方式);突变 Φ(D') 到描述 Φ(D)(不是自动机 D 的直接变化)传播到下一代产生的自动机集合,允许(自动机 + 描述)系统继续复制和进化(D → D')。从描述构建的主动过程与DNA 翻译相似,复制描述的被动过程与DNA 复制相似,突变描述的继承与生物学中 DNA 突变的垂直继承相似,由冯诺依曼在发现 DNA 分子的结构以及它如何在细胞中单独翻译和复制之前。|链接=Special:FilePath/Von_Neuman_Self-replication_2.jpg]]
  
 
Von Neumann's design has traditionally been understood to be a demonstration of the logical requirements for machine self-replication.<ref name=McMullin2000/> However, it is clear that far simpler machines can achieve self-replication. Examples include trivial [[Crystal growth|crystal-like growth]], [[template replication]], and [[Langton's loops]]. But von Neumann was interested in something more profound: construction, universality, and evolution.<ref name=Rocha1998/><ref name=Brenner2012/>
 
Von Neumann's design has traditionally been understood to be a demonstration of the logical requirements for machine self-replication.<ref name=McMullin2000/> However, it is clear that far simpler machines can achieve self-replication. Examples include trivial [[Crystal growth|crystal-like growth]], [[template replication]], and [[Langton's loops]]. But von Neumann was interested in something more profound: construction, universality, and evolution.<ref name=Rocha1998/><ref name=Brenner2012/>
第91行: 第91行:
  
 
— Sydney Brenner 悉尼布伦纳
 
— Sydney Brenner 悉尼布伦纳
 
 
 
{{Quote
 
|text=Turing invented the stored-program computer, and von Neumann showed that the description is separate from the universal constructor. This is not trivial. Physicist Erwin Schrödinger confused the program and the constructor in his 1944 book What is Life?, in which he saw chromosomes as ″architect's plan and builder's craft in one″. This is wrong. The code script contains only a description of the executive function, not the function itself.<ref name=Brenner2012/>
 
|author=[[Sydney Brenner]]
 
}}
 
 
=== Evolution of Complexity ===
 
  
 
=== Evolution of Complexity ===
 
=== Evolution of Complexity ===
  
= = = 进化的复杂性 = = =
+
=== 复杂性的演变 ===
 
Von Neumann's goal, as specified in his lectures at the University of Illinois in 1949,<ref name="TSRA"/> was to design a machine whose complexity could grow automatically akin to biological organisms under [[Natural Selection|natural selection]]. He asked what is the ''threshold of complexity'' that must be crossed for machines to be able to evolve and grow in complexity.<ref name=Rocha1998/><ref name=McMullin2000/>  His “proof-of-principle” designs showed how it is logically possible. By using an architecture that separates a general purpose programmable (“universal”) constructor from a general purpose copier, he showed how the descriptions (tapes) of machines could accumulate mutations in self-replication and thus evolve more complex machines (the image below illustrates this possibility.). This is a very important result, as prior to that, it might have been conjectured that there is a fundamental logical barrier to the existence of such machines; in which case, biological organisms, which do evolve and grow in complexity, could not be “machines”, as conventionally understood. Von Neumann's insight was to think of life as a Turing Machine, which, is similarly defined by a state-determined machine "head" separated from a memory tape.<ref name=Brenner2012/>
 
Von Neumann's goal, as specified in his lectures at the University of Illinois in 1949,<ref name="TSRA"/> was to design a machine whose complexity could grow automatically akin to biological organisms under [[Natural Selection|natural selection]]. He asked what is the ''threshold of complexity'' that must be crossed for machines to be able to evolve and grow in complexity.<ref name=Rocha1998/><ref name=McMullin2000/>  His “proof-of-principle” designs showed how it is logically possible. By using an architecture that separates a general purpose programmable (“universal”) constructor from a general purpose copier, he showed how the descriptions (tapes) of machines could accumulate mutations in self-replication and thus evolve more complex machines (the image below illustrates this possibility.). This is a very important result, as prior to that, it might have been conjectured that there is a fundamental logical barrier to the existence of such machines; in which case, biological organisms, which do evolve and grow in complexity, could not be “machines”, as conventionally understood. Von Neumann's insight was to think of life as a Turing Machine, which, is similarly defined by a state-determined machine "head" separated from a memory tape.<ref name=Brenner2012/>
  
第121行: 第112行:
 
'''''【终译版】'''''在实践中,当我们考虑冯诺依曼所追求的特定自动机实现时,我们得出结论,它不会产生太多的进化动力学,因为机器太脆弱了——绝大多数扰动会导致它们有效地瓦解。因此,今天更令人感兴趣的是他在伊利诺伊州的讲座中概述的概念模型,因为它展示了机器在原则上是如何进化的。这种洞察力更加显着,因为该模型先于上述讨论的 DNA 分子结构的发现。还值得注意的是,冯诺依曼的设计认为,向更复杂的突变需要发生在不涉及自我复制本身的子系统(描述)中,正如他认为执行所有不直接参与复制的功能的附加自动机''D''概念化的那样(见上图与冯诺依曼的具有进化能力的自我复制自动机系统。)事实上,在生物有机体中,仅观察到遗传密码的非常微小的变化,这与冯诺依曼的基本原理相吻合,即通用构造函数(''A'')和复印机(''乙'')不会自己发展,使所有的进化(和复杂性的增长),以自动''d''。在他未完成的作品中,冯诺依曼还简要考虑了他的自我复制机器之间的冲突和相互作用,以从他的自我复制机器理论中理解生态和社会互动的演变。
 
'''''【终译版】'''''在实践中,当我们考虑冯诺依曼所追求的特定自动机实现时,我们得出结论,它不会产生太多的进化动力学,因为机器太脆弱了——绝大多数扰动会导致它们有效地瓦解。因此,今天更令人感兴趣的是他在伊利诺伊州的讲座中概述的概念模型,因为它展示了机器在原则上是如何进化的。这种洞察力更加显着,因为该模型先于上述讨论的 DNA 分子结构的发现。还值得注意的是,冯诺依曼的设计认为,向更复杂的突变需要发生在不涉及自我复制本身的子系统(描述)中,正如他认为执行所有不直接参与复制的功能的附加自动机''D''概念化的那样(见上图与冯诺依曼的具有进化能力的自我复制自动机系统。)事实上,在生物有机体中,仅观察到遗传密码的非常微小的变化,这与冯诺依曼的基本原理相吻合,即通用构造函数(''A'')和复印机(''乙'')不会自己发展,使所有的进化(和复杂性的增长),以自动''d''。在他未完成的作品中,冯诺依曼还简要考虑了他的自我复制机器之间的冲突和相互作用,以从他的自我复制机器理论中理解生态和社会互动的演变。
  
[[Image:Pesavento replicator inherited mutations.png|thumb|center|700px|A demonstration of the ability of von Neumann's machine to support inheritable mutations. (1) At an earlier timestep, a mutation was manually added to the second generation machine's tape. (2) Later generations both display the [[phenotype]] of the mutation (a drawing of a flower) and pass the mutation on to their children, since the tape is copied each time. This example illustrates how von Neumann's design allows for complexity growth (in theory) since the tape could specify a machine that is more complex than the one making it.|链接=Special:FilePath/Pesavento_replicator_inherited_mutations.png]]
+
[[Image:Pesavento replicator inherited mutations.png|thumb|center|700px|A demonstration of the ability of von Neumann's machine to support inheritable mutations. (1) At an earlier timestep, a mutation was manually added to the second generation machine's tape. (2) Later generations both display the [[phenotype]] of the mutation (a drawing of a flower) and pass the mutation on to their children, since the tape is copied each time. This example illustrates how von Neumann's design allows for complexity growth (in theory) since the tape could specify a machine that is more complex than the one making it.
 +
 
 +
'''''【终译版】'''''冯诺依曼机器支持可遗传突变的能力的演示。(1) 在较早的时间步,一个突变被手动添加到第二代机器的磁带中。(2) 后代都显示突变的表型(一朵花的图画)并将突变传给他们的孩子,因为每次都复制磁带。这个例子说明了冯诺依曼的设计如何允许复杂性增长(理论上),因为磁带可以指定一台比制造它的机器更复杂的机器。|链接=Special:FilePath/Pesavento_replicator_inherited_mutations.png]]
  
 
== 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.
  
第196行: 第188行:
 
=== Comparison of implementations ===
 
=== Comparison of implementations ===
  
= = = 实现比较 = = =  
+
=== 各实现间的比较 ===  
  
 
{| class="wikitable sortable" style="text-align:center"
 
{| class="wikitable sortable" style="text-align:center"
第394行: 第386行:
 
|超线性
 
|超线性
 
|}
 
|}
 
 
  
 
As defined by von Neumann, universal construction entails the construction of passive configurations, only. As such, the concept of universal construction constituted nothing more than a literary (or, in this case, mathematical) device. It facilitated other proof, such as that a machine well constructed may engage in self-replication, while universal construction itself was simply assumed over a most minimal case. Universal construction under this standard is trivial. Hence, while all the configurations given here can construct any passive configuration, none can construct the real-time crossing organ devised by Gorman.<ref name="Automata2008" />
 
As defined by von Neumann, universal construction entails the construction of passive configurations, only. As such, the concept of universal construction constituted nothing more than a literary (or, in this case, mathematical) device. It facilitated other proof, such as that a machine well constructed may engage in self-replication, while universal construction itself was simply assumed over a most minimal case. Universal construction under this standard is trivial. Hence, while all the configurations given here can construct any passive configuration, none can construct the real-time crossing organ devised by Gorman.<ref name="Automata2008" />
第415行: 第405行:
  
 
= 动画画廊 =
 
= 动画画廊 =
[[文件:320 jump read arm.gif|左|缩略图|Example of a 29-state read arm. 来自维基百科]]
+
[[文件:320 jump read arm.gif|缩略图|Example of a 29-state read arm. 来自维基百科|替代=|无]]
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
  
 
Example of a 29-state read arm.
 
Example of a 29-state read arm.
第429行: 第411行:
 
'''''【终译版】'''''29 状态读取臂的示例。
 
'''''【终译版】'''''29 状态读取臂的示例。
  
= 另见 =
+
= 关联条目 =
 
*[[Codd's cellular automaton]]
 
*[[Codd's cellular automaton]]
 
*[[Langton's loops]]
 
*[[Langton's loops]]
第438行: 第420行:
 
*[[Constructor theory]]
 
*[[Constructor theory]]
  
*Codd's cellular automaton
+
= 参考文献 =
*Langton's loops
 
*Nobili cellular automata
 
*Quine, a program that produces itself as output
 
*Santa Claus machine
 
*Wireworld
 
*Constructor theory
 
 
 
这个程序把自己产生为输出圣诞老人机器线世界构造理论
 
 
 
= 参考文献[编辑] =
 
 
{{Reflist}}
 
{{Reflist}}
  
第462行: 第434行:
 
*John von Neumann's 29 state Cellular Automata Implemented in OpenLaszlo by Don Hopkins
 
*John von Neumann's 29 state Cellular Automata Implemented in OpenLaszlo by Don Hopkins
 
*A Catalogue of Self-Replicating Cellular Automata.  This catalogue complements the Proc. Automata 2008 volume.
 
*A Catalogue of Self-Replicating Cellular Automata.  This catalogue complements the Proc. Automata 2008 volume.
 +
*
 +
*'''''【终译版】'''''
 
*
 
*
  

2022年1月9日 (日) 18:10的版本

此词条暂由彩云小译翻译,翻译字数共2516,未经人工整理和审校,带来阅读不便,请见谅。

词条内容说明:每段内容由三部分组成,第一部分为含有超链接的英文原文,第二部分为不含超链接的英文原文,第三部分为参考译文。

领取审校任务的朋友可根据第二部分的英文原文和第三部分的参考译文重新组织语言,形成终译版,并根据参考文献和自己对该重要概念的理解进行删改与添加。

注意:页面的美观和整理后续会由编辑部的成员处理,在审校任务中并不涉及。

The first implementation of von Neumann's self-reproducing universal constructor.[1] Three generations of machine are shown: the second has nearly finished constructing the third. The lines running to the right are the tapes of genetic instructions, which are copied along with the body of the machines. The machine shown runs in a 32-state version of von Neumann's cellular automata environment, not his original 29-state specification. 冯 · 诺依曼的自复制通用构造函数的第一个实现。三代机器显示: 第二个已经接近完成建设第三。右边的线条是遗传指令的磁带,这些磁带随着机器的身体一起被复制。所展示的机器运行在32状态的冯 · 诺依曼的细胞自动机环境中,而不是他最初的29状态规范。 【终译版】冯 · 诺依曼的自复制通用构造函数的第一个实现。显示了三代机器:第二代已基本完成第三代的构建。向右延伸的线条是遗传指令的磁带,它们与机器的主体一起被复制。显示的机器在冯诺依曼的元胞自动机环境的 32 状态版本中运行,而不是他最初的 29 状态规范。

John von Neumann's universal constructor is a self-replicating machine in a cellular automata (CA) environment. It was designed in the 1940s, without the use of a computer. The fundamental details of the machine were published in von Neumann's book Theory of Self-Reproducing Automata, completed in 1966 by Arthur W. Burks after von Neumann's death.[2] While typically not as well known as von Neumann's other work, it is regarded as foundational for automata theory, complex systems, and artificial life.[3][4] Indeed, Nobel Laureate Sydney Brenner considered Von Neumann's work on self-reproducing automata (together with Turing's work on computing machines) central to biological theory as well, allowing us to "discipline our thoughts about machines, both natural and artificial."[5]

John von Neumann's universal constructor is a self-replicating machine in a cellular automata (CA) environment. It was designed in the 1940s, without the use of a computer. The fundamental details of the machine were published in von Neumann's book Theory of Self-Reproducing Automata, completed in 1966 by Arthur W. Burks after von Neumann's death. While typically not as well known as von Neumann's other work, it is regarded as foundational for automata theory, complex systems, and artificial life. Indeed, Nobel Laureate Sydney Brenner considered Von Neumann's work on self-reproducing automata (together with Turing's work on computing machines) central to biological theory as well, allowing us to "discipline our thoughts about machines, both natural and artificial."

约翰·冯·诺伊曼的通用构造器是细胞自动机(CA)环境中的自我复制机械。它是在20世纪40年代设计的,当时没有使用计算机。机器的基本细节发表在冯 · 诺依曼的《自复制自动机理论》一书中,该书由冯 · 诺依曼死后的亚瑟 · w · 伯克斯于1966年完成。虽然通常不像冯 · 诺依曼的其他著作那样广为人知,但它被认为是自动机理论、复杂系统和人工生命的基础。事实上,诺贝尔奖获得者悉尼 · 布伦纳认为冯 · 诺依曼关于自我复制自动机的工作(以及图灵关于计算机的工作)对生物学理论同样重要,它允许我们“约束我们关于自然和人工机器的思想”。

【终译版】约翰·冯·诺依曼(John von Neumann)的通用构造器是一个细胞自动机(CA)环境中的自我复制结构。它是在20世纪40年代没有使用计算机的情况下设计的。自动机的基本细节发表在了冯·诺依曼的著作《自复制自动机理论》中,该书由亚瑟 · 伯克斯(Arthur W. Burks)于冯·诺依曼去世后的1966 年完成。[2]虽然自复制自动机不像冯诺依曼的其他成就那样广为人知,但它被认为是自动机理论(automata theory)、复杂系统(complex systems)和人工生命的基础。[3][4]并且,诺贝尔奖得主悉尼布伦纳(Sydney Brenner)认为冯诺依曼提出的自复制自动机(以及计算机)也是生物学理论的核心,让我们能够梳理我们对自然和人造机器的认识。[5]

Von Neumann's goal, as specified in his lectures at the University of Illinois in 1949,[2] was to design a machine whose complexity could grow automatically akin to biological organisms under natural selection. He asked what is the threshold of complexity that must be crossed for machines to be able to evolve.[4] His answer was to specify an abstract machine which, when run, would replicate itself. In his design, the self-replicating machine consists of three parts: a "description" of ('blueprint' or program for) itself, a universal constructor mechanism that can read any description and construct the machine (sans description) encoded in that description, and a universal copy machine that can make copies of any description. After the universal constructor has been used to construct a new machine encoded in the description, the copy machine is used to create a copy of that description, and this copy is passed on to the new machine, resulting in a working replication of the original machine that can keep on reproducing. Some machines will do this backwards, copying the description and then building a machine. Crucially, the self-reproducing machine can evolve by accumulating mutations of the description, not the machine itself, thus gaining the ability to grow in complexity.[4][5]

Von Neumann's goal, as specified in his lectures at the University of Illinois in 1949, was to design a machine whose complexity could grow automatically akin to biological organisms under natural selection. He asked what is the threshold of complexity that must be crossed for machines to be able to evolve. His answer was to specify an abstract machine which, when run, would replicate itself. In his design, the self-replicating machine consists of three parts: a "description" of ('blueprint' or program for) itself, a universal constructor mechanism that can read any description and construct the machine (sans description) encoded in that description, and a universal copy machine that can make copies of any description. After the universal constructor has been used to construct a new machine encoded in the description, the copy machine is used to create a copy of that description, and this copy is passed on to the new machine, resulting in a working replication of the original machine that can keep on reproducing. Some machines will do this backwards, copying the description and then building a machine. Crucially, the self-reproducing machine can evolve by accumulating mutations of the description, not the machine itself, thus gaining the ability to grow in complexity.

1949年,冯 · 诺依曼在伊利诺伊大学厄巴纳-香槟分校的演讲中明确指出,他的目标是设计一种机器,其复杂性可以自动增长,类似于自然选择下的生物有机体。他问,机器要想进化,必须跨越多大的复杂性门槛。他的答案是指定一个抽象的机器,当运行时,它会自我复制。在他的设计中,自我复制机械包括3个部分: 一个对(‘蓝图’或程序)本身的“描述”,一个可以读取任何描述并构造机器的通用构造机制(无描述) ,以及一个可以复制任何描述的通用复印机。在使用通用构造函数构造描述中编码的新机器之后,使用复制机器创建描述的副本,并将该副本传递给新机器,从而生成可以继续复制的原始机器的工作复制。有些机器会向后执行此操作,复制描述,然后构建一台机器。至关重要的是,自我复制机器可以通过不断累积描述的突变而不是机器本身来进化,从而获得在复杂性中增长的能力。

【终译版】1949年,冯 · 诺依曼在伊利诺伊大学厄巴纳-香槟分校的演讲中提到,[2]他的目标是设计一种复杂性可以自动增长,类似于自然选择下有机生命体的机器。在被问到机器要跨越多高的复杂性阈值才能够进化时,[4]他给出了一个在运行中会自我复制的抽象机器模型(self-replicating machine)。自复制机由三部分组成:1、一个关于自身的“描述”(蓝图或编码);2、可以阅读任何描述并基于描述构建机器的通用构造机制(universal constructor mechanism),该机制本身无具体描述;3、可以复制任何描述的复制机(copy machine)。在通用构造机制基于描述构建新机器后,复制机用于生成该描述的副本,并将该副本传递给新机器,从而产生原始机器的工作复制可以继续繁殖。有些机器会倒着做,复制描述,然后建造一台机器。至关重要的是,自我复制机器可以通过积累描述的突变而不是机器本身来进化,从而获得了增加复杂性的能力。[4][5]

To define his machine in more detail, von Neumann invented the concept of a cellular automaton. The one he used consists of a two-dimensional grid of cells, each of which can be in one of 29 states at any point in time. At each timestep, each cell updates its state depending on the states of the surrounding cells at the prior timestep. The rules governing these updates are identical for all cells.

To define his machine in more detail, von Neumann invented the concept of a cellular automaton. The one he used consists of a two-dimensional grid of cells, each of which can be in one of 29 states at any point in time. At each timestep, each cell updates its state depending on the states of the surrounding cells at the prior timestep. The rules governing these updates are identical for all cells.

为了更详细地定义他的机器,von Neumann 发明了细胞自动机的概念。他使用的那个由一个二维的细胞网格组成,每个细胞在任何时间点都可以处于29种状态之一。在每个时间步骤中,每个单元根据前一个时间步骤中周围单元的状态更新其状态。管理这些更新的规则对所有单元格都是相同的。

【终译版】为了更详细地定义他的机器,冯诺依曼发明了元胞自动机(cellular automaton)的概念。在他所使用的一个包括细胞,其中的每一个可以在任何时间点在29个状态中的一个的二维网格。在每个时间步,每个单元格都根据前一个时间步长的周围单元格的状态更新其状态。管理这些更新的规则对于所有单元都是相同的。

The universal constructor is a certain pattern of cell states in this cellular automaton. It contains one line of cells that serve as the description (akin to Turing's tape), encoding a sequence of instructions that serve as a 'blueprint' for the machine. The machine reads these instructions one by one and performs the corresponding actions. The instructions direct the machine to use its 'construction arm' (another automaton that functions like an Operating System[4]) to build a copy of the machine, without the description tape, at some other location in the cell grid. The description cannot contain instructions to build an equally long description tape, just as a container cannot contain a container of the same size. Therefore, the machine includes the separate copy machine which reads the description tape and passes a copy to the newly constructed machine. The resulting new set of universal constructor and copy machines plus description tape is identical to the old one, and it proceeds to replicate again.

The universal constructor is a certain pattern of cell states in this cellular automaton. It contains one line of cells that serve as the description (akin to Turing's tape), encoding a sequence of instructions that serve as a 'blueprint' for the machine. The machine reads these instructions one by one and performs the corresponding actions. The instructions direct the machine to use its 'construction arm' (another automaton that functions like an Operating System) to build a copy of the machine, without the description tape, at some other location in the cell grid. The description cannot contain instructions to build an equally long description tape, just as a container cannot contain a container of the same size. Therefore, the machine includes the separate copy machine which reads the description tape and passes a copy to the newly constructed machine. The resulting new set of universal constructor and copy machines plus description tape is identical to the old one, and it proceeds to replicate again.

通用构造函数是本细胞自动机中细胞状态的某种模式。它包含一行细胞作为描述(类似于图灵的磁带) ,对一系列指令进行编码,作为机器的“蓝图”。机器逐条读取这些指令并执行相应的操作。指令指导机器使用它的“构造臂”(另一个自动机,其功能类似于操作系统)在单元网格的其他位置建立一个机器的副本,而不需要描述磁带。说明不能包含生成同样长的说明磁带的指令,就像容器不能包含同样大小的容器一样。因此,该机器包括单独的复印机,该复印机读取描述磁带并将一个副本传递给新构建的机器。由此产生的新的通用构造函数集和复印机加上描述磁带与旧的相同,并且它继续进行复制。

【终译版】通用构造函数是该元胞自动机中的某种细胞状态模式。它包含一行作为描述的单元格(类似于图灵的磁带),对一系列指令进行编码,作为机器的“蓝图”。机器会一一读取这些指令,并执行相应的动作。指令指示机器使用其“构造臂”(另一个功能类似于操作系统的自动机) 在单元格网格中的其他位置构建机器的副本,不带描述带。描述不能包含构建同样长的描述带的说明,就像容器不能包含相同大小的容器一样。因此,该机器包括单独的复印机,该复印机读取描述磁带并将副本传递给新建的机器。生成的一组新的通用构造器和复制机加上描述磁带与旧的相同,并且它会再次进行复制。

Purpose

目的

Von Neumann's System of Self-Replication Automata with the ability to evolve (Figure adapted from Luis Rocha's Lecture Notes at Indiana University[6]). i) the self-replicating system is composed of several automata plus a separate description (an encoding formalized as a Turing 'tape') of all the automata: Universal Constructor (A), Universal Copier (B), Operating System (C), extra functions not involved with replication (D), and separate description Φ(A,B,C,D) encoding all automata. ii) (Top) Universal Constructor produces (decodes) automata from their description (active mode of description); (Bottom) Universal Copier copies description of automata (passive mode of description); Mutations Φ(D') to description Φ(D) (not changes in automaton D directly) propagate to the set of automata produced in next generation, allowing (automata + description) system to continue replicating and evolving (D → D').[4] The active process of construction from a description parallels DNA translation, the passive process of copying the description parallels DNA replication, and inheritance of mutated descriptions parallels Vertical inheritance of DNA mutations in Biology,[4][5] and were proposed by Von Neumann before the discovery of the structure of the DNA molecule and how it is separately translated and replicated in the Cell.[6]【终译版】Von Neumann 的具有进化能力的自我复制自动机系统(图改编自Luis Rocha在印第安纳大学的讲义)。i) 自我复制系统由几个自动机加上所有自动机的单独描述(形式化为图灵“磁带”的编码)组成:通用构造器(A),通用复印机(B),操作系统(C),不涉及复制的额外功能 (D),以及编码所有自动机的单独描述 Φ(A,B,C,D)。ii)(上)通用构造函数从它们的描述中产生(解码)自动机(描述的主动模式);(下)Universal Copier 复制自动机的描述(被动描述方式);突变 Φ(D') 到描述 Φ(D)(不是自动机 D 的直接变化)传播到下一代产生的自动机集合,允许(自动机 + 描述)系统继续复制和进化(D → D')。从描述构建的主动过程与DNA 翻译相似,复制描述的被动过程与DNA 复制相似,突变描述的继承与生物学中 DNA 突变的垂直继承相似,由冯诺依曼在发现 DNA 分子的结构以及它如何在细胞中单独翻译和复制之前。

Von Neumann's design has traditionally been understood to be a demonstration of the logical requirements for machine self-replication.[3] However, it is clear that far simpler machines can achieve self-replication. Examples include trivial crystal-like growth, template replication, and Langton's loops. But von Neumann was interested in something more profound: construction, universality, and evolution.[4][5]

Von Neumann's design has traditionally been understood to be a demonstration of the logical requirements for machine self-replication. However, it is clear that far simpler machines can achieve self-replication. Examples include trivial crystal-like growth, template replication, and Langton's loops. But von Neumann was interested in something more profound: construction, universality, and evolution.

的设计传统上被理解为对机器自我复制的逻辑需求的论证。然而,很明显,更简单的机器可以达到自我复制。例子包括平凡的晶体样生长、模板复制和朗顿循环。但冯 · 诺依曼对更深奥的东西感兴趣: 构造、普遍性和进化。

【终译版】冯·诺依曼的设计传统上被理解为展示机器自我复制的逻辑要求。然而,很明显,更简单的机器可以实现自我复制。例子包括微不足道的晶体状生长、模板复制和兰顿环。但冯·诺依曼对更深刻的东西感兴趣:建构、普遍性和进化。

Note that the simpler self-replicating CA structures (especially, Byl's loop and the Chou–Reggia loop) cannot exist in a wide variety of forms and thus have very limited evolvability. Other CA structures such as the Evoloop are somewhat evolvable but still don't support open-ended evolution. Commonly, simple replicators do not fully contain the machinery of construction, there being a degree to which the replicator is information copied by its surrounding environment. Although the Von Neumann design is a logical construction, it is in principle a design that could be instantiated as a physical machine. Indeed, this universal constructor can be seen as an abstract simulation of a physical universal assembler. The issue of the environmental contribution to replication is somewhat open, since there are different conceptions of raw material and its availability.

Note that the simpler self-replicating CA structures (especially, Byl's loop and the Chou–Reggia loop) cannot exist in a wide variety of forms and thus have very limited evolvability. Other CA structures such as the Evoloop are somewhat evolvable but still don't support open-ended evolution. Commonly, simple replicators do not fully contain the machinery of construction, there being a degree to which the replicator is information copied by its surrounding environment. Although the Von Neumann design is a logical construction, it is in principle a design that could be instantiated as a physical machine. Indeed, this universal constructor can be seen as an abstract simulation of a physical universal assembler. The issue of the environmental contribution to replication is somewhat open, since there are different conceptions of raw material and its availability.

注意,更简单的自我复制 CA 结构(尤其是 Byl 循环和 Chou-Reggia 循环)不能以多种形式存在,因此可进化性非常有限。其他 CA 结构,比如 Evoloop 也是可进化的,但仍然不支持开放式进化。通常情况下,简单的复制因子并不完全包含构建机制,在一定程度上,复制因子是由其周围环境复制的信息。尽管冯 · 诺依曼设计是一个逻辑结构,但从原则上讲,它是一个可以被实例化为物理机器的设计。实际上,这个通用构造函数可以看作是对物理通用汇编程序的抽象模拟。由于对原材料及其可得性有不同的概念,环境对复制的贡献问题在某种程度上是开放的。

【终译版】请注意,更简单的自我复制 CA 结构(尤其是Byl 循环和Chou-Reggia 循环)不能以多种形式存在,因此可进化性非常有限。其他 CA 结构(例如Evoloop)在某种程度上是可进化的,但仍然不支持开放式进化。通常,简单的复制器不完全包含构造机械,复制器在一定程度上是被周围环境复制的信息。尽管冯诺依曼设计是一种逻辑结构,但原则上它是一种可以被实例化为物理机器的设计。事实上,这个通用构造器可以看作是对物理的抽象模拟万能汇编器。环境对复制的贡献问题有些开放,因为对原材料及其可用性有不同的概念。

Von Neumann's crucial insight is that the description of the machine, which is copied and passed to offspring separately via the universal copier, has a double use; being both an active component of the construction mechanism in reproduction, and being the target of a passive copying process. This part is played by the description (akin to Turing's tape of instructions) in Von Neumann's combination of universal constructor and universal copier.[4] The combination of a universal constructor and copier, plus a tape of instructions conceptualizes and formalizes i) self-replication, and ii) open-ended evolution, or growth of complexity observed in biological organisms.[3]

Von Neumann's crucial insight is that the description of the machine, which is copied and passed to offspring separately via the universal copier, has a double use; being both an active component of the construction mechanism in reproduction, and being the target of a passive copying process. This part is played by the description (akin to Turing's tape of instructions) in Von Neumann's combination of universal constructor and universal copier. The combination of a universal constructor and copier, plus a tape of instructions conceptualizes and formalizes i) self-replication, and ii) open-ended evolution, or growth of complexity observed in biological organisms.

冯 · 诺依曼的重要见解是,对机器的描述---- 通用复印机分别复制并传递给后代---- 具有双重用途: 既是繁殖过程中构建机制的主动部分,又是被动复制过程的目标。冯 · 诺依曼将通用构造函数和通用复印机结合在一起的描述(类似于图灵的指令磁带)扮演了这一角色。一个通用的构造器和复印器的组合,再加上一盘指令磁带,概念化和形式化了 i)自我复制,ii)开放式的进化,或者说在生物有机体中观察到的复杂性的增长。

【终译版】冯诺依曼的关键见解是机器的描述,通过通用复印机分别复制并传递给后代,具有双重用途;既是再生产中建构机制的主动组成部分,又是被动复制过程的目标。这部分是由描述(类似于发挥图灵的指令磁带)的通用构造和通用复印机的冯·诺依曼的组合。通用构造器和复制器的组合,加上一卷说明,将 i) 自我复制和 ii) 开放式进化或在生物有机体中观察到的复杂性增长概念化和形式化。

This insight is all the more remarkable because it preceded the discovery of the structure of the DNA molecule by Watson and Crick and how it is separately translated and replicated in the cell—though it followed the Avery–MacLeod–McCarty experiment which identified DNA as the molecular carrier of genetic information in living organisms.[6] The DNA molecule is processed by separate mechanisms that carry out its instructions (translation) and copy (replicate) the DNA for newly constructed cells. The ability to achieve open-ended evolution lies in the fact that, just as in nature, errors (mutations) in the copying of the genetic tape can lead to viable variants of the automaton, which can then evolve via natural selection.[4] As Brenner put it:

This insight is all the more remarkable because it preceded the discovery of the structure of the DNA molecule by Watson and Crick and how it is separately translated and replicated in the cell—though it followed the Avery–MacLeod–McCarty experiment which identified DNA as the molecular carrier of genetic information in living organisms. The DNA molecule is processed by separate mechanisms that carry out its instructions (translation) and copy (replicate) the DNA for newly constructed cells. The ability to achieve open-ended evolution lies in the fact that, just as in nature, errors (mutations) in the copying of the genetic tape can lead to viable variants of the automaton, which can then evolve via natural selection. As Brenner put it:

这一发现尤其引人注目,因为它先于沃森与克里克发现了 DNA 分子的结构,以及 DNA 分子在细胞中是如何分别翻译和复制的---- 尽管它遵循的是 Avery-MacLeod-McCarty 实验,该实验将 DNA 确定为活生物体中遗传信息的分子载体。DNA 分子通过不同的机制进行处理,为新构建的细胞执行其指令(翻译)和复制(复制) DNA。实现开放式进化的能力在于,就像在自然界一样,复制基因带时的错误(突变)可以导致自动机的可行变体,然后通过自然选择进化。正如布伦纳所言:

【终译版】这一见解更加引人注目,因为它先于Watson和Crick发现 DNA 分子的结构以及它如何在细胞中单独翻译和复制——尽管它遵循Avery-MacLeod-McCarty 实验,该实验将DNA确定为生物体内遗传信息的分子载体。 DNA 分子由执行其指令(翻译)和复制(复制)新构建细胞的 DNA的单独机制进行处理。实现开放式进化的能力在于,就像自然界一样,错误(突变) 在遗传磁带的复制中可以导致自动机的可行变体,然后可以通过自然选择进化。正如布伦纳所说:


Turing invented the stored-program computer, and von Neumann showed that the description is separate from the universal constructor. This is not trivial. Physicist Erwin Schrödinger confused the program and the constructor in his 1944 book What is Life?, in which he saw chromosomes as ″architect's plan and builder's craft in one″. This is wrong. The code script contains only a description of the executive function, not the function itself.

【终译版】图灵发明了存储程序计算机,冯诺依曼证明了描述与通用构造函数是分开的。这不是微不足道的。物理学家 Erwin Schrödinger 在其 1944 年的著作《生命是什么?这是错误的。代码脚本只包含对执行函数的描述,而不是函数本身。

— Sydney Brenner 悉尼布伦纳

Evolution of Complexity

复杂性的演变

Von Neumann's goal, as specified in his lectures at the University of Illinois in 1949,[2] was to design a machine whose complexity could grow automatically akin to biological organisms under natural selection. He asked what is the threshold of complexity that must be crossed for machines to be able to evolve and grow in complexity.[4][3] His “proof-of-principle” designs showed how it is logically possible. By using an architecture that separates a general purpose programmable (“universal”) constructor from a general purpose copier, he showed how the descriptions (tapes) of machines could accumulate mutations in self-replication and thus evolve more complex machines (the image below illustrates this possibility.). This is a very important result, as prior to that, it might have been conjectured that there is a fundamental logical barrier to the existence of such machines; in which case, biological organisms, which do evolve and grow in complexity, could not be “machines”, as conventionally understood. Von Neumann's insight was to think of life as a Turing Machine, which, is similarly defined by a state-determined machine "head" separated from a memory tape.[5]

Von Neumann's goal, as specified in his lectures at the University of Illinois in 1949, was to design a machine whose complexity could grow automatically akin to biological organisms under natural selection. He asked what is the threshold of complexity that must be crossed for machines to be able to evolve and grow in complexity. His “proof-of-principle” designs showed how it is logically possible. By using an architecture that separates a general purpose programmable (“universal”) constructor from a general purpose copier, he showed how the descriptions (tapes) of machines could accumulate mutations in self-replication and thus evolve more complex machines (the image below illustrates this possibility.). This is a very important result, as prior to that, it might have been conjectured that there is a fundamental logical barrier to the existence of such machines; in which case, biological organisms, which do evolve and grow in complexity, could not be “machines”, as conventionally understood. Von Neumann's insight was to think of life as a Turing Machine, which, is similarly defined by a state-determined machine "head" separated from a memory tape.

1949年,冯 · 诺依曼在伊利诺伊大学厄巴纳-香槟分校的演讲中明确指出,他的目标是设计一种机器,其复杂性可以自动增长,类似于自然选择下的生物有机体。他问,机器要想在复杂性中进化和成长,必须跨越多大的复杂性门槛。他的“原理证明”设计显示了这在逻辑上是可能的。通过使用一种将通用可编程构造器和通用复印机分离开来的架构,他展示了机器的描述(磁带)是如何在自我复制中累积突变,从而进化出更复杂的机器的(下图说明了这种可能性).这是一个非常重要的结果,因为在此之前,人们可能会推测,这种机器的存在有一个根本的逻辑障碍; 在这种情况下,确实进化和增长的复杂性的生物有机体,不可能是传统意义上的“机器”。冯 · 诺依曼的洞察力是把生命想象成一台图灵机,它同样被一台状态决定的机器“头”从一个记忆磁带中分离出来。

【终译版】正如 1949 年在伊利诺伊大学的演讲中所指出的,冯·诺依曼的目标是设计一种机器,其复杂性可以自动增长,类似于自然选择下的生物有机体。他询问机器必须跨越的复杂性阈值是什么,才能进化和增加复杂性。 他的“原理证明”设计展示了它在逻辑上的可能性。通过使用将通用可编程(“通用”)构造器与通用复制器分开的架构,他展示了机器的描述(磁带)如何在自我复制中积累突变,从而进化出更复杂的机器(下图说明这种可能性。)。这是一个非常重要的结果,因为在此之前,人们可能会推测这种机器的存在存在根本的逻辑障碍;在这种情况下,确实进化和复杂性增长的生物有机体不可能是传统意义上的“机器”。冯·诺依曼的见解是将生命视为一台图灵机,它同样由与存储磁带分离的状态确定的机器“磁头”定义。


In practice, when we consider the particular automata implementation Von Neumann pursued, we conclude that it does not yield much evolutionary dynamics because the machines are too fragile - the vast majority of perturbations cause them effectively to disintegrate.[3] Thus, it is the conceptual model outlined in his Illinois lectures[2] that is of greater interest today because it shows how a machine can in principle evolve.[7][4] This insight is all the more remarkable because the model preceded the discovery of the structure of the DNA molecule as discussed above.[6] It is also noteworthy that Von Neumann's design considers that mutations towards greater complexity need to occur in the (descriptions of) subsystems not involved in self-reproduction itself, as conceptualized by the additional automaton D he considered to perform all functions not directly involved in reproduction (see Figure above with Von Neumann's System of Self-Replication Automata with the ability to evolve.) Indeed, in biological organisms only very minor variations of the genetic code have been observed, which matches Von Neumann's rationale that the universal constructor (A) and Copier (B) would not themselves evolve, leaving all evolution (and growth of complexity) to automaton D.[4] In his unfinished work, Von Neumann also briefly considers conflict and interactions between his self-reproducing machines, towards understanding the evolution of ecological and social interactions from his theory of self-reproducing machines.[2]:147

In practice, when we consider the particular automata implementation Von Neumann pursued, we conclude that it does not yield much evolutionary dynamics because the machines are too fragile - the vast majority of perturbations cause them effectively to disintegrate. Thus, it is the conceptual model outlined in his Illinois lectures that is of greater interest today because it shows how a machine can in principle evolve. This insight is all the more remarkable because the model preceded the discovery of the structure of the DNA molecule as discussed above. It is also noteworthy that Von Neumann's design considers that mutations towards greater complexity need to occur in the (descriptions of) subsystems not involved in self-reproduction itself, as conceptualized by the additional automaton D he considered to perform all functions not directly involved in reproduction (see Figure above with Von Neumann's System of Self-Replication Automata with the ability to evolve.) Indeed, in biological organisms only very minor variations of the genetic code have been observed, which matches Von Neumann's rationale that the universal constructor (A) and Copier (B) would not themselves evolve, leaving all evolution (and growth of complexity) to automaton D. In his unfinished work, Von Neumann also briefly considers conflict and interactions between his self-reproducing machines, towards understanding the evolution of ecological and social interactions from his theory of self-reproducing machines.

在实践中,当我们考虑冯 · 诺依曼所追求的特定自动机实现时,我们得出结论,它不会产生太多的进化动力学,因为机器太脆弱了——绝大多数的扰动会导致它们有效地解体。因此,他在伊利诺伊州的演讲中概述的概念模型是今天人们更感兴趣的,因为它展示了机器原则上是如何进化的。这个发现更加引人注目,因为这个模型是在上面讨论的 DNA 分子结构被发现之前。值得注意的是,Von Neumann 的设计认为向着更高复杂性的突变需要发生在(描述)子系统中,而这些子系统本身并不涉及自我复制,这是由额外的自动机 d 来概念化的,他认为这些自动机执行所有不直接涉及复制的功能(见上面的图和 Von Neumann 的具有进化能力的自我复制自动机系统)事实上,在生物有机体中,只观察到遗传密码的微小变异,这与冯 · 诺依曼的理论基础相符,即通用构造器(a)和复印器(b)本身不会进化,将所有进化(和复杂性的增长)留给自动机 d。在他未完成的著作中,冯 · 诺依曼还简要地考虑了他的自我繁殖机器之间的冲突和相互作用,以便从他的自我繁殖机器理论中理解生态和社会相互作用的进化。

【终译版】在实践中,当我们考虑冯诺依曼所追求的特定自动机实现时,我们得出结论,它不会产生太多的进化动力学,因为机器太脆弱了——绝大多数扰动会导致它们有效地瓦解。因此,今天更令人感兴趣的是他在伊利诺伊州的讲座中概述的概念模型,因为它展示了机器在原则上是如何进化的。这种洞察力更加显着,因为该模型先于上述讨论的 DNA 分子结构的发现。还值得注意的是,冯诺依曼的设计认为,向更复杂的突变需要发生在不涉及自我复制本身的子系统(描述)中,正如他认为执行所有不直接参与复制的功能的附加自动机D概念化的那样(见上图与冯诺依曼的具有进化能力的自我复制自动机系统。)事实上,在生物有机体中,仅观察到遗传密码的非常微小的变化,这与冯诺依曼的基本原理相吻合,即通用构造函数(A)和复印机()不会自己发展,使所有的进化(和复杂性的增长),以自动d。在他未完成的作品中,冯诺依曼还简要考虑了他的自我复制机器之间的冲突和相互作用,以从他的自我复制机器理论中理解生态和社会互动的演变。

A demonstration of the ability of von Neumann's machine to support inheritable mutations. (1) At an earlier timestep, a mutation was manually added to the second generation machine's tape. (2) Later generations both display the phenotype of the mutation (a drawing of a flower) and pass the mutation on to their children, since the tape is copied each time. This example illustrates how von Neumann's design allows for complexity growth (in theory) since the tape could specify a machine that is more complex than the one making it. 【终译版】冯诺依曼机器支持可遗传突变的能力的演示。(1) 在较早的时间步,一个突变被手动添加到第二代机器的磁带中。(2) 后代都显示突变的表型(一朵花的图画)并将突变传给他们的孩子,因为每次都复制磁带。这个例子说明了冯诺依曼的设计如何允许复杂性增长(理论上),因为磁带可以指定一台比制造它的机器更复杂的机器。

Implementations

实现

In automata theory, the concept of a universal constructor is non-trivial because of the existence of 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 patterns. But a simple definition is that a universal constructor is able to construct any finite pattern of non-excited (quiescent) cells.

在自动机理论中,由于伊甸园模式的存在,普遍构造函数的概念是非平凡的。但一个简单的定义是,通用构造函数能够构造任何非激发(静止)细胞的有限模式。

【终译版】在自动机理论中,由于伊甸园模式的存在,通用构造函数的概念是不平凡的。但一个简单的定义是,通用构造函数能够构造任何有限模式的非兴奋(静止)细胞。

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.

亚瑟 · 伯克斯和其他人扩展了冯 · 诺依曼的工作,给出了一套更加清晰和完整的关于冯 · 诺依曼自复制因子的设计和操作的细节。撒切尔的工作尤其值得注意,因为他极大地简化了设计。尽管如此,他们的工作并没有产生一个完整的设计,一个细胞一个细胞的配置能够显示自我复制。

【终译版】Arthur Burks和其他人扩展了冯诺依曼的工作,给出了关于冯诺依曼自我复制器的设计和操作的更清晰和完整的细节。JW Thatcher 的作品尤其值得一提,因为他大大简化了设计。尽管如此,他们的工作并没有逐个单元地产生能够展示自我复制的配置的完整设计。

Renato Nobili and Umberto Pesavento published the first fully implemented self-reproducing cellular automaton in 1995, nearly fifty years after von Neumann's work.[1][8] They used a 32-state cellular automaton instead of von Neumann's original 29-state specification, extending it to allow for easier signal-crossing, explicit memory function and a more compact design. They also published an implementation of a general constructor within the original 29-state CA but not one capable of complete replication - the configuration cannot duplicate its tape, nor can it trigger its offspring; the configuration can only construct.[8][9]

Renato Nobili and Umberto Pesavento published the first fully implemented self-reproducing cellular automaton in 1995, nearly fifty years after von Neumann's work. They used a 32-state cellular automaton instead of von Neumann's original 29-state specification, extending it to allow for easier signal-crossing, explicit memory function and a more compact design. They also published an implementation of a general constructor within the original 29-state CA but not one capable of complete replication - the configuration cannot duplicate its tape, nor can it trigger its offspring; the configuration can only construct.

Renato Nobili 和 Umberto Pesavento 在1995年发表了第一个完全实现的自我复制细胞自动机,比 von Neumann 的工作晚了近50年。他们使用了32态细胞自动机,而不是冯诺依曼最初的29态规范,扩展了它,以便更容易的信号交叉,显式存储功能和更紧凑的设计。他们还发布了原始29状态 CA 中的一个通用构造函数的实现,但是没有一个能够完成复制——配置不能复制它的磁带,也不能触发它的后代; 配置只能构造。

【终译版】1995 年,Renato Nobili和 Umberto Pesavento 发表了第一个完全实现的自我复制元胞自动机,距冯·诺依曼的工作近 50 年。他们使用 32 状态元胞自动机代替冯诺依曼最初的29 状态规范,并对其进行了扩展,以实现更轻松的信号交叉、显式记忆功能和更紧凑的设计。他们还在最初的 29 状态 CA 中发布了一个通用构造函数的实现,但它不能完全复制——配置不能复制它的磁带,也不能触发它的后代;配置只能构造。

In 2004, D. Mange et al. reported an implementation of a self-replicator that is consistent with the designs of von Neumann.[10]

In 2004, D. Mange et al. reported an implementation of a self-replicator that is consistent with the designs of von Neumann.

In 2004, D. Mange et al.报道了一个与冯 · 诺依曼设计一致的自复制器的实现。

【终译版】2004 年,D. Mange 等人。报告了与冯诺依曼的设计一致的自我复制器的实现。

In 2007, Nobili published a 32-state implementation that uses run-length encoding to greatly reduce the size of the tape.[11]

In 2007, Nobili published a 32-state implementation that uses run-length encoding to greatly reduce the size of the tape.

2007年,Nobili 发布了一个包含32个州的实现方案,该方案使用游程编码来大大减小磁带的大小。

【终译版】2007 年,Nobili 发布了一个 32 状态的实现,它使用游程编码来大大减小磁带的大小。

In 2008, William R. Buckley published two configurations which are self-replicators within the original 29-state CA of von Neumann.[9] Buckley claims that the crossing of signal within von Neumann 29-state cellular automata is not necessary to the construction of self-replicators.[9] Buckley also points out that for the purposes of evolution, each replicator should return to its original configuration after replicating, in order to be capable (in theory) of making more than one copy. As published, the 1995 design of Nobili-Pesavento does not fulfill this requirement but the 2007 design of Nobili does; the same is true of Buckley's configurations.

In 2008, William R. Buckley published two configurations which are self-replicators within the original 29-state CA of von Neumann. Buckley claims that the crossing of signal within von Neumann 29-state cellular automata is not necessary to the construction of self-replicators. Buckley also points out that for the purposes of evolution, each replicator should return to its original configuration after replicating, in order to be capable (in theory) of making more than one copy. As published, the 1995 design of Nobili-Pesavento does not fulfill this requirement but the 2007 design of Nobili does; the same is true of Buckley's configurations.

2008年,威廉 · r · 巴克利发表了两个构型,它们是冯 · 诺依曼原始的29态 CA 中的自复制因子。巴克利认为,冯 · 诺依曼29态细胞自动机中的信号交叉对于自复制因子的构造是不必要的。巴克利还指出,出于进化的目的,每个复制因子在复制之后都应该返回到原来的结构,以便(理论上)能够复制多个副本。正如发表的,1995年的诺比利-佩斯旺托设计没有满足这一要求,但2007年的诺比利设计做到了,巴克利的配置也是如此。

【终译版】2008 年,威廉·R·巴克利 (William R. Buckley) 发表了两种配置,它们是冯·诺依曼最初的 29 州 CA 中的自我复制器。巴克利声称冯诺依曼 29 态元胞自动机内的信号交叉对于构建自我复制器不是必需的。巴克利还指出,为了进化的目的,每个复制器在复制后都应该恢复到原来的配置,以便能够(理论上)制造多个副本。正如发表的那样,1995 年的 Nobili-Pesavento 设计不满足这一要求,但 2007 年的 Nobili 设计却满足了这一要求。Buckley 的配置也是如此。

In 2009, Buckley published with Golly a third configuration for von Neumann 29-state cellular automata, which can perform either holistic self-replication, or self-replication by partial construction. This configuration also demonstrates that signal crossing is not necessary to the construction of self-replicators within von Neumann 29-state cellular automata.

In 2009, Buckley published with Golly a third configuration for von Neumann 29-state cellular automata, which can perform either holistic self-replication, or self-replication by partial construction. This configuration also demonstrates that signal crossing is not necessary to the construction of self-replicators within von Neumann 29-state cellular automata.

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. [12] [13]

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.

2002年,c. l. Nehaniv,还有 y. Takada 等人。2004年,提出了一个通用构造函数,它直接在异步细胞自动机上实现,而不是在同步细胞自动机上实现。

【终译版】2002 年的 CL Nehaniv,以及 Y. Takada 等人。2004年,提出了一种直接在异步元胞自动机上实现的通用构造函数,而不是在同步元胞自动机上实现。

Comparison of implementations

各实现间的比较

Implementation Source Ruleset Rectangular area Number of cells Length of tape Ratio Period Tape code compression Tape code length Tape code type Replication mechanism Replication type Growth rate
Nobili-Pesavento, 1995[1] 模板:CEmpty[14] Nobili 32-state 97 × 170 6,329 145,315 22.96 6.34模板:Times1010 模板:CNone 5 bits binary holistic constructor 模板:No2 linear
Nobili, 2007 SR_CCN_AP.EVN[11] Nobili 32-state 97 × 100 5,313 56,325 10.60 9.59模板:Times109 run-length limited encoding 5 bits binary holistic constructor 模板:Yes2 super-linear
Buckley, 2008 codon5.rle[15] Nobili 32-state 112 × 50 3,343 44,155 13.21 5.87模板:Times109 auto-retraction 5 bits binary holistic constructor 模板:Yes2 linear
Buckley, 2008[9] replicator.mc von Neumann 29-state 312 × 132 18,589 294,844 15.86 2.61模板:Times1011 auto-retraction 5 bits binary holistic constructor 模板:Yes2 linear
Buckley, 2008 codon4.rle[15] Nobili 32-state 109 × 59 3,574 37,780 10.57 4.31模板:Times109 auto-retraction/bit generation 4 bits binary holistic constructor 模板:Yes2 linear
Buckley, 2009 codon3.rle Nobili 32-state 116 × 95 4,855 23,577 4.86 1.63模板:Times109 auto-retraction/bit generation/code overlay 3 bits binary holistic constructor 模板:Yes2 super-linear
Buckley, 2009 PartialReplicator.mc[15] von Neumann 29-state 2063 × 377 264,321 模板:NA 模板:Sdash ≈1.12模板:Times1014 模板:CNone 4 bits binary partial constructor 模板:Yes2 linear
Goucher & Buckley, 2012 phi9.rle[16] Nobili 32-state 122 × 60 3957 8920 2.25 模板:Sdash auto-retraction/bit generation/code overlay/run length limited 3+ bits ternary holistic constructor 模板:Yes2 super-linear
Implementation Source Ruleset Rectangular area Number of cells Length of tape Ratio Period Tape code compression Tape code length Tape code type Replication mechanism Replication type Growth rate
Nobili-Pesavento, 1995 Nobili 32-state 97 × 170 6,329 145,315 22.96 6.341010 5 bits binary holistic constructor linear
Nobili, 2007 SR_CCN_AP.EVN Nobili 32-state 97 × 100 5,313 56,325 10.60 9.59109 run-length limited encoding 5 bits binary holistic constructor super-linear
Buckley, 2008 codon5.rle Nobili 32-state 112 × 50 3,343 44,155 13.21 5.87109 auto-retraction 5 bits binary holistic constructor linear
Buckley, 2008 replicator.mc von Neumann 29-state 312 × 132 18,589 294,844 15.86 2.611011 auto-retraction 5 bits binary holistic constructor linear
Buckley, 2008 codon4.rle Nobili 32-state 109 × 59 3,574 37,780 10.57 4.31109 auto-retraction/bit generation 4 bits binary holistic constructor linear
Buckley, 2009 codon3.rle Nobili 32-state 116 × 95 4,855 23,577 4.86 1.63109 auto-retraction/bit generation/code overlay 3 bits binary holistic constructor super-linear
Buckley, 2009 PartialReplicator.mc von Neumann 29-state 2063 × 377 264,321 ≈1.121014 4 bits binary partial constructor linear
Goucher & Buckley, 2012 phi9.rle Nobili 32-state 122 × 60 3957 8920 2.25 auto-retraction/bit generation/code overlay/run length limited 3+ bits ternary holistic constructor super-linear


【终译版】

执行 来源 规则集 矩形区域 细胞数 胶带长度 比率 时期 磁带编码压缩 带码长度 带码类型 复制机制 复制类型 增长率
诺比利-佩萨文托,1995 诺比利 32 州 97 × 170 6,329 145,315 22.96 6.34  ×  10 10 5 位 二进制 整体构造器 不可重复 线性的
诺比利, 2007 SR_CCN_AP.EVN 诺比利 32 州 97 × 100 5,313 56,325 10.60 9.59  ×  10 9 游程限制编码 5 位 二进制 整体构造器 可重复的 超线性
巴克利,2008 密码子5.rle 诺比利 32 州 112×50 3,343 44,155 13.21 5.87  ×  10 9 自动回缩 5 位 二进制 整体构造器 可重复的 线性的
巴克利,2008 复制器.mc 冯诺依曼 29 态 312 × 132 18,589 294,844 15.86 2.61  ×  10 11 自动回缩 5 位 二进制 整体构造器 可重复的 线性的
巴克利,2008 密码子4.rle 诺比利 32 州 109 × 59 3,574 37,780 10.57 4.31  ×  10 9 自动回退/位生成 4 位 二进制 整体构造器 可重复的 线性的
巴克利,2009 密码子3.rle 诺比利 32 州 116 × 95 4,855 23,577 4.86 1.63  ×  10 9 自动撤回/位生成/代码覆盖 3 位 二进制 整体构造器 可重复的 超线性
巴克利,2009 PartialReplicator.mc 冯诺依曼 29 态 2063 × 377 264,321 不适用 ≈1.12  ×  10 14 4 位 二进制 部分构造函数 可重复的 线性的
古彻和巴克利,2012 phi9.rle 诺比利 32 州 122×60 3957 8920 2.25 自动撤回/位生成/代码覆盖/运行长度限制 3+ 位 三元 整体构造器 可重复的 超线性

As defined by von Neumann, universal construction entails the construction of passive configurations, only. As such, the concept of universal construction constituted nothing more than a literary (or, in this case, mathematical) device. It facilitated other proof, such as that a machine well constructed may engage in self-replication, while universal construction itself was simply assumed over a most minimal case. Universal construction under this standard is trivial. Hence, while all the configurations given here can construct any passive configuration, none can construct the real-time crossing organ devised by Gorman.[9]

As defined by von Neumann, universal construction entails the construction of passive configurations, only. As such, the concept of universal construction constituted nothing more than a literary (or, in this case, mathematical) device. It facilitated other proof, such as that a machine well constructed may engage in self-replication, while universal construction itself was simply assumed over a most minimal case. Universal construction under this standard is trivial. Hence, while all the configurations given here can construct any passive configuration, none can construct the real-time crossing organ devised by Gorman.

正如冯 · 诺依曼所定义的,宇宙结构只需要被动构型的结构。因此,普遍建构的概念只不过是一种文学(或者,在这里,是数学)手段。它促进了其他的证明,如一个机器构造良好可能参与自我复制,而通用建设本身只是假定在最小的情况下。在这个标准下,通用结构是微不足道的。因此,虽然这里给出的所有构型都可以构造任何被动构型,但没有一种构型可以构造戈尔曼设计的实时交叉器官。

【终译版】正如冯诺依曼所定义的,通用构造只需要构造被动配置。因此,普遍建构的概念只不过是一种文学(或者,在这种情况下,是数学)装置。它促进了其他证明,例如构造良好的机器可能会进行自我复制,而通用构造本身只是假设在最小的情况下。此标准下的通用构造是微不足道的。因此,虽然这里给出的所有配置都可以构建任何被动配置,但没有一个可以构建 Gorman 设计的实时交叉器官。

实用性和计算成本

All the implementations of von Neumann's self-reproducing machine require considerable resources to run on computer. For example, in the Nobili-Pesavento 32-state implementation shown above, while the body of the machine is just 6,329 non-empty cells (within a rectangle of size 97x170), it requires a tape that is 145,315 cells long, and takes 63 billion timesteps to replicate. A simulator running at 1,000 timesteps per second would take over 2 years to make the first copy. In 1995, when the first implementation was published, the authors had not seen their own machine replicate. However, in 2008, the hashlife algorithm was extended to support the 29-state and 32-state rulesets in Golly. On a modern desktop PC, replication now takes only a few minutes, although a significant amount of memory is required.

All the implementations of von Neumann's self-reproducing machine require considerable resources to run on computer. For example, in the Nobili-Pesavento 32-state implementation shown above, while the body of the machine is just 6,329 non-empty cells (within a rectangle of size 97x170), it requires a tape that is 145,315 cells long, and takes 63 billion timesteps to replicate. A simulator running at 1,000 timesteps per second would take over 2 years to make the first copy. In 1995, when the first implementation was published, the authors had not seen their own machine replicate. However, in 2008, the hashlife algorithm was extended to support the 29-state and 32-state rulesets in Golly. On a modern desktop PC, replication now takes only a few minutes, although a significant amount of memory is required.

冯 · 诺依曼的自复制机的所有实现都需要相当多的资源才能在计算机上运行。例如,在上面显示的 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 上,复制现在只需几分钟,尽管需要大量内存。

动画画廊

Example of a 29-state read arm. 来自维基百科

Example of a 29-state read arm.

【终译版】29 状态读取臂的示例。

关联条目

参考文献

  1. 1.0 1.1 1.2 Pesavento, Umberto (1995), "An implementation of von Neumann's self-reproducing machine" (PDF), Artificial Life, MIT Press, 2 (4): 337–354, doi:10.1162/artl.1995.2.337, PMID 8942052, archived from the original (PDF) on June 21, 2007
  2. 2.0 2.1 2.2 2.3 2.4 2.5 2.6 von Neumann, John; Burks, Arthur W. (1966), Theory of Self-Reproducing Automata. (Scanned book online), University of Illinois Press, retrieved 2017-02-28
  3. 3.0 3.1 3.2 3.3 3.4 3.5 McMullin, B. (2000), "John von Neumann and the Evolutionary Growth of Complexity: Looking Backwards, Looking Forwards...", Artificial Life, 6 (4): 347–361, doi:10.1162/106454600300103674, PMID 11348586, S2CID 5454783
  4. 4.00 4.01 4.02 4.03 4.04 4.05 4.06 4.07 4.08 4.09 4.10 4.11 4.12 4.13 4.14 Rocha, Luis M. (1998), "Selected self-organization and the semiotics of evolutionary systems", Evolutionary Systems, Springer, Dordrecht: 341–358, doi:10.1007/978-94-017-1510-2_25, ISBN 978-90-481-5103-5
  5. 5.0 5.1 5.2 5.3 5.4 5.5 5.6 Brenner, Sydney (2012), "Life's code script", Nature, 482 (7386): 461, doi:10.1038/482461a, PMID 22358811, S2CID 205070101
  6. 6.0 6.1 6.2 6.3 Rocha, Luis M. (2015), "Chapter 6. Von Neumann and Natural Selection." (PDF), Lecture Notes of I-485-Biologically Inspired Computing Course, Indiana University (PDF)
  7. Pattee, Howard, H. (1995), "Evolving self-reference: matter symbols, and semantic closure", Communication and Cognition Artificial Intelligence, Biosemiotics, 12 (1–2): 9–27, doi:10.1007/978-94-007-5161-3_14, ISBN 978-94-007-5160-6
  8. 8.0 8.1 Nobili, Renato; Pesavento, Umberto (1996), "Generalised von Neumann's Automata", in Besussi, E.; Cecchini, A. (eds.), Proc. Artificial Worlds and Urban Studies, Conference 1 (PDF), Venice: DAEST
  9. 9.0 9.1 9.2 9.3 9.4 Buckley, William R. (2008), "Signal Crossing Solutions in von Neumann Self-replicating Cellular Automata", in Andrew Adamatzky; Ramon Alonso-Sanz; Anna Lawniczak; Genaro Juarez Martinez; Kenichi Morita; Thomas Worsch (eds.), Proc. Automata 2008 (PDF), Luniver Press, pp. 453–503
  10. Mange, Daniel; Stauffer, A.; Peparaolo, L.; Tempesti, G. (2004), "A Macroscopic View of Self-replication", Proceedings of the IEEE, 92 (12): 1929–1945, doi:10.1109/JPROC.2004.837631, S2CID 22500865
  11. 11.0 11.1 Nobili, Renato (2007). "The Cellular Automata of John von Neumann". Archived from the original on January 29, 2011. Retrieved January 29, 2011.
  12. Nehaniv, Chrystopher L. (2002), "Self-Reproduction in Asynchronous Cellular Automata", 2002 NASA/DoD Conference on Evolvable Hardware (15-18 July 2002, Alexandria, Virginia, USA), IEEE Computer Society Press, pp. 201–209
  13. Takada, Yousuke; Isokawa, Teijiro; Peper, Ferdinand; Matsui, Nobuyuki (2004), "Universal Construction on Self-Timed Cellular Automata", in Sloot, P.M.A. (ed.), ACRI 2004, LNCS 3305, pp. 21–30
  14. "Von Neumann's Self-Reproducing Universal Constructor".
  15. 15.0 15.1 15.2 andykt. "Golly, a Game of Life simulator". SourceForge.
  16. "Self-replication". Complex Projective 4-Space.

外部链接

  • Golly - the Cellular Automata Simulation Accelerator Very fast implementation of state transition and support for JvN, GoL, Wolfram, and other systems.
  • von Neumann's Self-Reproducing Universal Constructor The original Nobili-Pesavento source code, animations and Golly files of the replicators.
  • John von Neumann's 29 state Cellular Automata Implemented in OpenLaszlo by Don Hopkins
  • A Catalogue of Self-Replicating Cellular Automata. This catalogue complements the Proc. Automata 2008 volume.
  • 【终译版】
  • Golly-细胞自动机模拟加速器状态转换的快速实现,并支持 jvm、 GoL、 Wolfram 和其他系统。
  • 冯 · 诺依曼的自复制通用构造器原始的 Nobili-Pesavento 源代码、动画和复制器的 Golly 文件。
  • Don Hopkins 在 OpenLaszlo 中实现的约翰·冯·诺伊曼29态元胞自动机
  • 自我复制元胞自动机目录。本目录补充了本程序。自动化2008卷。
  • Golly - 元胞自动机模拟加速器非常快速地实现状态转换并支持 JvN、GoL、Wolfram 和其他系统。
  • von Neumann 的自我复制通用构造器 复制器的原始 Nobili-Pesavento 源代码、动画和 Golly 文件。
  • John von Neumann 的 29 状态元胞自动机在 OpenLaszlo 中实现,由Don Hopkins
  • 自复制元胞自动机目录。 该目录是对Proc 的补充。自动机 2008卷。