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 Abstract Freely available
Right arrow Full Text (PDF)
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.

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



References

  1. Ambos-Spies K, Mayordomo E. Resource bounded measure and randomness. In: Complexity Logic and Recursion Theory—Sorbi A, ed. (1997) New York NY: Marcel Dekker. 1–47.
  2. Ambos-Spies K, Terwijn S, Zheng X. Resource bounded randomness and weakly complete problems. Theoretical Computer Science (1997) 172:195–207.[CrossRef][Web of Science]
  3. Becher V, Figueira S. An example of a computable absolutely normal number. Theoretical Computer Science (2002) 270:947–958.[CrossRef][Web of Science]
  4. Becher V, Figueira S, Picchi R. Turing's unpublished algorithm for normal numbers. Theoretical Computer Science (2007) 70:126–138.
  5. Gács P. Every set is reducible to a random one. Information and Control (1986) 70:186–192.[CrossRef][Web of Science]
  6. Jockusch C Jr, Soare RI. {Pi}Formula classes and degrees of theories. Transactions of the American Mathematical Society (1972) 173:33–56.[CrossRef][Web of Science]
  7. Kucera A. Measure, {Pi}Formula classes, and complete extensions of PA. Lecture Notes in Mathematics (1985) 1141:245–259.[CrossRef][Web of Science]
  8. Ladner RE. Mitotic recursively enumerable sets. The Journal of Symbolic Logic (1973) 38:199–211.[CrossRef]
  9. Lutz JH. Category and measure in complexity classes. SIAM Journal of Computing (1990) 19:1100–1131.[CrossRef]
  10. Martin-Löf P. The definition of random sequences. Information and Control (1966) 9:602–619.[CrossRef][Web of Science]
  11. Miller JS, Yu L. On initial segment complexity and degrees of randomness. Transactions of the American Mathematical Society (2008) 360:3193–3210.[CrossRef][Web of Science]
  12. Oxtoby JC. Measure and Category (1980) 2nd edn. New York: Springer.
  13. Schnorr C-P. (1971) Heidelberg: Springer. Zufälligkeit und Wahrscheinlichkeit, Vol. 218 of Lecture Notes in Mathematics.
  14. Soare RI. Recursively Enumerable Sets and Degrees (1987) Heidelberg: Springer.
  15. Soare RI. Computability and recursion. Bulletin of Symbolic Logic (1996) 2:284–321.[CrossRef]
  16. Soare RI. Computability and incomputability. Cooper SB, Löwe B, Sorbi A, eds. (2007) Berlin/Heidelberg: Springer. 705–715. In Computation and Logic in the Real World. Vol. 4497 of Lecture Notes in Computer Science.
  17. Trahtenbrot BA. On autoreducibility. Doklady Akademii Nauk SSSR (1970) 192:1224–1227.
  18. van Lambalgen M. Random Sequences (1987) University of Amserdam. PhD thesis Avaialble at http://staff.science.uva.nl/~michiell/docs/fFDiss.pdf.
  19. van Lambalgen M. The axiomatization of randomness. Journal of Symbolic Logic (1990) 55:1143–1167.[CrossRef][Web of Science]

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



This Article
Right arrow Abstract Freely available
Right arrow Full Text (PDF)
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?