Random sets versus random sequences
Peter H. Hertling · 2001
Besides the classical randomness notion for in nite binary sequences one can de ne another randomness notion for sets of natural numbers [2]. The relation between these two notions reminds one of the relation between recursive sets and recursively enumerable sets. It is easy to see that randomness of the characteristic sequence of a set implies randomness of the set and of its complement. In this paper we show that the converse is not true: there exists a set such that both the set and its complement are random but the corresponding characteristic binary sequence is nonrandom.