Abstract:
In this paper we study some computability theoretic properties of two notions of
randomness for finite strings: randomness based on the blank-endmarker complexity measure
and Chaitin randomness based on the self-delimiting complexity measure. For example, we find
the position of RANDK and RANDC at the same level in the scale of immunity notions by
proving that both of them are not hyperimmune sets. Also we introduce a new notion of complex
infinite sequences of finite strings. We call them K-bounded sequences.