3,094
个编辑
更改
跳到导航
跳到搜索
第315行：
第315行： + + + + 第377行：
第381行： +
→推论：SRT 衍生出的若干重要结果
——按规则展开后，这个短语恰好指称'''它自己'''<ref name="rogers1967" /><ref name="moschovakis2010" />。
——按规则展开后，这个短语恰好指称'''它自己'''<ref name="rogers1967" /><ref name="moschovakis2010" />。
=== 其它形式的第二递归定理 ===
====带参数的形式====
====uniform====
=== 推论：SRT 衍生出的若干重要结果 ===
=== 推论：SRT 衍生出的若干重要结果 ===
[[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>
。
。
=== λ演算视角：与 Y 组合子的关系 ===
=== λ演算视角：与 Y 组合子的关系 ===