Abstract:
In this paper we discuss three notions of partial randomness
or ε-randomness. ε-randomness should display all features of randomness
in a scaled down manner. However, as Reimann and
Stephan [15] proved, Tadaki [22] and Calude et al. [3] proposed at
least three different concepts of partial randomness.
We show that all of them satisfy the natural requirement that
any ε-non-null set contains an ε-random infinite word. This allows
us to focus our investigations on the strongest one which is based
on a priori complexity.
We investigate this concept of partial randomness and show
that it allows—similar to the random infinite words—oscillationfree
(w.r.t. to a priori complexity) ε-random infinite words if only ε
is a computable number. The proof uses the dilution principle.
Alternatively, for certain sets of infinite words (w-languages)
we show that their most complex infinite words are oscillation-free
ε-random. Here the parameter ε is also computable and depends
on the set chosen.