Monash University
tr-2000-74-abs.pdf (116.02 kB)
Download file

On elementary computability-theoretic properties of algorithmic randomness

Download (116.02 kB)
posted on 2022-08-31, 02:28 authored by A Arslanov
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 notions of randomness for finite strings: randomness based on the blankendmarker complexity measure and Chaitin randomness based on the self-delimiting complexity measure. For example, we find the positions of RAND k and RAND c to be at the same level in the scale of immunity notions by observing that both of them are not hyperimmune sets. We introduce the notion of complex infinite sequence of finite strings, which we call K-bounded sequences.


Technical report number


Year of publication