3,094
个编辑
更改
→冯诺伊曼的自复制自动机（1948）
==== [[冯诺伊曼]]的[[自复制自动机]]（1948） ====
==== [[冯诺伊曼]]的[[自复制自动机]]（1948） ====
[[文件:冯诺伊曼的自复制自动机的工作原理.png|缩略图|'''图4'''：自复制机的闭合回路——机器 M 的蓝图描述了 M 的全部部件（构造器 A、拷贝器 B、控制器 C）；启动后 A 读蓝图 <math>\to </math>造出 M 的新副本、B 复制蓝图、C 把它们组装起来。SRT 保证存在这样的蓝图，让有限指令即可闭合循环（驳斥了"蓝图之蓝图无穷倒退"的谬误）。]]
早在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>。
早在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>。
Rogers 给出更一般的框架：'''只要存在一台"通用建造机"（即 von Neumann 的 A 的抽象——给蓝图就造机器），就必存在一台机器，无论输入什么都造出自己的副本'''<ref name="rogers1967" />。这直接驳倒了"自复制不可能"的谬误论证（"复制需要蓝图，蓝图又需要蓝图的蓝图，无穷倒退"）：SRT 表明系统能用'''有限'''指令闭合这个回环<ref name="rogers1967" />。
Rogers 给出更一般的框架：'''只要存在一台"通用建造机"（即 von Neumann 的 A 的抽象——给蓝图就造机器），就必存在一台机器，无论输入什么都造出自己的副本'''<ref name="rogers1967" />。这直接驳倒了"自复制不可能"的谬误论证（"复制需要蓝图，蓝图又需要蓝图的蓝图，无穷倒退"）：SRT 表明系统能用'''有限'''指令闭合这个回环<ref name="rogers1967" />。
==== Quine（自打印程序） ====
==== Quine（自打印程序） ====