We prove that there is no sw-complete c.e. real, negatively answering a question in [6].

We prove that every Turing degree a bounding some non-GL₂ degree is recursively enumerable in and above (r.e.a.) some 1-generic degree.

We investigate the initial segment complexity of random reals. Let K denote prefix-free Kolmogorov complexity. A natural measure of the relative randomness of two reals α and β is to compare complexity K and K. It is well-known that a real α is 1-random iff there is a constant c such that for all n, Kn−c. We ask the question, what else can be said about the initial segment complexity of random reals. Thus, we study the fine behaviour of K (...) for random α. Following work of Downey, Hirschfeldt and LaForte, we say that αK β iff there is a constant such that for all n, . We call the equivalence classes under this measure of relative randomness K-degrees. We give proofs that there is a random real α so that lim supn K−K=∞ where Ω is Chaitin's random real. One is based upon work of Solovay, and the other exploits a new idea. Further, based on this new idea, we prove there are uncountably many K-degrees of random reals by proving that μ=0. As a corollary to the proof we can prove there is no largest K-degree. Finally we prove that if n ≠ m then the initial segment complexities of the natural n- and m-random sets and Ω︀) are different. The techniques introduced in this paper have already found a number of other applications. (shrink)

On definable filters in computably enumerable degrees.

In this paper, we will prove that the plus cupping degrees generate a definable ideal on c.e. degrees different from other ones known so far, thus answering a question asked by Li and Yang (Proceedings of the 7th and the 8th Asian Logic Conferences. World Scientific Press, Singapore, 2003).

We consider how to represent the measurable sets in an infinite measure space. We use sequences of simple measurable sets converging under metrics to represent general measurable sets. Then we study the computability of the measure and the set operators of measurable sets with respect to such representations.

We investigate in the frame of TTE the computability of functions of the measurable sets from an infinite computable measure space such as the measure and the four kinds of set operations. We first present a series of undecidability and incomputability results about measurable sets. Then we construct several examples of computable topological spaces from the abstract infinite computable measure space, and analyze the computability of the considered functions via respectively each of the standard representations of the computable topological spaces (...) constructed. (shrink)