3,094
个编辑
更改
跳到导航
跳到搜索
第751行：
第751行： − − ===== Rice-Shapiro 定理（1956） ===== − − Rice 定理回答"'''能否'''判定"；[[莱斯-夏皮罗定理|Rice-Shapiro 定理]]进一步刻画"'''何时能半判定'''"——把注意力从"A 是否可计算"收窄到"A 自身何时是 r.e. 的"： − − 设 <math>A = \{ e :W_e \in \mathcal{A}\}</math> 是索引集。<math>A</math> 是 r.e. 的，'''当且仅当''' <math>\mathcal{A}</math> 是"有限可生成"的：存在一个可计算列举的有限集列 <math>\mathcal{S} = \{S_0,S_1,S_2,\ldots</math>}，使得 <math>W\in \mathcal{A}</math> ⟺ <math>\mathcal{S}</math>中存在某个 <math>S_i \subseteq W</math>。 − − 含义：一个行为性质若能'''被枚举地识别'''（索引集 r.e.），它就必须由'''有限证据'''决定——W 一旦包含某个预列的有限集 <math>S_i</math>，性质即成立；反之，性质成立也只需某个有限子集作证。"能识别 ⟹ 只依赖有限信息"这一半是紧致性式的论证（若性质的成立只靠无限多证据，枚举过程就永远等不到决定性的一刻）；"有限可生成 ⟹ 可枚举"那一半是直接列举。两个方向都与 SRT 无关。 − − Rice-Shapiro 不是 SRT 的推论，而是索引集理论中独立的结构定理，并且它比 Rice 定理更强——由它可以推出 Rice 定理：若非平凡索引集 A 可计算，则 A 与补集都是 r.e. 索引集，Rice-Shapiro 给 <math>\mathcal{A}</math> 与其补类都套上"有限可生成"；而有限可生成自动蕴含"超集仍在类中"，把两个类里各自的成员并起来，就得到同时属于两类的一个 r.e. 集，矛盾。可见在"识别程序性质"的问题上，真正的母定理是 Rice-Shapiro 而非 SRT<ref name="rogers1967" /><ref name="soare1987" />。
→Rice-Shapiro 定理（1956）
'''注（SRT 捷径，非本质）'''：[[莱斯定理|Rice 定理]]也可用 SRT 三行证完：设 <math>A</math> 可计算，取变换规则 <math>f(x) =</math>"<math>x\in A</math> 时给一个 <math>\notin A</math> 的编号，否则给一个 <math>\in A</math> 的编号"（A 非空非全，顺序搜索即可机械实现），SRT 给出不动点 <math>m</math> 使 <math>\phi_m = \phi_{f(m)}</math>。若 <math>m\in A</math>，则 <math>f(m)\notin A</math>，同一函数 <math>\phi_m = \phi_{f(m)}</math> 却一个在 A 内、一个在 A 外（索引集只看行为），矛盾；<math>m\notin A</math> 同理。这条证明虽短，却是'''事后捷径'''——它没有揭示 Rice 定理与停机问题的血缘，而后者（上面的归约）才是定理的标准证明与本质机制<ref name="rogers1967" />。
'''注（SRT 捷径，非本质）'''：[[莱斯定理|Rice 定理]]也可用 SRT 三行证完：设 <math>A</math> 可计算，取变换规则 <math>f(x) =</math>"<math>x\in A</math> 时给一个 <math>\notin A</math> 的编号，否则给一个 <math>\in A</math> 的编号"（A 非空非全，顺序搜索即可机械实现），SRT 给出不动点 <math>m</math> 使 <math>\phi_m = \phi_{f(m)}</math>。若 <math>m\in A</math>，则 <math>f(m)\notin A</math>，同一函数 <math>\phi_m = \phi_{f(m)}</math> 却一个在 A 内、一个在 A 外（索引集只看行为），矛盾；<math>m\notin A</math> 同理。这条证明虽短，却是'''事后捷径'''——它没有揭示 Rice 定理与停机问题的血缘，而后者（上面的归约）才是定理的标准证明与本质机制<ref name="rogers1967" />。
===== [[Myhill定理]]：[[创造集]] = [[完备集]] =====
===== [[Myhill定理]]：[[创造集]] = [[完备集]] =====