打开主菜单
首页
随机
登录
设置
关于集智百科 - 复杂系统|人工智能|复杂科学|复杂网络|自组织
免责声明
集智百科 - 复杂系统|人工智能|复杂科学|复杂网络|自组织
搜索
更改
←上一编辑
下一编辑→
递归定理
(查看源代码)
2026年9月9日 (三) 10:36的版本
添加60字节
、
2026年9月9日 (星期三)
→冯诺伊曼的自复制自动机(1948)
第499行:
第499行:
* '''定理(自复制图灵机)''':存在一台[[图灵机]],从空白纸带出发,停机时纸带上恰好写着'''它自己的完整描述(转移表)'''<ref name="moschovakis2010" />。
* '''定理(自复制图灵机)''':存在一台[[图灵机]],从空白纸带出发,停机时纸带上恰好写着'''它自己的完整描述(转移表)'''<ref name="moschovakis2010" />。
−
证明是
SRT 的典型用法:定义 <math>\psi(z)</math> = "把编号 z 的机器的描述打印出来"——一个完全机械、与"谁被打印"无关的变换。SRT 给出不动点
f:程序
f 的行为 = 打印 f 自己的描述。循环凭空闭合。
+
* 证明思路是
SRT 的典型用法:定义 <math>\psi(z)</math> = "把编号
<math>
z
</math>
的机器的描述打印出来"——一个完全机械、与"谁被打印"无关的变换。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" />
。


Jake
行政员
、
界面管理员
、
管理员
3,094
个编辑