Skip Navigation


Journal of Logic and Computation Advance Access originally published online on December 23, 2008
Journal of Logic and Computation 2009 19(2):425-443; doi:10.1093/logcom/exn101
This Article
Right arrow Full Text (PDF)
Right arrow All Versions of this Article:
19/2/425    most recent
exn101v1
Right arrow References
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Figueira, S.
Right arrow Articles by Nies, A.
Right arrow Search for Related Content
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

© The Author, 2008. Published by Oxford University Press. All rights reserved. For Permissions, please email: journals.permissions@oxfordjournals.org

Original Articles

Indifferent Sets

Santiago Figueira

Departamento de Computación, FCEyN, Universidad de Buenos Aires, Ciudad Universitaria, Pabellón I (C1428EGA), Buenos Aires, Argentina and CONICET, Argentina
E-mail: santiago{at}dc.uba.ar

Joseph S. Miller

Department of Mathematics, University of Wisconsin, Madison, WI 53706-1388, USA
E-mail: jmiller{at}math.wisc.edu

André Nies

Department of Computer Science, University of Auckland, Private Bag 92019, Auckland, New Zealand E-mail: andre{at}cs.auckland.ac.nz

Received 21 February 2008.


  Abstract

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.

Keywords: Indifferent set; randomness; autoreducibility; sparseness; hyperimmune set; absolutely normal number; Turing degree


Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?




Disclaimer: Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.