Presentations of K-trivial reals and kolmogorov complexity

Abstract

For given real α ∈ {0,1} ∞, a presentation V of α is a prefix-free and recursively enumerable subset of {0,1}* such that α = ∑ σ∈V 2 -|σ|. So, α has a presentation iff α is a left-r.e. real. Let A be the class of all reals which have only computable presentations. Downey and LaForte proved that A has an incomputable member. Call α strongly Kurtz-random if there does not exist any recursive function f with K(α(0) ... α(f(n) - 1)) < f(n) - n for all n. It is shown that every α ∈ A is either computable or strongly Kurtz-random. In particular, all K-trivial members of A are computable where α is K-trivial iff there is a c such that, for all n, K(α(0) ... α(n - 1)) < K(n) + c. Thus there is a natural and nontrivial Turing ideal of left-r.e. α not containing any incomputable member of A. © Springer-Verlag Berlin Heidelberg 2005.