On Elementary Computability-Theoretic Properties of Algorithmic Randomness
Asat Arslanov · Electronic Notes in Theoretical Computer Science · 2001
In this paper we apply some elementary computability-theoretic notions to algorithmic complexity theory with the aim of understanding the role and extent of computability techniques for algorithmic complexity theory. We study some computability-theoretic properties of two different notions of randomness for finite strings: randomness based on the blank-endmarker complexity measure and Chaitin's randomness based on the self-delimiting complexity measure. We introduce the notion of complex infinite sequence of finite strings, which we call K-bounded sequences.