_{p:U(p) halts}2

^{-|p|}.

*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

_{s→∞ }Ω

^{s}= Ω.

^{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