更改

==== [[冯诺伊曼]]的[[自复制自动机]]（1948） ====

==== [[冯诺伊曼]]的[[自复制自动机]]（1948） ====

'''现象'''：存在能在物理上[[自复制自动机]]。[[冯诺伊曼]]在[[洛斯阿拉莫斯实验室]]设计的自动机方案含四部分：'''通用构造器 A'''（读入一段指令，构造出该指令描述的任何机器）、'''通用拷贝器 B'''（复制指令）、'''控制器 C'''（指挥 A 与 B 协同运作、并把指令传给新机器）、以及一段描述 A、B、C 三者如何组合的'''蓝图'''（即指令带）；机器 M<math> = \langle</math> A, B, C, 蓝图<math>\rangle</math> 启动后能造出 M 自己的副本<ref name="vonneumann1966">'''von Neumann, J. (1966).''' ''Theory of Self-Reproducing Automata'' (A. W. Burks 编). University of Illinois Press.【自复制自动机的奠基性设计（原稿始于 1948）】【§[[#冯诺伊曼的自复制自动机（1948）|5.7.5]]】</ref><ref name="lee1963">'''Lee, C. Y. (1963).''' A Turing machine which prints its own tape. ''Mathematical Tables and Other Aids to Computation'', 17, 403–406.【Rogers 1967 §11.4 第三图示的直接启发】</ref>。

早在20世纪40年代，[[冯诺伊曼]]就开始思考一个问题，是否能在物理上构建一台自复制的自动机器。为了回答这个问题，冯诺伊曼采纳了其好友——数学家[[乌拉姆]]（Stan Ulam）的建议，开始在一个具有29个状态的二维元胞自动机上构建这样的虚拟机器，这就是冯诺伊曼的[[自复制自动机]]。这台机器的设计方案含四部分：'''通用构造器 A'''（读入一段指令，构造出该指令描述的任何机器）、'''通用拷贝器 B'''（复制指令）、'''控制器 C'''（指挥 A 与 B 协同运作、并把指令传给新机器）、以及一段描述 A、B、C 三者如何组合的'''蓝图'''（即指令带）；机器 M<math> = \langle</math> A, B, C, 蓝图<math>\rangle</math> 启动后能造出 M 自己的副本<ref name="vonneumann1966">'''von Neumann, J. (1966).''' ''Theory of Self-Reproducing Automata'' (A. W. Burks 编). University of Illinois Press.【自复制自动机的奠基性设计（原稿始于 1948）】【§[[#冯诺伊曼的自复制自动机（1948）|5.7.5]]】</ref><ref name="lee1963">'''Lee, C. Y. (1963).''' A Turing machine which prints its own tape. ''Mathematical Tables and Other Aids to Computation'', 17, 403–406.【Rogers 1967 §11.4 第三图示的直接启发】</ref>。

'''SRT 如何推出它'''：

'''SRT 如何推出它'''：

* '''定理（自复制图灵机）'''：存在一台[[图灵机]]，从空白纸带出发，停机时纸带上恰好写着'''它自己的完整描述（转移表）'''<ref name="moschovakis2010" />。

* '''定理（自复制图灵机）'''：存在一台[[图灵机]]，从空白纸带出发，停机时纸带上恰好写着'''它自己的完整描述（转移表）'''<ref name="moschovakis2010" />。

* 证明思路是 SRT 的典型用法：定义 <math>\psi(z)</math> = "把编号 <math>z</math> 的机器的描述打印出来"——一个完全机械、与"谁被打印"无关的变换。SRT 给出不动点 <math>f</math>：程序 <math>f</math> 的行为 = 打印 <math>f</math> 自己的描述。循环凭空闭合。

* 证明思路是 SRT 的典型用法：定义 <math>\psi(z)</math> = "把编号 <math>z</math> 的机器的描述打印出来"——这是一个完全机械、与"谁被打印"无关的变换，因此可以套用SRT。SRT 给出不动点 <math>f</math>：程序 <math>f</math> 的行为 = 打印 <math>f</math> 自己的描述。循环凭空闭合。

Rogers 给出更一般的框架：'''只要存在一台"通用建造机"（即 von Neumann 的 A 的抽象——给蓝图就造机器），就必存在一台机器，无论输入什么都造出自己的副本'''<ref name="rogers1967" />。这直接驳倒了"自复制不可能"的谬误论证（"复制需要蓝图，蓝图又需要蓝图的蓝图，无穷倒退"）：SRT 表明系统能用'''有限'''指令闭合这个回环<ref name="rogers1967" />。

Rogers 给出更一般的框架：'''只要存在一台"通用建造机"（即 von Neumann 的 A 的抽象——给蓝图就造机器），就必存在一台机器，无论输入什么都造出自己的副本'''<ref name="rogers1967" />。这直接驳倒了"自复制不可能"的谬误论证（"复制需要蓝图，蓝图又需要蓝图的蓝图，无穷倒退"）：SRT 表明系统能用'''有限'''指令闭合这个回环<ref name="rogers1967" />。