✦ LIBER ✦

Trivial Reals

✍ Scribed by Rod G. Downey; Denis R. Hirschfeldt; André Nies; Frank Stephan

Publisher: Elsevier Science
Year: 2002
Tongue: English
Weight: 223 KB
Volume: 66
Category: Article
ISSN: 1571-0661
DOI: 10.1016/s1571-0661(04)80377-3

No coin nor oath required. For personal study only.

✦ Synopsis

Solovay showed that there are noncomputable reals α such that

, where H is prefix-free Kolmogorov complexity. Such H-trivial reals are interesting due to the connection between algorithmic complexity and effective randomness. We give a new, easier construction of an H-trivial real. We also analyze various computability-theoretic properties of the H-trivial reals, showing for example that no H-trivial real can compute the halting problem (which means that our construction of an H-trivial computably enumerable set is a particularly easy, injury-free construction of an incomplete c.e. set). Finally, we relate the H-trivials to other classes of "highly nonrandom" reals that have been previously studied.

📜 SIMILAR VOLUMES

Needed reals and recursion in generic re

Needed reals and recursion in generic reals

✍ Andreas Blass 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 107 KB

We consider sets of reals that are "adequate" in various senses, for example dominating or unbounded or splitting or non-meager. Call a real x "needed" (in any of these senses) if every adequate set contains a real in which x is recursive. We characterize the needed reals for numerous senses of "ade

Regular reals

✍ Guohua Wu 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 180 KB

Say that α is an n-strongly c. e. (n-strongly computably enumerable) real if α is a sum of n many strongly c. e. reals, and that α is regular if α is n-strongly c. e. for some n. Let S n be the set of all n-strongly c. e. reals, Reg be the set of regular reals and CE be the set of c. e. reals. Then

Cleavability over reals

✍ A.V. Arhangel'skiǐ 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 1010 KB

Jumping with random reals

✍ Tomek Bartoszynski; Haim Judah 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 980 KB

A transfinite hierarchy of reals

✍ George Barmpalias 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 198 KB

## Abstract We extend the hierarchy defined in [5] to cover all hyperarithmetical reals. An intuitive idea is used or the definition, but a characterization of the related classes is obtained. A hierarchy theorem and two fixed point theorems (concerning computations related to the hierarchy) are pr

Making doughnuts of Cohen reals

✍ Lorenz Halbeisen 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 153 KB

## Abstract For __a__ ⊆ __b__ ⊆ __ω__ with __b__\ __a__ infinite, the set __D__ = {__x__ ∈ [__ω__]^__ω__^ : __a__ ⊆ __x__ ⊆ __b__} is called a __doughnut__. A set __S__ ⊆ [__ω__]^__ω__^ has the doughnut property 𝒟 if it contains or is disjoint from a doughnut. It is known that not every set __S__ ⊆