3,094
个编辑
更改
跳到导航
跳到搜索
第758行：
第758行： − +
→Myhill定理：创造集 = 完备集
* '''[[Myhill定理]]（Myhill 1955）'''：每个创造集都是 r.e.-完备的；两个概念重合<ref name="myhill1955">Myhill, J., & Shepherdson, J. C. (1955). Effective operations on partial recursive functions. ''Zeitschrift für mathematische Logik und Grundlagen der Mathematik'', 1, 310–317.</ref><ref name="rogers1967" /><ref name="moschovakis2010" />.
* '''[[Myhill定理]]（Myhill 1955）'''：每个创造集都是 r.e.-完备的；两个概念重合<ref name="myhill1955">Myhill, J., & Shepherdson, J. C. (1955). Effective operations on partial recursive functions. ''Zeitschrift für mathematische Logik und Grundlagen der Mathematik'', 1, 310–317.</ref><ref name="rogers1967" /><ref name="moschovakis2010" />.
'''证明中 SRT 的关键一步'''：想把任意 r.e. 集 B 归约到创造集 A，需要构造一个程序 <math>z</math>，使得"若 <math>x\in B</math>，则 <math>z</math> 枚举出<math>\{u(z)\}</math>；否则 <math>z</math> 枚举空集"——'''<math>z</math> 的定义里用到了 <math>z</math> 自己的编号'''（<math>u(z)</math> 是生产反例的程序作用于 <math>z</math>）。这正是 SRT 合法化的自指；没有这个自指，证明无法闭合。由此 Rogers 还得到推论：'''所有创造集在"可计算的重新命名"意义下完全相同（两两递归同构）'''——从可计算性角度看它们"长得一模一样"<ref name="rogers1967" />。
'''证明中用到了 SRT 的关键一步'''：想把任意 r.e. 集 B 归约到创造集 A，需要构造一个程序 <math>z</math>，使得"若 <math>x\in B</math>，则 <math>z</math> 枚举出<math>\{u(z)\}</math>；否则 <math>z</math> 枚举空集"——'''<math>z</math> 的定义里用到了 <math>z</math> 自己的编号'''（<math>u(z)</math> 是生产反例的程序作用于 <math>z</math>）。这正是 SRT 合法化的自指；没有这个自指，证明无法闭合。由此 Rogers 还得到推论：'''所有创造集在"可计算的重新命名"意义下完全相同（两两递归同构）'''——从可计算性角度看它们"长得一模一样"<ref name="rogers1967" />。
==== 有效运算的连续性：Myhill–Shepherdson 与 KLS–Čeĭnin 定理 ====
==== 有效运算的连续性：Myhill–Shepherdson 与 KLS–Čeĭnin 定理 ====