Computational Complexity

Friday, October 04, 2002

 
Chaitin's Omega - The Halting Probability

Posted by Lance

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) halts}2^-|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

lim_s→∞ Ω^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.

9:24 AM # 0 comments

Comment Feeds: This Post All