3,094
个编辑
更改
跳到导航
跳到搜索
第675行：
第675行： − + − + − +
→Myhill定理：创造集 = 完备集
==== [[Myhill定理]]：[[创造集]] = [[完备集]] ====
==== [[Myhill定理]]：[[创造集]] = [[完备集]] ====
'''背景'''：停机问题集合 <math>K = \{e : \text{程序} e \text{在输入} e \text{上停机}\}</math> 是 r.e. 集中"最不可判定"的——任何 r.e. 集都能通过可计算的翻译归约到它（称为 '''[[r.e.-完备|递归可枚举完备]]'''，complete）。另有一个看似完全不同的概念：一个 r.e. 集 A 称为'''[[创造集]]]（creative set）'''，如果它的补集是"能系统地生产反例"的——存在一个可计算程序，你给它任何与 A 不交的 r.e. 集，它都能吐出一个既不在 A 里也不在那个集合里的元素。创造性是 Post 1944 年为刻画"不可判定的源泉"而引入的概念。
'''背景'''：停机问题集合 <math>K = \{e : \text{程序} e \text{在输入} e \text{上停机}\}</math> 是 r.e. 集中"最不可判定"的——任何 r.e. 集都能通过可计算的翻译归约到它（称为 [[r.e.-完备|递归可枚举完备]]）。另有一个看似完全不同的概念：一个 r.e. 集 A 称为'''[[创造集]]（creative set）'''，如果它的补集是"能系统地生产反例"的——存在一个可计算程序，你给它任何与 A 不交的 r.e. 集，它都能吐出一个既不在 A 里也不在那个集合里的元素。创造性是 Post在1944 年为刻画"不可判定的源泉"而引入的概念。
* '''定理（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，需要构造一个程序 z，使得"若 x <math>\in B</math>，则 z 枚举出 {u(z)}；否则 z 枚举空集"——'''z 的定义里用到了 z 自己的编号'''（u(z) 是生产反例的程序作用于 z）。这正是 SRT 合法化的自指；没有这个自指，证明无法闭合。由此 Rogers 还得到推论：'''所有创造集在"可计算的重新命名"意义下完全相同（两两递归同构）'''——从可计算性角度看它们"长得一模一样"<ref name="rogers1967" />。
'''证明中 SRT 的关键一步'''：想把任意 r.e. 集 B 归约到创造集 A，需要构造一个程序 z，使得"若 x <math>\in B</math>，则 z 枚举出<math>\{u(z)\}</math>；否则 z 枚举空集"——'''z 的定义里用到了 z 自己的编号'''（<math>u(z)</math> 是生产反例的程序作用于 z）。这正是 SRT 合法化的自指；没有这个自指，证明无法闭合。由此 Rogers 还得到推论：'''所有创造集在"可计算的重新命名"意义下完全相同（两两递归同构）'''——从可计算性角度看它们"长得一模一样"<ref name="rogers1967" />。
=== 有效运算的连续性：Myhill–Shepherdson 与 KLS–Čeĭnin 定理 ===
=== 有效运算的连续性：Myhill–Shepherdson 与 KLS–Čeĭnin 定理 ===