Friday, October 04, 2002

Chaitin's Omega - The Halting Probability

Chaitin's Omega is the most compact way possible to encode the halting problem. Fix a prefix-free universal Turing machine U, that is if U(p) and U(q) both halt then p is not a prefix of q and vice versa. We define Chaitin's Omega by
Ω = Σp:U(p) halts2-|p|.
By Kraft's Inequality, Ω ≤ 1. Since U halts on some p but not others we have 0 < Ω < 1. Sometimes Ω is called the halting probability because it is the probability of halting if we run U at the start of an infinitely long randomly chosen string.

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

lims→∞ Ωs = Ω.
and Ωs is computable from s. So we find the smallest s ≥ n such that Ωs > Ωn. Note that U(p) halts if and only if it halts in s steps, otherwise Ω ≥ Ωs+2-n > Ωn+2-n a contradiction.

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.

No comments:

Post a Comment