One can determine whether U(p) halts from only the first |p| bits of Ω. Let n=|p| and Ωn be Ω truncated to the first n bits. We have Ωn < Ω < Ωn+2-n. Define Ωs as the same as the definition of Ω as above except then we only sum over the p of length at most s such that U(p) halts in s steps. Note we have
Consider ΩA, which has the same definition as Ω but U now has access to an oracle for A. Rod Downey asks whether this is well defined in terms of being machine independent? Is it degree invariant, that is if A and B have the same Turing degree does ΩA have the same degree as ΩB?
If the answer is yes, then, according to Rod, it is a solution to a very long standing question of Martin. Note you cannot necessarily compute even A from ΩA.
Post a Comment