Indifferent sets

SANTIAGO FIGUEIRA; JOSEPH S. MILLER; ANDRÉ NIES

JOURNAL OF LOGIC AND COMPUTATION

Oxford University Press

Lugar: Oxford; Año: 2009 vol. 19 p. 425 - 443

0955-792X

We define the notion of "indifferent set" with respect to a given class of {0,1}-sequences. Roughly, for a set A in the class, a set of natural numbers I is "indifferent for A" with respect to the class if it does not matter how we change A at the positions in $I$: the new sequence continues to be in the given class. We are especially interested in studying those sets that are indifferent with respect to classes containing different types of stochastic sequences. For the class of Martin-Löf random sequences, we show that every random sequence has an infinite indifferent set and that there is no universal indifferent set. We show that indifferent sets must be sparse, in fact sparse enough to decide the halting problem. We prove the existence of co-c.e. indifferent sets, including a co-c.e. set that is indifferent for every 2-random sequence with respect to the class of random sequences. For the class of absolutely normal numbers, we show that there are computable indifferent sets with respect to that class and we conclude that there is an absolutely normal real number in every non-trivial many-one degree.