'''[[Turing跳跃]](Turing jump)''':对任何集合 A,把"哪些以 A 为神谕的程序会停机"这一问题本身收集成一个集合,记作 A′(读作"A 撇")。可以证明:A′ 以 A 为神谕仍不可计算——每跳一次,都得到一个严格更难的"相对版停机问题"。特别地,从空集 <math>\emptyset</math> 出发跳一次得到的 <math>\emptyset'</math>,正是通常意义下的停机问题([[#图灵停机问题(1936)|5.7.3]])。 | '''[[Turing跳跃]](Turing jump)''':对任何集合 A,把"哪些以 A 为神谕的程序会停机"这一问题本身收集成一个集合,记作 A′(读作"A 撇")。可以证明:A′ 以 A 为神谕仍不可计算——每跳一次,都得到一个严格更难的"相对版停机问题"。特别地,从空集 <math>\emptyset</math> 出发跳一次得到的 <math>\emptyset'</math>,正是通常意义下的停机问题([[#图灵停机问题(1936)|5.7.3]])。 |