Randomness in Blum Universal Static Complexity Spaces
Cezar Câmpeanu · Universitätsbibliothek Gießen · 2012
In this paper we prove that plain complexity induces the weakest form of randomness for all Blum Universal Static Complexity Spaces. As a consequence, all infinite sequences have infinitely many non-random prefixes with respect to any given Blum Universal Static Complexity Space. This is a generalization of the result obtained by Solovay and Calude for plain complexity, also of the result obtained by Câmpeanu, and independently later on, by Bienvenu and Downey for prefix-free complexity. We also give a result on randomness in case of changing the encoding alphabet.