3,094
个编辑
更改
跳到导航
跳到搜索
第232行：
第232行： − +
→Arslanov 完全性判据（1981）
直觉上：[[R. R. Arslanov|Arslanov]] 判据说"装得下所有 r.e. 集合"等价于"对每个 r.e. 集合都有机械的相对化方式"——这和 SRT 中"对每个全可计算 <math>f</math> 都给出一个不动点"的相对化版本（relativized SRT）说的是同一件事：SRT 的相对化是说"对每个以 <math>C</math> 为'''神谕'''（oracle）可计算的 <math>f</math>，存在不动点 <math>c</math>"；Arslanov 判据说"对每个 <math>W</math>，存在以 <math>C</math> 为[[谕示机|神谕]]可计算的归约"。
直觉上：[[R. R. Arslanov|Arslanov]] 判据说"装得下所有 r.e. 集合"等价于"对每个 r.e. 集合都有机械的相对化方式"——这和 SRT 中"对每个全可计算 <math>f</math> 都给出一个不动点"的相对化版本（relativized SRT）说的是同一件事：SRT 的相对化是说"对每个以 <math>C</math> 为'''神谕'''（oracle）可计算的 <math>f</math>，存在不动点 <math>c</math>"；Arslanov 判据说"对每个 <math>W</math>，存在以 <math>C</math> 为[[谕示机|神谕]]可计算的归约"。
[[Arslanov 判据]]在[[递归论]]里是教科书级工具：①用于证明 Gödel 不完备定理的算术陈述（"[[PA不一致]]"这种陈述）的相对可计算性与停机问题同构；② 用于证明某些 r.e. 集"不可能被简化"<ref name="arslanov1981">'''Arslanov, R. R. (1981).''' On a class of recursively enumerable sets. ''Algebra and Logic'', 20, 324–328.【Arslanov 完全性判据】【§[[Arslanov 完全性判据（1981）|5.2.3]]】</ref><ref name="soare1987">'''Soare, R. I. (1987).''' ''Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets''. Berlin: Springer-Verlag.【r.e. 集与图灵度的标准教科书；Arslanov 完备性判据（§[[Arslanov 完全性判据（1981）|5.2.3]]）与 Rice–Shapiro 等索引集定理（§[[r.e. 索引集理论：Rice、Rice-Shapiro 与 Myhill|5.8.5]]）的教科书出处】</ref>
[[Arslanov 判据]]在[[递归论]]里是教科书级工具：①用于证明 Gödel 不完备定理的算术陈述（"[[PA不一致]]"这种陈述）的相对可计算性与停机问题同构；② 用于证明某些 r.e. 集"不可能被简化"<ref name="arslanov1981">'''Arslanov, R. R. (1981).''' On a class of recursively enumerable sets. ''Algebra and Logic'', 20, 324–328.【Arslanov 完全性判据】【§[[#Arslanov 完全性判据（1981）|5.2.3]]】</ref><ref name="soare1987">'''Soare, R. I. (1987).''' ''Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets''. Berlin: Springer-Verlag.【r.e. 集与图灵度的标准教科书；Arslanov 完备性判据（§[[#Arslanov 完全性判据（1981）|5.2.3]]）与 Rice–Shapiro 等索引集定理（§[[#r.e. 索引集理论：Rice、Rice-Shapiro 与 Myhill|5.8.5]]）的教科书出处】</ref>
。
。