更改
跳到导航
跳到搜索
←上一编辑
下一编辑→
递归定理
(查看源代码)
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
个编辑
导航菜单
个人工具
登录
名字空间
页面
讨论
变种
视图
阅读
查看源代码
查看历史
更多
搜索
导航
集智百科
集智主页
集智斑图
集智学园
最近更改
所有页面
捐赠我们
帮助
工具
特殊页面
可打印版本