% This file was created with JabRef 2.6.
% Encoding: UTF8

@INPROCEEDINGS{CY07,
  author = {Chi Tat Chong and Liang Yu},
  title = {Thin Maximal Antichains in the Turing Degrees.},
  booktitle = {CiE},
  year = {2007},
  editor = {S. Barry Cooper and Benedikt L?we and Andrea Sorbi},
  volume = {4497},
  series = {Lecture Notes in Computer Science},
  pages = {162--168},
  publisher = {Springer},
  bdsk-url-1 = {http://dblp.uni-trier.de/db/conf/cie/cie2007.html#ChongY07},
  crossref = {conf/cie/2007},
  date = {2007-08-02},
  description = {dblp},
  ee = {http://dx.doi.org/10.1007/978-3-540-73001-9_17},
  isbn = {978-3-540-73000-2},
  keywords = {dblp},
  owner = {Rupert},
  timestamp = {2009.12.17},
  url = {http://dblp.uni-trier.de/db/conf/cie/cie2007.html#ChongY07}
}

@INPROCEEDINGS{CY07,
  author = {Chi Tat Chong and Liang Yu},
  title = {Thin Maximal Antichains in the Turing Degrees.},
  booktitle = {CiE},
  year = {2007},
  editor = {S. Barry Cooper and Benedikt L?we and Andrea Sorbi},
  volume = {4497},
  series = {Lecture Notes in Computer Science},
  pages = {162--168},
  publisher = {Springer},
  crossref = {conf/cie/2007},
  date = {2007-08-02},
  description = {dblp},
  ee = {http://dx.doi.org/10.1007/978-3-540-73001-9_17},
  isbn = {978-3-540-73000-2},
  keywords = {dblp},
  owner = {Rupert},
  timestamp = {2009.12.17},
  url = {http://dblp.uni-trier.de/db/conf/cie/cie2007.html#ChongY07}
}

@ARTICLE{AbSh,
  author = {Abraham, Uri and Shore, Richard A.},
  title = {Initial segments of the degrees of size {$\aleph\sb 1$}},
  journal = {Israel J. Math.},
  year = {1986},
  volume = {53},
  pages = {1--51},
  number = {1},
  coden = {ISJMAP},
  fjournal = {Israel Journal of Mathematics},
  issn = {0021-2172},
  mrclass = {03D30 (06A12)},
  mrnumber = {MR861896 (88a:03099)},
  mrreviewer = {C. G. Jockusch, Jr.},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{AbSh,
  author = {Abraham, Uri and Shore, Richard A.},
  title = {Initial segments of the degrees of size {$\aleph\sb 1$}},
  journal = {Israel J. Math.},
  year = {1986},
  volume = {53},
  pages = {1--51},
  number = {1},
  coden = {ISJMAP},
  fjournal = {Israel Journal of Mathematics},
  issn = {0021-2172},
  mrclass = {03D30 (06A12)},
  mrnumber = {MR861896 (88a:03099)},
  mrreviewer = {C. G. Jockusch, Jr.},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@INCOLLECTION{AcRi72,
  author = {Aczel, Peter and Richter, Wayne},
  title = {Inductive definitions and analogues of large cardinals},
  booktitle = {Conference in Mathematical Logic---London '70 (Proc. Conf., Bedford
	Coll., London, 1970)},
  publisher = {Springer},
  year = {1972},
  pages = {1--9. Lecture Notes in Math., Vol. 255},
  address = {Berlin},
  mrclass = {02F27 (02K35 04A15)},
  mrnumber = {MR0363841 (51 \#96)},
  mrreviewer = {R. Platek},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@INCOLLECTION{AcRi72,
  author = {Aczel, Peter and Richter, Wayne},
  title = {Inductive definitions and analogues of large cardinals},
  booktitle = {Conference in Mathematical Logic---London '70 (Proc. Conf., Bedford
	Coll., London, 1970)},
  publisher = {Springer},
  year = {1972},
  pages = {1--9. Lecture Notes in Math., Vol. 255},
  address = {Berlin},
  mrclass = {02F27 (02K35 04A15)},
  mrnumber = {MR0363841 (51 \#96)},
  mrreviewer = {R. Platek},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{A,
  author = {Eric Allender and Michal Koucky and Detlef Ronneburger and Sambuddha
	Roy},
  title = {Derandomization and Distinguishing Complexity},
  journal = {Computational Complexity, Annual IEEE Conference on},
  year = {2003},
  volume = {0},
  pages = {209},
  address = {Los Alamitos, CA, USA},
  bdsk-url-1 = {http://doi.ieeecomputersociety.org/10.1109/CCC.2003.1214421},
  doi = {http://doi.ieeecomputersociety.org/10.1109/CCC.2003.1214421},
  issn = {1093-0159},
  owner = {Rupert},
  publisher = {IEEE Computer Society},
  timestamp = {2010.01.14}
}

@ARTICLE{A,
  author = {Eric Allender and Michal Koucky and Detlef Ronneburger and Sambuddha
	Roy},
  title = {Derandomization and Distinguishing Complexity},
  journal = {Computational Complexity, Annual IEEE Conference on},
  year = {2003},
  volume = {0},
  pages = {209},
  address = {Los Alamitos, CA, USA},
  doi = {http://doi.ieeecomputersociety.org/10.1109/CCC.2003.1214421},
  issn = {1093-0159},
  owner = {Rupert},
  publisher = {IEEE Computer Society},
  timestamp = {2010.01.14}
}

@ARTICLE{AFvMV,
  author = {Luis Antunes and Lance Fortnow and Dieter van Melkebeek and N. V.
	Vinodchandran},
  title = {Computational depth: Concept and applications},
  journal = {Theor. Comput. Sci.},
  year = {2006},
  volume = {354},
  pages = {391--404},
  number = {3},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  ee = {http://dx.doi.org/10.1016/j.tcs.2005.11.033},
  owner = {Rupert},
  timestamp = {2010.01.14}
}

@ARTICLE{AFvMV,
  author = {Luis Antunes and Lance Fortnow and Dieter van Melkebeek and N. V.
	Vinodchandran},
  title = {Computational depth: Concept and applications},
  journal = {Theor. Comput. Sci.},
  year = {2006},
  volume = {354},
  pages = {391--404},
  number = {3},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  ee = {http://dx.doi.org/10.1016/j.tcs.2005.11.033},
  owner = {Rupert},
  timestamp = {2010.01.14}
}

@ARTICLE{AF,
  author = {Luis Filipe Coelho Antunes and Lance Fortnow},
  title = {Sophistication Revisited},
  journal = {Theory Comput. Syst.},
  year = {2009},
  volume = {45},
  pages = {150--161},
  number = {1},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  ee = {http://springerlink.metapress.com/content/q132605835826g76/},
  owner = {Rupert},
  timestamp = {2010.01.14}
}

@ARTICLE{AF,
  author = {Luis Filipe Coelho Antunes and Lance Fortnow},
  title = {Sophistication Revisited},
  journal = {Theory Comput. Syst.},
  year = {2009},
  volume = {45},
  pages = {150--161},
  number = {1},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  ee = {http://springerlink.metapress.com/content/q132605835826g76/},
  owner = {Rupert},
  timestamp = {2010.01.14}
}

@ARTICLE{Arslanov81,
  author = {Arslanov, M. M.},
  title = {Some generalizations of a fixed-point theorem},
  journal = {Izv. Vyssh. Uchebn. Zaved. Mat.},
  year = {1981},
  pages = {9--16},
  number = {5},
  coden = {IVUMBY},
  fjournal = {Izvestiya Vysshikh Uchebnykh Zavedeni\u\i. Matematika},
  issn = {0021-3446},
  mrclass = {03D30 (03D25 03D35 03D45)},
  mrnumber = {MR630478 (82j:03050)},
  mrreviewer = {G. Asser},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Arslanov81,
  author = {Arslanov, M. M.},
  title = {Some generalizations of a fixed-point theorem},
  journal = {Izv. Vyssh. Uchebn. Zaved. Mat.},
  year = {1981},
  pages = {9--16},
  number = {5},
  coden = {IVUMBY},
  fjournal = {Izvestiya Vysshikh Uchebnykh Zavedeni\u\i. Matematika},
  issn = {0021-3446},
  mrclass = {03D30 (03D25 03D35 03D45)},
  mrnumber = {MR630478 (82j:03050)},
  mrreviewer = {G. Asser},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@BOOK{AshKnight,
  title = {Computable structures and the hyperarithmetical hierarchy},
  publisher = {North-Holland Publishing Co.},
  year = {2000},
  author = {Ash, C. J. and Knight, J.},
  volume = {144},
  pages = {xvi+346},
  series = {Studies in Logic and the Foundations of Mathematics},
  address = {Amsterdam},
  isbn = {0-444-50072-3},
  mrclass = {03D45 (03-02 03D28 03D30)},
  mrnumber = {MR1767842 (2001k:03090)},
  mrreviewer = {Rodney G. Downey},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@BOOK{AshKnight,
  title = {Computable structures and the hyperarithmetical hierarchy},
  publisher = {North-Holland Publishing Co.},
  year = {2000},
  author = {Ash, C. J. and Knight, J.},
  volume = {144},
  pages = {xvi+346},
  series = {Studies in Logic and the Foundations of Mathematics},
  address = {Amsterdam},
  isbn = {0-444-50072-3},
  mrclass = {03D45 (03-02 03D28 03D30)},
  mrnumber = {MR1767842 (2001k:03090)},
  mrreviewer = {Rodney G. Downey},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{MR2480292,
  author = {Barmpalias, George and Downey, Rod and Greenberg, Noam},
  title = {{$K$}-trivial degrees and the jump-traceability hierarchy},
  journal = {Proc. Amer. Math. Soc.},
  year = {2009},
  volume = {137},
  pages = {2099--2109},
  number = {6},
  bdsk-url-1 = {http://dx.doi.org/10.1090/S0002-9939-09-09761-5},
  coden = {PAMYAR},
  doi = {10.1090/S0002-9939-09-09761-5},
  fjournal = {Proceedings of the American Mathematical Society},
  issn = {0002-9939},
  mrclass = {03D80 (68Q30)},
  mrnumber = {MR2480292 (2009k:03073)},
  mrreviewer = {Liang Yu},
  owner = {Rupert},
  timestamp = {2010.02.15},
  url = {http://dx.doi.org/10.1090/S0002-9939-09-09761-5}
}

@BOOK{Barwise75,
  title = {Admissible sets and structures},
  publisher = {Springer-Verlag},
  year = {1975},
  author = {Barwise, Jon},
  pages = {xiii+394},
  address = {Berlin},
  mrclass = {02H99 (02F27 02B25)},
  mrnumber = {MR0424560 (54 \#12519)},
  mrreviewer = {Nigel J. Cutland},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@BOOK{Barwise75,
  title = {Admissible sets and structures},
  publisher = {Springer-Verlag},
  year = {1975},
  author = {Barwise, Jon},
  pages = {xiii+394},
  address = {Berlin},
  mrclass = {02H99 (02F27 02B25)},
  mrnumber = {MR0424560 (54 \#12519)},
  mrreviewer = {Nigel J. Cutland},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Ba,
  author = {Janis Barzdin},
  title = {Complexity of programs to determine whether natural numbers not greater
	than $n$ belong to a recursively enumerable set},
  journal = {Soviet Math. Dokl.},
  year = {1968},
  volume = {9},
  pages = {1251--1254},
  owner = {Rupert},
  timestamp = {2010.01.14}
}

@ARTICLE{Ba,
  author = {Janis Barzdin},
  title = {Complexity of programs to determine whether natural numbers not greater
	than $n$ belong to a recursively enumerable set},
  journal = {Soviet Math. Dokl.},
  year = {1968},
  volume = {9},
  pages = {1251--1254},
  owner = {Rupert},
  timestamp = {2010.01.14}
}

@INCOLLECTION{Be,
  author = {Bennett, Charles H.},
  title = {Logical depth and physical complexity},
  booktitle = {The universal Turing machine (2nd ed.): a half-century survey},
  publisher = {Springer},
  year = {1995},
  pages = {207--235},
  isbn = {3-211-82637-8},
  owner = {Rupert},
  timestamp = {2010.04.22}
}

@INPROCEEDINGS{BD,
  author = {Laurent Bienvenu and Rod Downey},
  title = {Kolmogorov Complexity and Solovay Functions},
  booktitle = {26th International Symposium on Theoretical Aspects of Computer Science
	(STACS 2009)},
  year = {2009},
  editor = {Susanne Albers and Jean-Yves Marion},
  volume = {3},
  series = {Leibniz International Proceedings in Informatics (LIPIcs)},
  pages = {147--158},
  annote = {Keywords: Algorithmic randomness, Kolmogorov complexity, K-triviality},
  doi = {http://dx.doi.org/10.4230/LIPIcs.STACS.2009.1810},
  isbn = {978-3-939897-09-05},
  issn = {1868-8969},
  owner = {Rupert},
  timestamp = {2010.01.14},
  url = {http://drops.dagstuhl.de/opus/volltexte/2009/1810},
  urn = {urn:nbn:de:0030-drops-18107}
}

@INPROCEEDINGS{MR2424720,
  author = {Bienvenu, Laurent and Merkle, Wolfgang},
  title = {Reconciling data compression and {K}olmogorov complexity},
  booktitle = {Proceedings of the International Conference on Automata, Languages
	and Programming (ICALP)},
  year = {2007},
  volume = {4596},
  series = {Lecture Notes in Comput. Sci.},
  pages = {643--654},
  address = {Springer, Berlin},
  doi = {10.1007/978-3-540-73420-8_56},
  mrclass = {68Q30 (68P30)},
  mrnumber = {MR2424720 (2009f:68082)},
  owner = {Rupert},
  timestamp = {2010.04.20},
  url = {http://dx.doi.org/10.1007/978-3-540-73420-8_56}
}

@ARTICLE{BP68,
  author = {Boolos, George and Putnam, Hilary},
  title = {Degrees of unsolvability of constructible sets of integers},
  journal = {J. Symbolic Logic},
  year = {1968},
  volume = {33},
  pages = {497--513},
  fjournal = {The Journal of Symbolic Logic},
  issn = {0022-4812},
  mrclass = {02.77},
  mrnumber = {MR0239977 (39 \#1331)},
  mrreviewer = {L. Hay},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{BP68,
  author = {Boolos, George and Putnam, Hilary},
  title = {Degrees of unsolvability of constructible sets of integers},
  journal = {J. Symbolic Logic},
  year = {1968},
  volume = {33},
  pages = {497--513},
  fjournal = {The Journal of Symbolic Logic},
  issn = {0022-4812},
  mrclass = {02.77},
  mrnumber = {MR0239977 (39 \#1331)},
  mrreviewer = {L. Hay},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{buhrman,
  author = {Buhrman, Harry and Fortnow, Lance and Laplante, Sophie},
  title = {Resource-Bounded Kolmogorov Complexity Revisited},
  journal = {SIAM J. Comput.},
  year = {2001},
  volume = {31},
  pages = {887--905},
  number = {3},
  address = {Philadelphia, PA, USA},
  bdsk-url-1 = {http://dx.doi.org/10.1137/S009753979834388X},
  doi = {http://dx.doi.org/10.1137/S009753979834388X},
  issn = {0097-5397},
  owner = {Rupert},
  publisher = {Society for Industrial and Applied Mathematics},
  timestamp = {2010.01.14}
}

@ARTICLE{buhrman,
  author = {Buhrman, Harry and Fortnow, Lance and Laplante, Sophie},
  title = {Resource-Bounded Kolmogorov Complexity Revisited},
  journal = {SIAM J. Comput.},
  year = {2001},
  volume = {31},
  pages = {887--905},
  number = {3},
  address = {Philadelphia, PA, USA},
  doi = {http://dx.doi.org/10.1137/S009753979834388X},
  issn = {0097-5397},
  owner = {Rupert},
  publisher = {Society for Industrial and Applied Mathematics},
  timestamp = {2010.01.14}
}

@ARTICLE{BuhrmanvMRSS2000,
  author = {Harry Buhrman and Dieter van Melkebeek and Kenneth Regan and D. Sivakumar
	and Martin Strauss},
  title = {A generalization of resource-bounded measure, with application to
	the {BPP} vs. {EXP} Problem},
  journal = {SIAM Journal of Computing},
  year = {2000},
  volume = {30},
  pages = {576--601},
  number = {2},
  date-added = {2009-04-14 18:28:07 +0200},
  date-modified = {2009-04-14 18:28:07 +0200},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{BuhrmanvMRSS2000,
  author = {Harry Buhrman and Dieter van Melkebeek and Kenneth Regan and D. Sivakumar
	and Martin Strauss},
  title = {A generalization of resource-bounded measure, with application to
	the {BPP} vs. {EXP} Problem},
  journal = {SIAM Journal of Computing},
  year = {2000},
  volume = {30},
  pages = {576--601},
  number = {2},
  date-added = {2009-04-14 18:28:07 +0200},
  date-modified = {2009-04-14 18:28:07 +0200},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{BuhrmanvMRSS2000,
  author = {Harry Buhrman and Dieter van Melkebeek and Kenneth Regan and D. Sivakumar
	and Martin Strauss},
  title = {A generalization of resource-bounded measure, with application to
	the {BPP} vs. {EXP} Problem},
  journal = {SIAM Journal of Computing},
  year = {2000},
  volume = {30},
  pages = {576--601},
  number = {2},
  date-added = {2009-04-14 18:28:07 +0200},
  date-modified = {2009-04-14 18:28:07 +0200},
  owner = {Rupert},
  timestamp = {2010.04.20}
}

@ARTICLE{BuhrmanvMRSS2000,
  author = {Harry Buhrman and Dieter van Melkebeek and Kenneth Regan and D. Sivakumar
	and Martin Strauss},
  title = {A generalization of resource-bounded measure, with application to
	the {BPP} vs. {EXP} Problem},
  journal = {SIAM Journal of Computing},
  year = {2000},
  volume = {30},
  pages = {576--601},
  number = {2},
  date-added = {2009-04-14 18:28:07 +0200},
  date-modified = {2009-04-14 18:28:07 +0200}
}

@ARTICLE{BuhrmanvMRSS2000,
  author = {Harry Buhrman and Dieter van Melkebeek and Kenneth Regan and D. Sivakumar
	and Martin Strauss},
  title = {A generalization of resource-bounded measure, with application to
	the {BPP} vs. {EXP} Problem},
  journal = {SIAM Journal of Computing},
  year = {2000},
  volume = {30},
  pages = {576--601},
  number = {2},
  date-added = {2009-04-14 18:28:07 +0200},
  date-modified = {2009-04-14 18:28:07 +0200},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{BuhrmanvMRSS2000,
  author = {Harry Buhrman and Dieter van Melkebeek and Kenneth Regan and D. Sivakumar
	and Martin Strauss},
  title = {A generalization of resource-bounded measure, with application to
	the {BPP} vs. {EXP} Problem},
  journal = {SIAM Journal of Computing},
  year = {2000},
  volume = {30},
  pages = {576--601},
  number = {2},
  date-added = {2009-04-14 18:28:07 +0200},
  date-modified = {2009-04-14 18:28:07 +0200},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@INCOLLECTION{CHV,
  author = {Cai, Jin-Yi and Hemachandra, Lane A. and Vysko\v{c}, Jozef},
  title = {Promises and fault-tolerant database access},
  booktitle = {Complexity theory: current research},
  publisher = {Cambridge University Press},
  year = {1993},
  pages = {101--146},
  isbn = {0-521-44220-6},
  owner = {Rupert},
  timestamp = {2010.01.14}
}

@ARTICLE{Cenzer74,
  author = {Cenzer, Douglas},
  title = {Analytic inductive definitions},
  journal = {J. Symbolic Logic},
  year = {1974},
  volume = {39},
  pages = {310--312},
  fjournal = {The Journal of Symbolic Logic},
  issn = {0022-4812},
  mrclass = {02F27 (02F35)},
  mrnumber = {MR0357089 (50 \#9557)},
  mrreviewer = {A. H. Lachlan},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Cenzer74,
  author = {Cenzer, Douglas},
  title = {Analytic inductive definitions},
  journal = {J. Symbolic Logic},
  year = {1974},
  volume = {39},
  pages = {310--312},
  fjournal = {The Journal of Symbolic Logic},
  issn = {0022-4812},
  mrclass = {02F27 (02F35)},
  mrnumber = {MR0357089 (50 \#9557)},
  mrreviewer = {A. H. Lachlan},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Cha87,
  author = {Chaitin, Gregory J.},
  title = {Incompleteness theorems for random reals},
  journal = {Adv. in Appl. Math.},
  year = {1987},
  volume = {8},
  pages = {119--146},
  number = {2},
  fjournal = {Advances in Applied Mathematics},
  issn = {0196-8858},
  mrclass = {68Q30 (82A99)},
  mrnumber = {MR886921 (88h:68038)},
  mrreviewer = {P. G{\'a}cs},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Cha87,
  author = {Chaitin, Gregory J.},
  title = {Incompleteness theorems for random reals},
  journal = {Adv. in Appl. Math.},
  year = {1987},
  volume = {8},
  pages = {119--146},
  number = {2},
  fjournal = {Advances in Applied Mathematics},
  issn = {0196-8858},
  mrclass = {68Q30 (82A99)},
  mrnumber = {MR886921 (88h:68038)},
  mrreviewer = {P. G{\'a}cs},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Cha75,
  author = {Chaitin, Gregory J.},
  title = {A theory of program size formally identical to information theory},
  journal = {J. Assoc. Comput. Mach.},
  year = {1975},
  volume = {22},
  pages = {329--340},
  fjournal = {Journal of the Association for Computing Machinery},
  issn = {0004-5411},
  mrclass = {94A15 (68A20)},
  mrnumber = {MR0411829 (53 \#15557)},
  mrreviewer = {Aldo De Luca},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Cha75,
  author = {Chaitin, Gregory J.},
  title = {A theory of program size formally identical to information theory},
  journal = {J. Assoc. Comput. Mach.},
  year = {1975},
  volume = {22},
  pages = {329--340},
  fjournal = {Journal of the Association for Computing Machinery},
  issn = {0004-5411},
  mrclass = {94A15 (68A20)},
  mrnumber = {MR0411829 (53 \#15557)},
  mrreviewer = {Aldo De Luca},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Cha69,
  author = {Chaitin, Gregory J.},
  title = {On the length of programs for computing finite binary sequences:
	statistical considerations},
  journal = {J. Assoc. Comput. Mach.},
  year = {1969},
  volume = {16},
  pages = {145--159},
  fjournal = {Journal of the Association for Computing Machinery},
  issn = {0004-5411},
  mrclass = {68.00 (94.00)},
  mrnumber = {MR0237121 (38 \#5414)},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Cha69,
  author = {Chaitin, Gregory J.},
  title = {On the length of programs for computing finite binary sequences:
	statistical considerations},
  journal = {J. Assoc. Comput. Mach.},
  year = {1969},
  volume = {16},
  pages = {145--159},
  fjournal = {Journal of the Association for Computing Machinery},
  issn = {0004-5411},
  mrclass = {68.00 (94.00)},
  mrnumber = {MR0237121 (38 \#5414)},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Cholak20082045,
  author = {Peter Cholak and Rod Downey and Noam Greenberg},
  title = {Strong jump-traceability {I}: The computably enumerable case},
  journal = {Advances in Mathematics},
  year = {2008},
  volume = {217},
  pages = {2045 - 2074},
  number = {5},
  bdsk-url-1 = {http://www.sciencedirect.com/science/article/B6W9F-4PYYGC4-2/2/b853914021581788fcfe553d45e911b7},
  bdsk-url-2 = {http://dx.doi.org/10.1016/j.aim.2007.09.008},
  doi = {DOI: 10.1016/j.aim.2007.09.008},
  issn = {0001-8708},
  keywords = {Strongly jump-traceable},
  owner = {Rupert},
  timestamp = {2010.02.15},
  url = {http://www.sciencedirect.com/science/article/B6W9F-4PYYGC4-2/2/b853914021581788fcfe553d45e911b7}
}

@ARTICLE{CGS,
  author = {Cholak, Peter and Groszek, Marcia and Slaman, Theodore},
  title = {An almost deep degree},
  journal = {J. Symbolic Logic},
  year = {2001},
  volume = {66},
  pages = {881--901},
  number = {2},
  coden = {JSYLA6},
  fjournal = {The Journal of Symbolic Logic},
  issn = {0022-4812},
  mrclass = {03D25},
  mrnumber = {MR1833485 (2002d:03070)},
  mrreviewer = {Michael Stob},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{CGS,
  author = {Cholak, Peter and Groszek, Marcia and Slaman, Theodore},
  title = {An almost deep degree},
  journal = {J. Symbolic Logic},
  year = {2001},
  volume = {66},
  pages = {881--901},
  number = {2},
  coden = {JSYLA6},
  fjournal = {The Journal of Symbolic Logic},
  issn = {0022-4812},
  mrclass = {03D25},
  mrnumber = {MR1833485 (2002d:03070)},
  mrreviewer = {Michael Stob},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{CNY07,
  author = {Chong, Chi Tat and Nies, Andr{\'e} and Yu, Liang},
  title = {Higher randomness notions and their lowness properties},
  journal = {Israel journal of mathematics},
  year = {2008},
  date-modified = {2007-11-30 11:02:11 +0800},
  fjournal = {Israel journal of mathematics},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{CNY07,
  author = {Chong, Chi Tat and Nies, Andr{\'e} and Yu, Liang},
  title = {Higher randomness notions and their lowness properties},
  journal = {Israel journal of mathematics},
  year = {2008},
  date-modified = {2007-11-30 11:02:11 +0800},
  fjournal = {Israel journal of mathematics},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{CY06,
  author = {Chong, Chi Tat and Yu, Liang},
  title = {Maximal chains in the Turing degrees},
  journal = {J. Symbolic Logic},
  year = {to appear},
  fjournal = {The Journal of Symbolic Logic},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{CY06,
  author = {Chong, Chi Tat and Yu, Liang},
  title = {Maximal chains in the Turing degrees},
  journal = {J. Symbolic Logic},
  year = {to appear},
  fjournal = {The Journal of Symbolic Logic},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@BOOK{Cohen66,
  title = {Set theory and the continuum hypothesis},
  publisher = {W. A. Benjamin, Inc., New York-Amsterdam},
  year = {1966},
  author = {Cohen, Paul J.},
  pages = {vi+154},
  mrclass = {02.65},
  mrnumber = {MR0232676 (38 \#999)},
  mrreviewer = {A. L{\'e}vy},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@BOOK{Cohen66,
  title = {Set theory and the continuum hypothesis},
  publisher = {W. A. Benjamin, Inc., New York-Amsterdam},
  year = {1966},
  author = {Cohen, Paul J.},
  pages = {vi+154},
  mrclass = {02.65},
  mrnumber = {MR0232676 (38 \#999)},
  mrreviewer = {A. L{\'e}vy},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Co73,
  author = {Cooper, S. B.},
  title = {Minimal degrees and the jump operator},
  journal = {J. Symbolic Logic},
  year = {1973},
  volume = {38},
  pages = {249--271},
  fjournal = {The Journal of Symbolic Logic},
  issn = {0022-4812},
  mrclass = {02F30},
  mrnumber = {MR0347572 (50 \#75)},
  mrreviewer = {C. G. Jockusch, Jr.},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Co73,
  author = {Cooper, S. B.},
  title = {Minimal degrees and the jump operator},
  journal = {J. Symbolic Logic},
  year = {1973},
  volume = {38},
  pages = {249--271},
  fjournal = {The Journal of Symbolic Logic},
  issn = {0022-4812},
  mrclass = {02F30},
  mrnumber = {MR0347572 (50 \#75)},
  mrreviewer = {C. G. Jockusch, Jr.},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@BOOK{Devlin84,
  title = {Constructibility},
  publisher = {Springer-Verlag},
  year = {1984},
  author = {Devlin, Keith J.},
  pages = {xi+425},
  series = {Perspectives in Mathematical Logic},
  address = {Berlin},
  isbn = {3-540-13258-9},
  mrclass = {03-02 (03E45)},
  mrnumber = {MR750828 (85k:03001)},
  mrreviewer = {A. Kanamori},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@BOOK{Devlin84,
  title = {Constructibility},
  publisher = {Springer-Verlag},
  year = {1984},
  author = {Devlin, Keith J.},
  pages = {xi+425},
  series = {Perspectives in Mathematical Logic},
  address = {Berlin},
  isbn = {3-540-13258-9},
  mrclass = {03-02 (03E45)},
  mrnumber = {MR750828 (85k:03001)},
  mrreviewer = {A. Kanamori},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{DoSi04,
  author = {Dobrinen, Natasha L. and Simpson, Stephen G.},
  title = {Almost everywhere domination},
  journal = {J. Symbolic Logic},
  year = {2004},
  volume = {69},
  pages = {914--922},
  number = {3},
  bdsk-url-1 = {http://projecteuclid.org/getRecord?id=euclid.jsl/1096901775},
  coden = {JSYLA6},
  fjournal = {The Journal of Symbolic Logic},
  issn = {0022-4812},
  mrclass = {03D28 (03B30 03F35 28A05 28E15)},
  mrnumber = {MR2078930 (2005d:03079)},
  mrreviewer = {Denis R. Hirschfeldt},
  owner = {Rupert},
  timestamp = {2009.12.17},
  url = {http://projecteuclid.org/getRecord?id=euclid.jsl/1096901775}
}

@ARTICLE{DoSi04,
  author = {Dobrinen, Natasha L. and Simpson, Stephen G.},
  title = {Almost everywhere domination},
  journal = {J. Symbolic Logic},
  year = {2004},
  volume = {69},
  pages = {914--922},
  number = {3},
  coden = {JSYLA6},
  fjournal = {The Journal of Symbolic Logic},
  issn = {0022-4812},
  mrclass = {03D28 (03B30 03F35 28A05 28E15)},
  mrnumber = {MR2078930 (2005d:03079)},
  mrreviewer = {Denis R. Hirschfeldt},
  owner = {Rupert},
  timestamp = {2009.12.17},
  url = {http://projecteuclid.org/getRecord?id=euclid.jsl/1096901775}
}

@BOOK{DowneyHirschfeldt-ta,
  title = {Algorithmic Randomness},
  publisher = {Springer},
  author = {Rod Downey and Denis Hirschfeldt},
  note = {To appear},
  date-added = {2009-04-17 16:40:19 +0200},
  date-modified = {2009-04-17 17:45:41 +0200}
}

@BOOK{DowneyHirschfeldt-ta,
  title = {Algorithmic Randomness},
  publisher = {Springer},
  year = {to appear},
  author = {Rod Downey and Denis Hirschfeldt},
  note = {Manuscript cited according to verson of November 2009},
  date-added = {2009-04-17 16:40:19 +0200},
  date-modified = {2010-02-17 10:30:47 +0100},
  owner = {Rupert},
  timestamp = {2010.04.20}
}

@ARTICLE{Downey.Griffiths.ea:04,
  author = {Rodney G. Downey and Evan J. Griffiths and Stephanie Reid},
  title = {On Kurtz randomness},
  journal = {Theor. Comput. Sci.},
  year = {2004},
  volume = {321},
  pages = {249--270},
  number = {2-3},
  address = {Essex, UK},
  bdsk-url-1 = {http://dx.doi.org/10.1016/j.tcs.2004.03.055},
  doi = {http://dx.doi.org/10.1016/j.tcs.2004.03.055},
  issn = {0304-3975},
  owner = {Rupert},
  publisher = {Elsevier Science Publishers Ltd.},
  timestamp = {2009.12.17}
}

@ARTICLE{Downey.Griffiths.ea:04,
  author = {Rodney G. Downey and Evan J. Griffiths and Stephanie Reid},
  title = {On Kurtz randomness},
  journal = {Theor. Comput. Sci.},
  year = {2004},
  volume = {321},
  pages = {249--270},
  number = {2-3},
  address = {Essex, UK},
  doi = {http://dx.doi.org/10.1016/j.tcs.2004.03.055},
  issn = {0304-3975},
  owner = {Rupert},
  publisher = {Elsevier Science Publishers Ltd.},
  timestamp = {2009.12.17}
}

@ARTICLE{DHL04,
  author = {Downey, Rod G. and Hirschfeldt, Denis R. and LaForte, Geoff},
  title = {Randomness and reducibility},
  journal = {J. Comput. System Sci.},
  year = {2004},
  volume = {68},
  pages = {96--114},
  number = {1},
  note = {See \cite{DHL01} for an extended abstract},
  coden = {JCSSBM},
  fjournal = {Journal of Computer and System Sciences},
  issn = {0022-0000},
  mrclass = {03D80 (03D30 68Q30)},
  mrnumber = {MR2030512 (2004m:03165)},
  mrreviewer = {A. Ku{\v{c}}era},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{DHL04,
  author = {Downey, Rod G. and Hirschfeldt, Denis R. and LaForte, Geoff},
  title = {Randomness and reducibility},
  journal = {J. Comput. System Sci.},
  year = {2004},
  volume = {68},
  pages = {96--114},
  number = {1},
  note = {See \cite{DHL01} for an extended abstract},
  coden = {JCSSBM},
  fjournal = {Journal of Computer and System Sciences},
  issn = {0022-0000},
  mrclass = {03D80 (03D30 68Q30)},
  mrnumber = {MR2030512 (2004m:03165)},
  mrreviewer = {A. Ku{\v{c}}era},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@INCOLLECTION{EMS,
  author = {Engelen, Fons van and Miller, Arnold W. and Steel, John},
  title = {Rigid {B}orel sets and better quasi-order theory},
  booktitle = {Logic and combinatorics (Arcata, Calif., 1985)},
  publisher = {Amer. Math. Soc.},
  year = {1987},
  volume = {65},
  series = {Contemp. Math.},
  pages = {199--222},
  address = {Providence, RI},
  mrclass = {03E60 (03E05 03E15 03E35 54H05)},
  mrnumber = {MR891249 (88e:03079)},
  mrreviewer = {Ivo D{\"u}ntsch},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@INCOLLECTION{EMS,
  author = {Engelen, Fons van and Miller, Arnold W. and Steel, John},
  title = {Rigid {B}orel sets and better quasi-order theory},
  booktitle = {Logic and combinatorics (Arcata, Calif., 1985)},
  publisher = {Amer. Math. Soc.},
  year = {1987},
  volume = {65},
  series = {Contemp. Math.},
  pages = {199--222},
  address = {Providence, RI},
  mrclass = {03E60 (03E05 03E15 03E35 54H05)},
  mrnumber = {MR891249 (88e:03079)},
  mrreviewer = {Ivo D{\"u}ntsch},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@BOOK{Epstein79,
  title = {Degrees of unsolvability: structure and theory},
  publisher = {Springer},
  year = {1979},
  author = {Epstein, Richard L.},
  volume = {759},
  pages = {xiv+240},
  series = {Lecture Notes in Mathematics},
  address = {Berlin},
  isbn = {3-540-09710-4},
  mrclass = {03D30 (03D25)},
  mrnumber = {MR551620 (81e:03042)},
  mrreviewer = {Barry Cooper},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@BOOK{Epstein79,
  title = {Degrees of unsolvability: structure and theory},
  publisher = {Springer},
  year = {1979},
  author = {Epstein, Richard L.},
  volume = {759},
  pages = {xiv+240},
  series = {Lecture Notes in Mathematics},
  address = {Berlin},
  isbn = {3-540-09710-4},
  mrclass = {03D30 (03D25)},
  mrnumber = {MR551620 (81e:03042)},
  mrreviewer = {Barry Cooper},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@INCOLLECTION{EpHaKr81,
  author = {Epstein, Richard L. and Haas, Richard and Kramer, Richard L.},
  title = {Hierarchies of sets and degrees below {${\bf 0}\sp{\prime} $}},
  booktitle = {Logic Year 1979--80 (Proc. Seminars and Conf. Math. Logic, Univ.
	Connecticut, Storrs, Conn., 1979/80)},
  publisher = {Springer},
  year = {1981},
  volume = {859},
  series = {Lecture Notes in Math.},
  pages = {32--48},
  address = {Berlin},
  mrclass = {03D55 (03D30)},
  mrnumber = {MR619859 (82k:03073)},
  mrreviewer = {C. G. Jockusch, Jr.},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@INCOLLECTION{EpHaKr81,
  author = {Epstein, Richard L. and Haas, Richard and Kramer, Richard L.},
  title = {Hierarchies of sets and degrees below {${\bf 0}\sp{\prime} $}},
  booktitle = {Logic Year 1979--80 (Proc. Seminars and Conf. Math. Logic, Univ.
	Connecticut, Storrs, Conn., 1979/80)},
  publisher = {Springer},
  year = {1981},
  volume = {859},
  series = {Lecture Notes in Math.},
  pages = {32--48},
  address = {Berlin},
  mrclass = {03D55 (03D30)},
  mrnumber = {MR619859 (82k:03073)},
  mrreviewer = {C. G. Jockusch, Jr.},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{ErshovIII,
  author = {Er{\v{s}}ov, Ju. L.},
  title = {A certain hierarchy of sets. {III}},
  journal = {Algebra i Logika},
  year = {1970},
  volume = {9},
  pages = {34--51},
  fjournal = {Akademiya Nauk SSSR. Sibirskoe Otdelenie. Institut Matematiki. Algebra
	i Logika},
  issn = {0373-9252},
  mrclass = {02F35},
  mrnumber = {MR0299478 (45 \#8526)},
  mrreviewer = {A. S. Ferebee},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{ErshovIII,
  author = {Er{\v{s}}ov, Ju. L.},
  title = {A certain hierarchy of sets. {III}},
  journal = {Algebra i Logika},
  year = {1970},
  volume = {9},
  pages = {34--51},
  fjournal = {Akademiya Nauk SSSR. Sibirskoe Otdelenie. Institut Matematiki. Algebra
	i Logika},
  issn = {0373-9252},
  mrclass = {02F35},
  mrnumber = {MR0299478 (45 \#8526)},
  mrreviewer = {A. S. Ferebee},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{ErshovI,
  author = {Er{\v{s}}ov, Ju. L.},
  title = {A certain hierarchy of sets. {I}},
  journal = {Algebra i Logika},
  year = {1968},
  volume = {7},
  pages = {47--74},
  number = {1},
  fjournal = {Akademiya Nauk SSSR. Sibirskoe Otdelenie. Institut Matematiki. Algebra
	i Logika},
  issn = {0373-9252},
  mrclass = {02.77},
  mrnumber = {MR0270911 (42 \#5794)},
  mrreviewer = {A. S. Ferebee},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{ErshovI,
  author = {Er{\v{s}}ov, Ju. L.},
  title = {A certain hierarchy of sets. {I}},
  journal = {Algebra i Logika},
  year = {1968},
  volume = {7},
  pages = {47--74},
  number = {1},
  fjournal = {Akademiya Nauk SSSR. Sibirskoe Otdelenie. Institut Matematiki. Algebra
	i Logika},
  issn = {0373-9252},
  mrclass = {02.77},
  mrnumber = {MR0270911 (42 \#5794)},
  mrreviewer = {A. S. Ferebee},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{ErshovII,
  author = {Er{\v{s}}ov, Ju. L.},
  title = {A certain hierarchy of sets. {II}},
  journal = {Algebra i Logika},
  year = {1968},
  volume = {7},
  pages = {15--47},
  number = {4},
  fjournal = {Akademiya Nauk SSSR. Sibirskoe Otdelenie. Institut Matematiki. Algebra
	i Logika},
  issn = {0373-9252},
  mrclass = {02.77},
  mrnumber = {MR0270912 (42 \#5795)},
  mrreviewer = {A. S. Ferebee},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{ErshovII,
  author = {Er{\v{s}}ov, Ju. L.},
  title = {A certain hierarchy of sets. {II}},
  journal = {Algebra i Logika},
  year = {1968},
  volume = {7},
  pages = {15--47},
  number = {4},
  fjournal = {Akademiya Nauk SSSR. Sibirskoe Otdelenie. Institut Matematiki. Algebra
	i Logika},
  issn = {0373-9252},
  mrclass = {02.77},
  mrnumber = {MR0270912 (42 \#5795)},
  mrreviewer = {A. S. Ferebee},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Fefer65,
  author = {Feferman, S.},
  title = {Some applications of the notions of forcing and generic sets},
  journal = {Fund. Math.},
  year = {1964/1965},
  volume = {56},
  pages = {325--345},
  fjournal = {Polska Akademia Nauk. Fundamenta Mathematicae},
  issn = {0016-2736},
  mrclass = {02.65},
  mrnumber = {MR0176925 (31 \#1193)},
  mrreviewer = {A. Mostowski},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Fefer65,
  author = {Feferman, S.},
  title = {Some applications of the notions of forcing and generic sets},
  journal = {Fund. Math.},
  year = {1964/1965},
  volume = {56},
  pages = {325--345},
  fjournal = {Polska Akademia Nauk. Fundamenta Mathematicae},
  issn = {0016-2736},
  mrclass = {02.65},
  mrnumber = {MR0176925 (31 \#1193)},
  mrreviewer = {A. Mostowski},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{FeKr66,
  author = {Feferman, S. and Kreisel, G.},
  title = {Persistent and invariant formulas relative to theories of higher
	order},
  journal = {Bull. Amer. Math. Soc.},
  year = {1966},
  volume = {72},
  pages = {480--485},
  mrclass = {02.32},
  mrnumber = {MR0193007 (33 \#1229)},
  mrreviewer = {E. Engeler},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{FeKr66,
  author = {Feferman, S. and Kreisel, G.},
  title = {Persistent and invariant formulas relative to theories of higher
	order},
  journal = {Bull. Amer. Math. Soc.},
  year = {1966},
  volume = {72},
  pages = {480--485},
  mrclass = {02.32},
  mrnumber = {MR0193007 (33 \#1229)},
  mrreviewer = {E. Engeler},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{FeSpe62,
  author = {Feferman, S. and Spector, C.},
  title = {Incompleteness along paths in progressions of theories},
  journal = {J. Symbolic Logic},
  year = {1962},
  volume = {27},
  pages = {383--390},
  fjournal = {The Journal of Symbolic Logic},
  issn = {0022-4812},
  mrclass = {02.18},
  mrnumber = {MR0172793 (30 \#3012)},
  mrreviewer = {J. R. Shoenfield},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{FeSpe62,
  author = {Feferman, S. and Spector, C.},
  title = {Incompleteness along paths in progressions of theories},
  journal = {J. Symbolic Logic},
  year = {1962},
  volume = {27},
  pages = {383--390},
  fjournal = {The Journal of Symbolic Logic},
  issn = {0022-4812},
  mrclass = {02.18},
  mrnumber = {MR0172793 (30 \#3012)},
  mrreviewer = {J. R. Shoenfield},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{FLMR,
  author = {Fenner, Stephen A. and Lutz, Jack H. and Mayordomo, Elvira and Reardon,
	Patrick},
  title = {Weakly useful sequences},
  journal = {Inf. Comput.},
  year = {2005},
  volume = {197},
  pages = {41--54},
  number = {1/2},
  address = {Duluth, MN, USA},
  doi = {http://dx.doi.org/10.1016/j.ic.2005.01.001},
  issn = {0890-5401},
  owner = {Rupert},
  publisher = {Academic Press, Inc.},
  timestamp = {2010.01.14}
}

@ARTICLE{FLMR,
  author = {Fenner, Stephen A. and Lutz, Jack H. and Mayordomo, Elvira and Reardon,
	Patrick},
  title = {Weakly useful sequences},
  journal = {Inf. Comput.},
  year = {2005},
  volume = {197},
  pages = {41--54},
  number = {1/2},
  address = {Duluth, MN, USA},
  bdsk-url-1 = {http://dx.doi.org/10.1016/j.ic.2005.01.001},
  doi = {http://dx.doi.org/10.1016/j.ic.2005.01.001},
  issn = {0890-5401},
  owner = {Rupert},
  publisher = {Academic Press, Inc.},
  timestamp = {2010.01.14}
}

@ARTICLE{FK,
  author = {Fortnow, Lance and Kummer, Martin},
  title = {On resource-bounded instance complexity},
  journal = {Theor. Comput. Sci.},
  year = {1996},
  volume = {161},
  pages = {123--140},
  number = {1-2},
  address = {Essex, UK},
  doi = {http://dx.doi.org/10.1016/0304-3975(95)00097-6},
  issn = {0304-3975},
  owner = {Rupert},
  publisher = {Elsevier Science Publishers Ltd.},
  timestamp = {2010.01.14}
}

@ARTICLE{FK,
  author = {Fortnow, Lance and Kummer, Martin},
  title = {On resource-bounded instance complexity},
  journal = {Theor. Comput. Sci.},
  year = {1996},
  volume = {161},
  pages = {123--140},
  number = {1-2},
  address = {Essex, UK},
  bdsk-url-1 = {http://dx.doi.org/10.1016/0304-3975(95)00097-6},
  doi = {http://dx.doi.org/10.1016/0304-3975(95)00097-6},
  issn = {0304-3975},
  owner = {Rupert},
  publisher = {Elsevier Science Publishers Ltd.},
  timestamp = {2010.01.14}
}

@ARTICLE{FGSW,
  author = {Johanna Franklin and Noam Greenberg and Frank Stephan and Guohua
	Wu},
  title = {Anti-complexity, lowness and highness notions, and reducibilities
	with tiny use},
  note = {Manuscript, 2009.},
  owner = {Rupert},
  timestamp = {2010.01.14}
}

@ARTICLE{FS,
  author = {Johanna Franklin and Frank Stephan},
  title = {Schnorr trivial sets and truth-table reducibility},
  journal = {Journal of Symbolic Logic},
  year = {2010},
  volume = {75},
  pages = {501--521},
  owner = {Rupert},
  timestamp = {2010.01.14}
}

@ARTICLE{Friedberg57,
  author = {Friedberg, Richard M.},
  title = {Two recursively enumerable sets of incomparable degrees of unsolvability
	(solution of {P}ost's problem, 1944)},
  journal = {Proc. Nat. Acad. Sci. U.S.A.},
  year = {1957},
  volume = {43},
  pages = {236--238},
  mrclass = {02.0X},
  mrnumber = {MR0084474 (18,867a)},
  mrreviewer = {A. Heyting},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Friedberg57,
  author = {Friedberg, Richard M.},
  title = {Two recursively enumerable sets of incomparable degrees of unsolvability
	(solution of {P}ost's problem, 1944)},
  journal = {Proc. Nat. Acad. Sci. U.S.A.},
  year = {1957},
  volume = {43},
  pages = {236--238},
  mrclass = {02.0X},
  mrnumber = {MR0084474 (18,867a)},
  mrreviewer = {A. Heyting},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Fried73,
  author = {Friedman, Harvey M.},
  title = {Borel sets and hyperdegrees},
  journal = {J. Symbolic Logic},
  year = {1973},
  volume = {38},
  pages = {405--409},
  fjournal = {The Journal of Symbolic Logic},
  issn = {0022-4812},
  mrclass = {02F30},
  mrnumber = {MR0335248 (49 \#30)},
  mrreviewer = {Donald Martin},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Fried73,
  author = {Friedman, Harvey M.},
  title = {Borel sets and hyperdegrees},
  journal = {J. Symbolic Logic},
  year = {1973},
  volume = {38},
  pages = {405--409},
  fjournal = {The Journal of Symbolic Logic},
  issn = {0022-4812},
  mrclass = {02F30},
  mrnumber = {MR0335248 (49 \#30)},
  mrreviewer = {Donald Martin},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{BDG,
  author = {G. Barmpalias, R. Downey and N. Greenberg},
  title = {$\K$-trivial degrees and the jump-traceability hierarchy},
  journal = {Proc. Amer. Math. Soc.},
  year = {2009},
  doi = {10.1090/S0002-9939-09-09761-5},
  owner = {Rupert},
  timestamp = {2010.01.14}
}

@ARTICLE{BDG,
  author = {G. Barmpalias, R. Downey and N. Greenberg},
  title = {$\K$-trivial degrees and the jump-traceability hierarchy},
  journal = {Proc. Amer. Math. Soc.},
  year = {2009},
  bdsk-url-1 = {http://dx.doi.org/10.1090/S0002-9939-09-09761-5},
  doi = {10.1090/S0002-9939-09-09761-5},
  owner = {Rupert},
  timestamp = {2010.01.14}
}

@ARTICLE{Gandy60,
  author = {Gandy, R. O.},
  title = {Proof of {M}ostowski's conjecture},
  journal = {Bull. Acad. Polon. Sci. S\'er. Sci. Math. Astronom. Phys.},
  year = {1960},
  volume = {8},
  pages = {571--575},
  fjournal = {Bulletin de l'Acad\'emie Polonaise des Sciences. S\'erie des Sciences
	Math\'ematiques, Astronomiques et Physiques},
  issn = {0001-4117},
  mrclass = {02.72},
  mrnumber = {MR0126383 (23 \#A3679)},
  mrreviewer = {G. Kreisel},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Gandy60,
  author = {Gandy, R. O.},
  title = {Proof of {M}ostowski's conjecture},
  journal = {Bull. Acad. Polon. Sci. S\'er. Sci. Math. Astronom. Phys.},
  year = {1960},
  volume = {8},
  pages = {571--575},
  fjournal = {Bulletin de l'Acad\'emie Polonaise des Sciences. S\'erie des Sciences
	Math\'ematiques, Astronomiques et Physiques},
  issn = {0001-4117},
  mrclass = {02.72},
  mrnumber = {MR0126383 (23 \#A3679)},
  mrreviewer = {G. Kreisel},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{GrMi,
  author = {Noam Greenberg and Joseph Miller},
  title = {Lowness for {K}urtz Randomness},
  year = {In preparation},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{GrMi,
  author = {Noam Greenberg and Joseph Miller},
  title = {Lowness for {K}urtz Randomness},
  year = {In preparation},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{GMta,
  author = {Greenberg, Noam and Montalb{\'a}n, Antonio},
  title = {RANKED STRUCTURES AND ARITHMETIC TRANSFINITE RECURSION},
  journal = {to appear},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{GMta,
  author = {Greenberg, Noam and Montalb{\'a}n, Antonio},
  title = {RANKED STRUCTURES AND ARITHMETIC TRANSFINITE RECURSION},
  journal = {to appear},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Ga86,
  author = {G{\'a}cs, P{\'e}ter},
  title = {Every sequence is reducible to a random one},
  journal = {Inform. and Control},
  year = {1986},
  volume = {70},
  pages = {186--192},
  number = {2-3},
  coden = {IFCNA4},
  fjournal = {Information and Control},
  issn = {0019-9958},
  mrclass = {03D30 (60A05 68Q30)},
  mrnumber = {87k:03043},
  mrreviewer = {Hisao Tanaka},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Ga86,
  author = {G{\'a}cs, P{\'e}ter},
  title = {Every sequence is reducible to a random one},
  journal = {Inform. and Control},
  year = {1986},
  volume = {70},
  pages = {186--192},
  number = {2-3},
  coden = {IFCNA4},
  fjournal = {Information and Control},
  issn = {0019-9958},
  mrclass = {03D30 (60A05 68Q30)},
  mrnumber = {87k:03043},
  mrreviewer = {Hisao Tanaka},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Ga80,
  author = {G{\'a}cs, P{\'e}ter},
  title = {Exact expressions for some randomness tests},
  journal = {Z. Math. Logik Grundlag. Math.},
  year = {1980},
  volume = {26},
  pages = {385--394},
  number = {5},
  coden = {ZMLGAQ},
  fjournal = {Zeitschrift f\"ur Mathematische Logik und Grundlagen der Mathematik},
  issn = {0044-3050},
  mrclass = {65C10 (68C25)},
  mrnumber = {82c:65004},
  mrreviewer = {Harald Niederreiter},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Ga80,
  author = {G{\'a}cs, P{\'e}ter},
  title = {Exact expressions for some randomness tests},
  journal = {Z. Math. Logik Grundlag. Math.},
  year = {1980},
  volume = {26},
  pages = {385--394},
  number = {5},
  coden = {ZMLGAQ},
  fjournal = {Zeitschrift f\"ur Mathematische Logik und Grundlagen der Mathematik},
  issn = {0044-3050},
  mrclass = {65C10 (68C25)},
  mrnumber = {82c:65004},
  mrreviewer = {Harald Niederreiter},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Harrington78,
  author = {Harrington, Leo},
  title = {Analytic determinacy and {$0\sp{\sharp }$}},
  journal = {J. Symbolic Logic},
  year = {1978},
  volume = {43},
  pages = {685--693},
  number = {4},
  coden = {JSYLA6},
  fjournal = {The Journal of Symbolic Logic},
  issn = {0022-4812},
  mrclass = {03E15 (03E60)},
  mrnumber = {MR518675 (80b:03065)},
  mrreviewer = {Jeffrey Paris},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Harrington78,
  author = {Harrington, Leo},
  title = {Analytic determinacy and {$0\sp{\sharp }$}},
  journal = {J. Symbolic Logic},
  year = {1978},
  volume = {43},
  pages = {685--693},
  number = {4},
  coden = {JSYLA6},
  fjournal = {The Journal of Symbolic Logic},
  issn = {0022-4812},
  mrclass = {03E15 (03E60)},
  mrnumber = {MR518675 (80b:03065)},
  mrreviewer = {Jeffrey Paris},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Har76,
  author = {Harrington, L},
  title = {A powerless proof of a theorem by Silver},
  journal = {handwritten note, UC Berkeley},
  year = {1976},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Har76,
  author = {Harrington, L},
  title = {A powerless proof of a theorem by Silver},
  journal = {handwritten note, UC Berkeley},
  year = {1976},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@BOOK{Hin78,
  title = {Recursion-theoretic hierarchies},
  publisher = {Springer-Verlag},
  year = {1978},
  author = {Hinman, Peter G.},
  pages = {xii+480},
  address = {Berlin},
  isbn = {3-540-07904-1},
  mrclass = {03D55 (03-02 03D60 03D65)},
  mrnumber = {MR499205 (82b:03084)},
  mrreviewer = {Stephen G. Simpson},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@BOOK{Hin78,
  title = {Recursion-theoretic hierarchies},
  publisher = {Springer-Verlag},
  year = {1978},
  author = {Hinman, Peter G.},
  pages = {xii+480},
  address = {Berlin},
  isbn = {3-540-07904-1},
  mrclass = {03D55 (03-02 03D60 03D65)},
  mrnumber = {MR499205 (82b:03084)},
  mrreviewer = {Stephen G. Simpson},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{HjNi,
  author = {Hjorth, G and Nies, A},
  title = {Randomness in effective descriptive set theory},
  journal = {J. London. Math. Soc.},
  year = {2007},
  volume = {75},
  pages = {495--508},
  number = {2},
  date-modified = {2007-11-30 11:03:36 +0800},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{HjNi,
  author = {Hjorth, G and Nies, A},
  title = {Randomness in effective descriptive set theory},
  journal = {J. London. Math. Soc.},
  year = {2007},
  volume = {75},
  pages = {495--508},
  number = {2},
  date-modified = {2007-11-30 11:03:36 +0800},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@BOOK{1196416,
  title = {Introduction to Automata Theory, Languages, and Computation (3rd
	Edition)},
  publisher = {Addison-Wesley Longman Publishing Co., Inc.},
  year = {2006},
  author = {Hopcroft, John E. and Motwani, Rajeev and Ullman, Jeffrey D.},
  address = {Boston, MA, USA},
  isbn = {0321455363},
  owner = {Rupert},
  timestamp = {2010.04.21}
}

@BOOK{Jech03,
  title = {Set theory},
  publisher = {Springer-Verlag},
  year = {2003},
  author = {Jech, Thomas},
  pages = {xiv+769},
  series = {Springer Monographs in Mathematics},
  address = {Berlin},
  isbn = {3-540-44085-2},
  mrclass = {03Exx (03-01 03-02)},
  mrnumber = {MR1940513 (2004g:03071)},
  mrreviewer = {Eva Coplakova},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@BOOK{Jech03,
  title = {Set theory},
  publisher = {Springer-Verlag},
  year = {2003},
  author = {Jech, Thomas},
  pages = {xiv+769},
  series = {Springer Monographs in Mathematics},
  address = {Berlin},
  isbn = {3-540-44085-2},
  mrclass = {03Exx (03-01 03-02)},
  mrnumber = {MR1940513 (2004g:03071)},
  mrreviewer = {Eva Coplakova},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Jensen72,
  author = {Jensen, R. Bj{\"o}rn},
  title = {The fine structure of the constructible hierarchy},
  journal = {Ann. Math. Logic},
  year = {1972},
  volume = {4},
  pages = {229--308; erratum, ibid. 4 (1972), 443},
  fjournal = {Annals of Pure and Applied Logic},
  issn = {0168-0072},
  mrclass = {02K05},
  mrnumber = {MR0309729 (46 \#8834)},
  mrreviewer = {Andreas Blass},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Jensen72,
  author = {Jensen, R. Bj{\"o}rn},
  title = {The fine structure of the constructible hierarchy},
  journal = {Ann. Math. Logic},
  year = {1972},
  volume = {4},
  pages = {229--308; erratum, ibid. 4 (1972), 443},
  fjournal = {Annals of Pure and Applied Logic},
  issn = {0168-0072},
  mrclass = {02K05},
  mrnumber = {MR0309729 (46 \#8834)},
  mrreviewer = {Andreas Blass},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@INCOLLECTION{MR1034562,
  author = {Jockusch, Jr., Carl G.},
  title = {Degrees of functions with no fixed points},
  booktitle = {Proceedings of the Eighth International Congress of Logic, Methodology
	and Philosophy of Science ({M}oscow, 1987)},
  publisher = {North-Holland},
  year = {1989},
  volume = {126},
  series = {Stud. Logic Found. Math.},
  pages = {191--201},
  address = {Amsterdam},
  doi = {10.1016/S0049-237X(08)70045-4},
  mrclass = {03D30},
  mrnumber = {MR1034562 (91c:03036)},
  mrreviewer = {Barry Cooper},
  owner = {Rupert},
  timestamp = {2010.02.25},
  url = {http://dx.doi.org/10.1016/S0049-237X(08)70045-4}
}

@ARTICLE{Jo68,
  author = {Jockusch, Jr., Carl G.},
  title = {Uniformly introreducible sets},
  journal = {J. Symbolic Logic},
  year = {1968},
  volume = {33},
  pages = {521--536},
  fjournal = {The Journal of Symbolic Logic},
  issn = {0022-4812},
  mrclass = {02.70},
  mrnumber = {MR0237330 (38 \#5619)},
  mrreviewer = {K. Appel},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Jo68,
  author = {Jockusch, Jr., Carl G.},
  title = {Uniformly introreducible sets},
  journal = {J. Symbolic Logic},
  year = {1968},
  volume = {33},
  pages = {521--536},
  fjournal = {The Journal of Symbolic Logic},
  issn = {0022-4812},
  mrclass = {02.70},
  mrnumber = {MR0237330 (38 \#5619)},
  mrreviewer = {K. Appel},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{JoPo81,
  author = {Jockusch, Jr., Carl G. and Posner, David B.},
  title = {Automorphism bases for degrees of unsolvability},
  journal = {Israel J. Math.},
  year = {1981},
  volume = {40},
  pages = {150--164},
  number = {2},
  bdsk-url-1 = {http://dx.doi.org/10.1007/BF02761906},
  coden = {ISJMAP},
  doi = {10.1007/BF02761906},
  fjournal = {Israel Journal of Mathematics},
  issn = {0021-2172},
  mrclass = {03D30},
  mrnumber = {MR634902 (83j:03072)},
  mrreviewer = {A. H. Lachlan},
  owner = {Rupert},
  timestamp = {2009.12.17},
  url = {http://dx.doi.org/10.1007/BF02761906}
}

@ARTICLE{JoPo81,
  author = {Jockusch, Jr., Carl G. and Posner, David B.},
  title = {Automorphism bases for degrees of unsolvability},
  journal = {Israel J. Math.},
  year = {1981},
  volume = {40},
  pages = {150--164},
  number = {2},
  coden = {ISJMAP},
  doi = {10.1007/BF02761906},
  fjournal = {Israel Journal of Mathematics},
  issn = {0021-2172},
  mrclass = {03D30},
  mrnumber = {MR634902 (83j:03072)},
  mrreviewer = {A. H. Lachlan},
  owner = {Rupert},
  timestamp = {2009.12.17},
  url = {http://dx.doi.org/10.1007/BF02761906}
}

@ARTICLE{JockSo73,
  author = {Jockusch, Jr., Carl G. and Soare, Robert I.},
  title = {Encodability of {K}leene's {$O$}},
  journal = {J. Symbolic Logic},
  year = {1973},
  volume = {38},
  pages = {437--440},
  fjournal = {The Journal of Symbolic Logic},
  issn = {0022-4812},
  mrclass = {02F30},
  mrnumber = {MR0363842 (51 \#97)},
  mrreviewer = {J. C. Owings, Jr.},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{JockSo73,
  author = {Jockusch, Jr., Carl G. and Soare, Robert I.},
  title = {Encodability of {K}leene's {$O$}},
  journal = {J. Symbolic Logic},
  year = {1973},
  volume = {38},
  pages = {437--440},
  fjournal = {The Journal of Symbolic Logic},
  issn = {0022-4812},
  mrclass = {02F30},
  mrnumber = {MR0363842 (51 \#97)},
  mrreviewer = {J. C. Owings, Jr.},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{JockSo72,
  author = {Jockusch, Jr., Carl G. and Soare, Robert I.},
  title = {{$\Pi \sp{0}\sb{1}$} classes and degrees of theories},
  journal = {Trans. Amer. Math. Soc.},
  year = {1972},
  volume = {173},
  pages = {33--56},
  fjournal = {Transactions of the American Mathematical Society},
  issn = {0002-9947},
  mrclass = {02F30 (02F35 02G05)},
  mrnumber = {MR0316227 (47 \#4775)},
  mrreviewer = {S. Feferman},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{JockSo72,
  author = {Jockusch, Jr., Carl G. and Soare, Robert I.},
  title = {{$\Pi \sp{0}\sb{1}$} classes and degrees of theories},
  journal = {Trans. Amer. Math. Soc.},
  year = {1972},
  volume = {173},
  pages = {33--56},
  fjournal = {Transactions of the American Mathematical Society},
  issn = {0002-9947},
  mrclass = {02F30 (02F35 02G05)},
  mrnumber = {MR0316227 (47 \#4775)},
  mrreviewer = {S. Feferman},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{JLL,
  author = {Juedes, David W. and Lathrop, James I. and Lutz, Jack H.},
  title = {Computational depth and reducibility},
  journal = {Theor. Comput. Sci.},
  year = {1994},
  volume = {132},
  pages = {37--70},
  number = {1-2},
  address = {Essex, UK},
  bdsk-url-1 = {http://dx.doi.org/10.1016/0304-3975(94)00014-X},
  doi = {http://dx.doi.org/10.1016/0304-3975(94)00014-X},
  issn = {0304-3975},
  owner = {Rupert},
  publisher = {Elsevier Science Publishers Ltd.},
  timestamp = {2010.01.14}
}

@ARTICLE{JLL,
  author = {Juedes, David W. and Lathrop, James I. and Lutz, Jack H.},
  title = {Computational depth and reducibility},
  journal = {Theor. Comput. Sci.},
  year = {1994},
  volume = {132},
  pages = {37--70},
  number = {1-2},
  address = {Essex, UK},
  doi = {http://dx.doi.org/10.1016/0304-3975(94)00014-X},
  issn = {0304-3975},
  owner = {Rupert},
  publisher = {Elsevier Science Publishers Ltd.},
  timestamp = {2010.01.14}
}

@ARTICLE{kanovich1970,
  author = {Max I. Kanovich},
  title = {On the complexity of enumeration and decision of predicates},
  journal = {Soviet Math. Dokl.},
  year = {1970},
  volume = {11},
  pages = {17--20},
  owner = {Rupert},
  timestamp = {2010.02.15}
}

@ARTICLE{KastermansL,
  author = {Kastermans, Bart and Lempp, Steffen},
  title = {Comparing notions of randomness},
  journal = {Theor. Comput. Sci.},
  year = {2010},
  volume = {411},
  pages = {602--616},
  acmid = {1670841},
  address = {Essex, UK},
  doi = {10.1016/j.tcs.2009.09.036},
  issn = {0304-3975},
  issue = {3},
  keywords = {Effective randomness, Kolmogorov-Loveland randomness, Martin-L\"{o}f
	randomness},
  numpages = {15},
  owner = {Rupert},
  publisher = {Elsevier Science Publishers Ltd.},
  timestamp = {2010.04.22},
  url = {http://portal.acm.org/citation.cfm?id=1670829.1670841}
}

@ARTICLE{Kech73,
  author = {Kechris, Alexander S.},
  title = {Measure and category in effective descriptive set theory},
  journal = {Ann. Math. Logic},
  year = {1972/73},
  volume = {5},
  pages = {337--384},
  fjournal = {Annals of Pure and Applied Logic},
  issn = {0168-0072},
  mrclass = {02K30 (02F35 04A15 28A05)},
  mrnumber = {MR0369072 (51 \#5308)},
  mrreviewer = {J. R. Shoenfield},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Kech73,
  author = {Kechris, Alexander S.},
  title = {Measure and category in effective descriptive set theory},
  journal = {Ann. Math. Logic},
  year = {1972/73},
  volume = {5},
  pages = {337--384},
  fjournal = {Annals of Pure and Applied Logic},
  issn = {0168-0072},
  mrclass = {02K30 (02F35 04A15 28A05)},
  mrnumber = {MR0369072 (51 \#5308)},
  mrreviewer = {J. R. Shoenfield},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Kechris75,
  author = {Kechris, Alexander S.},
  title = {The theory of countable analytical sets},
  journal = {Trans. Amer. Math. Soc.},
  year = {1975},
  volume = {202},
  pages = {259--297},
  fjournal = {Transactions of the American Mathematical Society},
  issn = {0002-9947},
  mrclass = {02K30 (02F35)},
  mrnumber = {MR0419235 (54 \#7259)},
  mrreviewer = {Peter G. Hinman},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Kechris75,
  author = {Kechris, Alexander S.},
  title = {The theory of countable analytical sets},
  journal = {Trans. Amer. Math. Soc.},
  year = {1975},
  volume = {202},
  pages = {259--297},
  fjournal = {Transactions of the American Mathematical Society},
  issn = {0002-9947},
  mrclass = {02K30 (02F35)},
  mrnumber = {MR0419235 (54 \#7259)},
  mrreviewer = {Peter G. Hinman},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{KMS-ta,
  author = {Bj{\o}rn Kjos-Hanssen and Wolfgang Merkle and Frank Stephan},
  title = {Kolmogorov Complexity and the Recursion Theorem},
  journal = {Trans. Amer. Math. Soc.},
  note = {In print.},
  date-added = {2010-02-10 15:35:50 +0100},
  date-modified = {2010-02-17 10:41:35 +0100},
  owner = {Rupert},
  timestamp = {2010.04.20}
}

@ARTICLE{Kol68,
  author = {Kolmogorov, A. N.},
  title = {Three approaches to the quantitative definition of information},
  journal = {Internat. J. Comput. Math.},
  year = {1968},
  volume = {2},
  pages = {157--168},
  fjournal = {International Journal of Computer Mathematics. Section A. Programming
	Theory and Methods. Section B. Computational Methods},
  issn = {0020-7160},
  mrclass = {94.20},
  mrnumber = {MR0243922 (39 \#5240)},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Kol68,
  author = {Kolmogorov, A. N.},
  title = {Three approaches to the quantitative definition of information},
  journal = {Internat. J. Comput. Math.},
  year = {1968},
  volume = {2},
  pages = {157--168},
  fjournal = {International Journal of Computer Mathematics. Section A. Programming
	Theory and Methods. Section B. Computational Methods},
  issn = {0020-7160},
  mrclass = {94.20},
  mrnumber = {MR0243922 (39 \#5240)},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{koppel,
  author = {Koppel, Moshe and Atlan, Henri},
  title = {An almost machine-independent theory of program-length complexity,
	sophistication, and induction},
  journal = {Inf. Sci.},
  year = {1991},
  volume = {56},
  pages = {23--33},
  number = {1-3},
  address = {New York, NY, USA},
  bdsk-url-1 = {http://dx.doi.org/10.1016/0020-0255(91)90021-L},
  doi = {http://dx.doi.org/10.1016/0020-0255(91)90021-L},
  issn = {0020-0255},
  owner = {Rupert},
  publisher = {Elsevier Science Inc.},
  timestamp = {2010.01.14}
}

@ARTICLE{koppel,
  author = {Koppel, Moshe and Atlan, Henri},
  title = {An almost machine-independent theory of program-length complexity,
	sophistication, and induction},
  journal = {Inf. Sci.},
  year = {1991},
  volume = {56},
  pages = {23--33},
  number = {1-3},
  address = {New York, NY, USA},
  doi = {http://dx.doi.org/10.1016/0020-0255(91)90021-L},
  issn = {0020-0255},
  owner = {Rupert},
  publisher = {Elsevier Science Inc.},
  timestamp = {2010.01.14}
}

@ARTICLE{KS,
  author = {Kucera, Anton\'{\i}n and Slaman, T.},
  title = {Randomness and Recursive Enumerability},
  journal = {SIAM J. Comput.},
  year = {2001},
  volume = {31},
  pages = {199--211},
  number = {1},
  address = {Philadelphia, PA, USA},
  bdsk-url-1 = {http://dx.doi.org/10.1137/S0097539799357441},
  doi = {http://dx.doi.org/10.1137/S0097539799357441},
  issn = {0097-5397},
  owner = {Rupert},
  publisher = {Society for Industrial and Applied Mathematics},
  timestamp = {2010.01.14}
}

@ARTICLE{KS,
  author = {Kucera, Anton\'{\i}n and Slaman, T.},
  title = {Randomness and Recursive Enumerability},
  journal = {SIAM J. Comput.},
  year = {2001},
  volume = {31},
  pages = {199--211},
  number = {1},
  address = {Philadelphia, PA, USA},
  doi = {http://dx.doi.org/10.1137/S0097539799357441},
  issn = {0097-5397},
  owner = {Rupert},
  publisher = {Society for Industrial and Applied Mathematics},
  timestamp = {2010.01.14}
}

@ARTICLE{kummer,
  author = {Kummer, Martin},
  title = {Kolmogorov Complexity and Instance Complexity of Recursively Enumerable
	Sets},
  journal = {SIAM J. Comput.},
  year = {1996},
  volume = {25},
  pages = {1123--1143},
  number = {6},
  address = {Philadelphia, PA, USA},
  bdsk-url-1 = {http://dx.doi.org/10.1137/S0097539794268789},
  doi = {http://dx.doi.org/10.1137/S0097539794268789},
  issn = {0097-5397},
  owner = {Rupert},
  publisher = {Society for Industrial and Applied Mathematics},
  timestamp = {2010.01.14}
}

@ARTICLE{kummer,
  author = {Kummer, Martin},
  title = {Kolmogorov Complexity and Instance Complexity of Recursively Enumerable
	Sets},
  journal = {SIAM J. Comput.},
  year = {1996},
  volume = {25},
  pages = {1123--1143},
  number = {6},
  address = {Philadelphia, PA, USA},
  doi = {http://dx.doi.org/10.1137/S0097539794268789},
  issn = {0097-5397},
  owner = {Rupert},
  publisher = {Society for Industrial and Applied Mathematics},
  timestamp = {2010.01.14}
}

@BOOK{Kun80,
  title = {Set theory},
  publisher = {North-Holland Publishing Co.},
  year = {1980},
  author = {Kunen, Kenneth},
  volume = {102},
  pages = {xvi+313},
  series = {Studies in Logic and the Foundations of Mathematics},
  address = {Amsterdam},
  note = {An introduction to independence proofs},
  isbn = {0-444-85401-0},
  mrclass = {03-02 (03E35 03Exx 04-02)},
  mrnumber = {MR597342 (82f:03001)},
  mrreviewer = {U. Felgner},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@BOOK{Kun80,
  title = {Set theory},
  publisher = {North-Holland Publishing Co.},
  year = {1980},
  author = {Kunen, Kenneth},
  volume = {102},
  pages = {xvi+313},
  series = {Studies in Logic and the Foundations of Mathematics},
  address = {Amsterdam},
  note = {An introduction to independence proofs},
  isbn = {0-444-85401-0},
  mrclass = {03-02 (03E35 03Exx 04-02)},
  mrnumber = {MR597342 (82f:03001)},
  mrreviewer = {U. Felgner},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@PHDTHESIS{Kur81,
  author = {Kurtz, S.},
  title = {Randomness and genericity in the degrees of unsolvability},
  school = {University of Illinois, Urbana},
  year = {1981},
  type = {Ph.{D.} {D}issertation},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@PHDTHESIS{Kur81,
  author = {Kurtz, S.},
  title = {Randomness and genericity in the degrees of unsolvability},
  school = {University of Illinois, Urbana},
  year = {1981},
  type = {Ph.{D.} {D}issertation},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@INCOLLECTION{Ku89,
  author = {Ku{\v{c}}era, Anton{\'{\i}}n},
  title = {On the use of diagonally nonrecursive functions},
  booktitle = {Logic Colloquium '87 (Granada, 1987)},
  publisher = {North-Holland},
  year = {1989},
  volume = {129},
  series = {Stud. Logic Found. Math.},
  pages = {219--239},
  address = {Amsterdam},
  mrclass = {03D30},
  mrnumber = {91c:03037},
  mrreviewer = {Barry Cooper},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@INCOLLECTION{Ku89,
  author = {Ku{\v{c}}era, Anton{\'{\i}}n},
  title = {On the use of diagonally nonrecursive functions},
  booktitle = {Logic Colloquium '87 (Granada, 1987)},
  publisher = {North-Holland},
  year = {1989},
  volume = {129},
  series = {Stud. Logic Found. Math.},
  pages = {219--239},
  address = {Amsterdam},
  mrclass = {03D30},
  mrnumber = {91c:03037},
  mrreviewer = {Barry Cooper},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@INCOLLECTION{Ku85,
  author = {Ku{\v{c}}era, Anton{\'{\i}}n},
  title = {Measure, {$\Pi\sp 0\sb 1$}-classes and complete extensions of {${\rm
	PA}$}},
  booktitle = {Recursion theory week (Oberwolfach, 1984)},
  publisher = {Springer},
  year = {1985},
  volume = {1141},
  series = {Lecture Notes in Math.},
  pages = {245--259},
  address = {Berlin},
  mrclass = {03D35 (03D30 03F30)},
  mrnumber = {87e:03102},
  mrreviewer = {A. M. Dawes},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@INCOLLECTION{Ku85,
  author = {Ku{\v{c}}era, Anton{\'{\i}}n},
  title = {Measure, {$\Pi\sp 0\sb 1$}-classes and complete extensions of {${\rm
	PA}$}},
  booktitle = {Recursion theory week (Oberwolfach, 1984)},
  publisher = {Springer},
  year = {1985},
  volume = {1141},
  series = {Lecture Notes in Math.},
  pages = {245--259},
  address = {Berlin},
  mrclass = {03D35 (03D30 03F30)},
  mrnumber = {87e:03102},
  mrreviewer = {A. M. Dawes},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{KuTe99,
  author = {Ku{\v{c}}era, Anton{\'{\i}}n and Terwijn, Sebastiaan A.},
  title = {Lowness for the class of random sets},
  journal = {J. Symbolic Logic},
  year = {1999},
  volume = {64},
  pages = {1396--1402},
  number = {4},
  coden = {JSYLA6},
  fjournal = {The Journal of Symbolic Logic},
  issn = {0022-4812},
  mrclass = {03D30},
  mrnumber = {2001j:03082},
  mrreviewer = {Marat M. Arslanov},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{KuTe99,
  author = {Ku{\v{c}}era, Anton{\'{\i}}n and Terwijn, Sebastiaan A.},
  title = {Lowness for the class of random sets},
  journal = {J. Symbolic Logic},
  year = {1999},
  volume = {64},
  pages = {1396--1402},
  number = {4},
  coden = {JSYLA6},
  fjournal = {The Journal of Symbolic Logic},
  issn = {0022-4812},
  mrclass = {03D30},
  mrnumber = {2001j:03082},
  mrreviewer = {Marat M. Arslanov},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{van90,
  author = {van Lambalgen, Michiel},
  title = {The axiomatization of randomness},
  journal = {J. Symbolic Logic},
  year = {1990},
  volume = {55},
  pages = {1143--1167},
  number = {3},
  coden = {JSYLA6},
  fjournal = {The Journal of Symbolic Logic},
  issn = {0022-4812},
  mrclass = {68Q30 (03B45 03C65 03C80 60A05)},
  mrnumber = {92f:68075},
  mrreviewer = {Xiang Li},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{van90,
  author = {van Lambalgen, Michiel},
  title = {The axiomatization of randomness},
  journal = {J. Symbolic Logic},
  year = {1990},
  volume = {55},
  pages = {1143--1167},
  number = {3},
  coden = {JSYLA6},
  fjournal = {The Journal of Symbolic Logic},
  issn = {0022-4812},
  mrclass = {68Q30 (03B45 03C65 03C80 60A05)},
  mrnumber = {92f:68075},
  mrreviewer = {Xiang Li},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@PHDTHESIS{van87,
  author = {van Lambalgen, M.},
  title = {Random sequences},
  school = {University of Amsterdam},
  year = {1987},
  type = {Ph.{D.} {D}issertation},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@PHDTHESIS{van87,
  author = {van Lambalgen, M.},
  title = {Random sequences},
  school = {University of Amsterdam},
  year = {1987},
  type = {Ph.{D.} {D}issertation},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{LL,
  author = {Lathrop, James I. and Lutz, Jack H.},
  title = {Recursive computational depth},
  journal = {Inf. Comput.},
  year = {1999},
  volume = {153},
  pages = {139--172},
  number = {2},
  address = {Duluth, MN, USA},
  doi = {http://dx.doi.org/10.1006/inco.1999.2794},
  issn = {0890-5401},
  owner = {Rupert},
  publisher = {Academic Press, Inc.},
  timestamp = {2010.01.14}
}

@ARTICLE{LL,
  author = {Lathrop, James I. and Lutz, Jack H.},
  title = {Recursive computational depth},
  journal = {Inf. Comput.},
  year = {1999},
  volume = {153},
  pages = {139--172},
  number = {2},
  address = {Duluth, MN, USA},
  bdsk-url-1 = {http://dx.doi.org/10.1006/inco.1999.2794},
  doi = {http://dx.doi.org/10.1006/inco.1999.2794},
  issn = {0890-5401},
  owner = {Rupert},
  publisher = {Academic Press, Inc.},
  timestamp = {2010.01.14}
}

@BOOK{Ler83,
  title = {Degrees of unsolvability},
  publisher = {Springer-Verlag},
  year = {1983},
  author = {Lerman, Manuel},
  pages = {xiii+307},
  series = {Perspectives in Mathematical Logic},
  address = {Berlin},
  note = {Local and global theory},
  isbn = {3-540-12155-2},
  mrclass = {03D30 (03-02 03D25 03D55)},
  mrnumber = {85h:03044},
  mrreviewer = {Barry Cooper},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@BOOK{Ler83,
  title = {Degrees of unsolvability},
  publisher = {Springer-Verlag},
  year = {1983},
  author = {Lerman, Manuel},
  pages = {xiii+307},
  series = {Perspectives in Mathematical Logic},
  address = {Berlin},
  note = {Local and global theory},
  isbn = {3-540-12155-2},
  mrclass = {03D30 (03-02 03D25 03D55)},
  mrnumber = {85h:03044},
  mrreviewer = {Barry Cooper},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{levin,
  author = {Levin, Leonid A.},
  title = {Randomness conservation inequalities; information and independence
	in mathematical theories},
  journal = {Inf. Control},
  year = {1984},
  volume = {61},
  pages = {15--37},
  number = {1},
  address = {San Diego, CA, USA},
  doi = {http://dx.doi.org/10.1016/S0019-9958(84)80060-1},
  issn = {0019-9958},
  owner = {Rupert},
  publisher = {Academic Press Professional, Inc.},
  timestamp = {2010.01.14}
}

@ARTICLE{levin,
  author = {Levin, Leonid A.},
  title = {Randomness conservation inequalities; information and independence
	in mathematical theories},
  journal = {Inf. Control},
  year = {1984},
  volume = {61},
  pages = {15--37},
  number = {1},
  address = {San Diego, CA, USA},
  bdsk-url-1 = {http://dx.doi.org/10.1016/S0019-9958(84)80060-1},
  doi = {http://dx.doi.org/10.1016/S0019-9958(84)80060-1},
  issn = {0019-9958},
  owner = {Rupert},
  publisher = {Academic Press Professional, Inc.},
  timestamp = {2010.01.14}
}

@ARTICLE{Lev73,
  author = {Levin, L. A.},
  title = {On the notion of a random sequence},
  journal = {Soviet Math. Dokl.},
  year = {1974},
  volume = {14(1973)},
  pages = {1413--1416},
  fjournal = {Soviet Mathematics. Doklady},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Lev73,
  author = {Levin, L. A.},
  title = {On the notion of a random sequence},
  journal = {Soviet Math. Dokl.},
  year = {1974},
  volume = {14(1973)},
  pages = {1413--1416},
  fjournal = {Soviet Mathematics. Doklady},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Lev74,
  author = {Levin, L. A.},
  title = {Laws of information conservation (non-growth) and aspects of the
	foundation of probability theory},
  journal = {Problems Inform. Transmission},
  year = {1974},
  volume = {10},
  pages = {206--210},
  number = {3},
  fjournal = {Problems of Information Transmission},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Lev74,
  author = {Levin, L. A.},
  title = {Laws of information conservation (non-growth) and aspects of the
	foundation of probability theory},
  journal = {Problems Inform. Transmission},
  year = {1974},
  volume = {10},
  pages = {206--210},
  number = {3},
  fjournal = {Problems of Information Transmission},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@BOOK{LiVitanyi2008,
  title = {An Introduction to Kolmogorov Complexity and Its Applications},
  publisher = {Springer},
  year = {2008},
  author = {Ming Li and Paul Vit{\'a}nyi},
  date-added = {2009-04-17 17:40:30 +0200},
  date-modified = {2009-04-17 17:55:51 +0200},
  owner = {Rupert},
  timestamp = {2010.04.20}
}

@ARTICLE{Louveau80,
  author = {Louveau, Alain},
  title = {A separation theorem for {$\Sigma \sp{1}\sb{1}$} sets},
  journal = {Trans. Amer. Math. Soc.},
  year = {1980},
  volume = {260},
  pages = {363--378},
  number = {2},
  coden = {TAMTAM},
  fjournal = {Transactions of the American Mathematical Society},
  issn = {0002-9947},
  mrclass = {04A15 (03E15 26A21 28A05 54H05)},
  mrnumber = {MR574785 (81j:04001)},
  mrreviewer = {Jacques Stern},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Louveau80,
  author = {Louveau, Alain},
  title = {A separation theorem for {$\Sigma \sp{1}\sb{1}$} sets},
  journal = {Trans. Amer. Math. Soc.},
  year = {1980},
  volume = {260},
  pages = {363--378},
  number = {2},
  coden = {TAMTAM},
  fjournal = {Transactions of the American Mathematical Society},
  issn = {0002-9947},
  mrclass = {04A15 (03E15 26A21 28A05 54H05)},
  mrnumber = {MR574785 (81j:04001)},
  mrreviewer = {Jacques Stern},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Louveau80,
  author = {Louveau, Alain},
  title = {A separation theorem for {$\Sigma \sp{1}\sb{1}$} sets},
  journal = {Trans. Amer. Math. Soc.},
  year = {1980},
  volume = {260},
  pages = {363--378},
  number = {2},
  coden = {TAMTAM},
  fjournal = {Transactions of the American Mathematical Society},
  issn = {0002-9947},
  mrclass = {04A15 (03E15 26A21 28A05 54H05)},
  mrnumber = {MR574785 (81j:04001)},
  mrreviewer = {Jacques Stern},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Louveau80,
  author = {Louveau, Alain},
  title = {A separation theorem for {$\Sigma \sp{1}\sb{1}$} sets},
  journal = {Trans. Amer. Math. Soc.},
  year = {1980},
  volume = {260},
  pages = {363--378},
  number = {2},
  coden = {TAMTAM},
  fjournal = {Transactions of the American Mathematical Society},
  issn = {0002-9947},
  mrclass = {04A15 (03E15 26A21 28A05 54H05)},
  mrnumber = {MR574785 (81j:04001)},
  mrreviewer = {Jacques Stern},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Man75,
  author = {Mansfield, Richard},
  title = {The non-existence of {$\Sigma \sp{1}\sb{2}$} well-orderings of the
	{C}antor set},
  journal = {Fund. Math.},
  year = {1975},
  volume = {86},
  pages = {279--282},
  number = {3},
  fjournal = {Polska Akademia Nauk. Fundamenta Mathematicae},
  issn = {0016-2736},
  mrclass = {02K30 (02K05)},
  mrnumber = {MR0387056 (52 \#7903)},
  mrreviewer = {F. R. Drake},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Man75,
  author = {Mansfield, Richard},
  title = {The non-existence of {$\Sigma \sp{1}\sb{2}$} well-orderings of the
	{C}antor set},
  journal = {Fund. Math.},
  year = {1975},
  volume = {86},
  pages = {279--282},
  number = {3},
  fjournal = {Polska Akademia Nauk. Fundamenta Mathematicae},
  issn = {0016-2736},
  mrclass = {02K30 (02K05)},
  mrnumber = {MR0387056 (52 \#7903)},
  mrreviewer = {F. R. Drake},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Man70,
  author = {Mansfield, Richard},
  title = {Perfect subsets of definable sets of real numbers},
  journal = {Pacific J. Math.},
  year = {1970},
  volume = {35},
  pages = {451--457},
  fjournal = {Pacific Journal of Mathematics},
  issn = {0030-8730},
  mrclass = {04.40 (02.00)},
  mrnumber = {MR0280380 (43 \#6100)},
  mrreviewer = {L. Bukovsk{\'y}},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Man70,
  author = {Mansfield, Richard},
  title = {Perfect subsets of definable sets of real numbers},
  journal = {Pacific J. Math.},
  year = {1970},
  volume = {35},
  pages = {451--457},
  fjournal = {Pacific Journal of Mathematics},
  issn = {0030-8730},
  mrclass = {04.40 (02.00)},
  mrnumber = {MR0280380 (43 \#6100)},
  mrreviewer = {L. Bukovsk{\'y}},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Martin76,
  author = {Martin, Donald A.},
  title = {Proof of a conjecture of {F}riedman},
  journal = {Proc. Amer. Math. Soc.},
  year = {1976},
  volume = {55},
  pages = {129},
  number = {1},
  fjournal = {Proceedings of the American Mathematical Society},
  issn = {0002-9939},
  mrclass = {02F35},
  mrnumber = {MR0406785 (53 \#10571)},
  mrreviewer = {Manuel Lerman},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Martin75,
  author = {Martin, Donald A.},
  title = {Borel determinacy},
  journal = {Ann. of Math. (2)},
  year = {1975},
  volume = {102},
  pages = {363--371},
  number = {2},
  fjournal = {Annals of Mathematics. Second Series},
  issn = {0003-486X},
  mrclass = {02K30 (90D05 04A15)},
  mrnumber = {MR0403976 (53 \#7785)},
  mrreviewer = {John P. Burgess},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Martin66,
  author = {Martin, Donald A.},
  title = {Classes of recursively enumerable sets and degrees of unsolvability},
  journal = {Z. Math. Logik Grundlagen Math.},
  year = {1966},
  volume = {12},
  pages = {295--310},
  fjournal = {Zeitschrift f\"ur Mathematische Logik und Grundlagen der Mathematik},
  mrclass = {02.74},
  mrnumber = {MR0224469 (37 \#68)},
  mrreviewer = {R. A. DiPaola},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{MS70,
  author = {Martin, D. A. and Solovay, R. M.},
  title = {Internal {C}ohen extensions},
  journal = {Ann. Math. Logic},
  year = {1970},
  volume = {2},
  pages = {143--178},
  number = {2},
  fjournal = {Annals of Pure and Applied Logic},
  issn = {0168-0072},
  mrclass = {02.60},
  mrnumber = {MR0270904 (42 \#5787)},
  mrreviewer = {L. Bukovsk{\'y}},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{MS70,
  author = {Martin, D. A. and Solovay, R. M.},
  title = {Internal {C}ohen extensions},
  journal = {Ann. Math. Logic},
  year = {1970},
  volume = {2},
  pages = {143--178},
  number = {2},
  fjournal = {Annals of Pure and Applied Logic},
  issn = {0168-0072},
  mrclass = {02.60},
  mrnumber = {MR0270904 (42 \#5787)},
  mrreviewer = {L. Bukovsk{\'y}},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{ML71,
  author = {Martin-L{\"o}f, Per},
  title = {Complexity oscillations in infinite binary sequences},
  journal = {Z. Wahrscheinlichkeitstheorie und Verw. Gebiete},
  year = {1971},
  volume = {19},
  pages = {225--230},
  mrclass = {60A05 (68A20 02E15)},
  mrnumber = {MR0451322 (56 \#9609)},
  mrreviewer = {Settimo Termini},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{ML71,
  author = {Martin-L{\"o}f, Per},
  title = {Complexity oscillations in infinite binary sequences},
  journal = {Z. Wahrscheinlichkeitstheorie und Verw. Gebiete},
  year = {1971},
  volume = {19},
  pages = {225--230},
  mrclass = {60A05 (68A20 02E15)},
  mrnumber = {MR0451322 (56 \#9609)},
  mrreviewer = {Settimo Termini},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@INCOLLECTION{ML70,
  author = {Martin-L{\"o}f, Per},
  title = {On the notion of randomness},
  booktitle = {Intuitionism and Proof Theory (Proc. Conf., Buffalo, N.Y., 1968)},
  publisher = {North-Holland},
  year = {1970},
  pages = {73--78},
  address = {Amsterdam},
  mrclass = {60.02 (02.00)},
  mrnumber = {MR0275483 (43 \#1237)},
  mrreviewer = {J. E. Fenstad},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@INCOLLECTION{ML70,
  author = {Martin-L{\"o}f, Per},
  title = {On the notion of randomness},
  booktitle = {Intuitionism and Proof Theory (Proc. Conf., Buffalo, N.Y., 1968)},
  publisher = {North-Holland},
  year = {1970},
  pages = {73--78},
  address = {Amsterdam},
  mrclass = {60.02 (02.00)},
  mrnumber = {MR0275483 (43 \#1237)},
  mrreviewer = {J. E. Fenstad},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{ML66,
  author = {Martin-L{\"o}f, Per},
  title = {The definition of random sequences},
  journal = {Information and Control},
  year = {1966},
  volume = {9},
  pages = {602--619},
  fjournal = {Information and Computation},
  issn = {0890-5401},
  mrclass = {94.20 (60.00)},
  mrnumber = {MR0223179 (36 \#6228)},
  mrreviewer = {F. J. Beutler},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{ML66,
  author = {Martin-L{\"o}f, Per},
  title = {The definition of random sequences},
  journal = {Information and Control},
  year = {1966},
  volume = {9},
  pages = {602--619},
  fjournal = {Information and Computation},
  issn = {0890-5401},
  mrclass = {94.20 (60.00)},
  mrnumber = {MR0223179 (36 \#6228)},
  mrreviewer = {F. J. Beutler},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Merkle2008,
  author = {Wolfgang Merkle},
  title = {The complexity of stochastic sequences},
  journal = {Journal of Computer and System Sciences},
  year = {2008},
  volume = {74},
  pages = {350--357},
  number = {3},
  date-added = {2009-04-09 16:13:11 +0200},
  date-modified = {2009-04-09 16:13:11 +0200},
  owner = {Rupert},
  timestamp = {2010.04.20}
}

@ARTICLE{Merkle2008,
  author = {Wolfgang Merkle},
  title = {The complexity of stochastic sequences},
  journal = {Journal of Computer and System Sciences},
  year = {2008},
  volume = {74},
  pages = {350--357},
  number = {3},
  date-added = {2009-04-09 16:13:11 +0200},
  date-modified = {2009-04-09 16:13:11 +0200}
}

@ARTICLE{Merkle2008,
  author = {Wolfgang Merkle},
  title = {The complexity of stochastic sequences},
  journal = {Journal of Computer and System Sciences},
  year = {2008},
  volume = {74},
  pages = {350--357},
  number = {3},
  date-added = {2009-04-09 16:13:11 +0200},
  date-modified = {2009-04-09 16:13:11 +0200},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Merkle2008,
  author = {Wolfgang Merkle},
  title = {The complexity of stochastic sequences},
  journal = {Journal of Computer and System Sciences},
  year = {2008},
  volume = {74},
  pages = {350--357},
  number = {3},
  date-added = {2009-04-09 16:13:11 +0200},
  date-modified = {2009-04-09 16:13:11 +0200},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Merkle2008,
  author = {Wolfgang Merkle},
  title = {The complexity of stochastic sequences},
  journal = {Journal of Computer and System Sciences},
  year = {2008},
  volume = {74},
  pages = {350--357},
  number = {3},
  date-added = {2009-04-09 16:13:11 +0200},
  date-modified = {2009-04-09 16:13:11 +0200},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Merkle2008,
  author = {Wolfgang Merkle},
  title = {The complexity of stochastic sequences},
  journal = {Journal of Computer and System Sciences},
  year = {2008},
  volume = {74},
  pages = {350--357},
  number = {3},
  date-added = {2009-04-09 16:13:11 +0200},
  date-modified = {2009-04-09 16:13:11 +0200},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Merkle2003,
  author = {Wolfgang Merkle},
  title = {The {K}olmogorov-{L}oveland stochastic sequences are not closed under
	selecting subsequences},
  journal = {Journal of Symbolic Logic},
  year = {2003},
  volume = {68},
  pages = {1362--1376},
  date-added = {2009-04-17 23:37:59 +0200},
  date-modified = {2009-05-09 14:22:57 +0200},
  owner = {Rupert},
  timestamp = {2010.04.20}
}

@ARTICLE{Merkle2003,
  author = {Wolfgang Merkle},
  title = {The {K}olmogorov-{L}oveland stochastic sequences are not closed under
	selecting subsequences},
  journal = {Journal of Symbolic Logic},
  year = {2003},
  volume = {68},
  pages = {1362--1376},
  date-added = {2009-04-17 23:37:59 +0200},
  date-modified = {2009-05-09 14:22:57 +0200}
}

@ARTICLE{Merkle2003,
  author = {Wolfgang Merkle},
  title = {The {K}olmogorov-{L}oveland stochastic sequences are not closed under
	selecting subsequences},
  journal = {Journal of Symbolic Logic},
  year = {2003},
  volume = {68},
  pages = {1362--1376},
  date-added = {2009-04-17 23:37:59 +0200},
  date-modified = {2009-05-09 14:22:57 +0200},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Merkle2003,
  author = {Wolfgang Merkle},
  title = {The {K}olmogorov-{L}oveland stochastic sequences are not closed under
	selecting subsequences},
  journal = {Journal of Symbolic Logic},
  year = {2003},
  volume = {68},
  pages = {1362--1376},
  date-added = {2009-04-17 23:37:59 +0200},
  date-modified = {2009-05-09 14:22:57 +0200},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Merkle2003,
  author = {Wolfgang Merkle},
  title = {The {K}olmogorov-{L}oveland stochastic sequences are not closed under
	selecting subsequences},
  journal = {Journal of Symbolic Logic},
  year = {2003},
  volume = {68},
  pages = {1362--1376},
  date-added = {2009-04-17 23:37:59 +0200},
  date-modified = {2009-05-09 14:22:57 +0200},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Merkle2003,
  author = {Wolfgang Merkle},
  title = {The {K}olmogorov-{L}oveland stochastic sequences are not closed under
	selecting subsequences},
  journal = {Journal of Symbolic Logic},
  year = {2003},
  volume = {68},
  pages = {1362--1376},
  date-added = {2009-04-17 23:37:59 +0200},
  date-modified = {2009-05-09 14:22:57 +0200},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{MerkleMNRS2006,
  author = {Wolfgang Merkle and Joseph S. Miller and Andr{\'e} Nies and Jan Reimann
	and Frank Stephan},
  title = {{K}olmogorov-{L}oveland randomness and stochasticity},
  journal = {Annals of Pure and Applied Logic},
  year = {2006},
  volume = {138},
  pages = {183--210},
  number = {1-3},
  date-added = {2009-04-09 16:14:17 +0200},
  date-modified = {2009-04-09 16:14:17 +0200},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{MerkleMNRS2006,
  author = {Wolfgang Merkle and Joseph S. Miller and Andr{\'e} Nies and Jan Reimann
	and Frank Stephan},
  title = {{K}olmogorov-{L}oveland randomness and stochasticity},
  journal = {Annals of Pure and Applied Logic},
  year = {2006},
  volume = {138},
  pages = {183--210},
  number = {1-3},
  date-added = {2009-04-09 16:14:17 +0200},
  date-modified = {2009-04-09 16:14:17 +0200},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{MerkleMNRS2006,
  author = {Wolfgang Merkle and Joseph S. Miller and Andr{\'e} Nies and Jan Reimann
	and Frank Stephan},
  title = {{K}olmogorov-{L}oveland randomness and stochasticity},
  journal = {Annals of Pure and Applied Logic},
  year = {2006},
  volume = {138},
  pages = {183--210},
  number = {1-3},
  date-added = {2009-04-09 16:14:17 +0200},
  date-modified = {2009-04-09 16:14:17 +0200},
  owner = {Rupert},
  timestamp = {2010.04.20}
}

@ARTICLE{MerkleMNRS2006,
  author = {Wolfgang Merkle and Joseph S. Miller and Andr{\'e} Nies and Jan Reimann
	and Frank Stephan},
  title = {{K}olmogorov-{L}oveland randomness and stochasticity},
  journal = {Annals of Pure and Applied Logic},
  year = {2006},
  volume = {138},
  pages = {183--210},
  number = {1-3},
  date-added = {2009-04-09 16:14:17 +0200},
  date-modified = {2009-04-09 16:14:17 +0200}
}

@ARTICLE{MerkleMNRS2006,
  author = {Wolfgang Merkle and Joseph S. Miller and Andr{\'e} Nies and Jan Reimann
	and Frank Stephan},
  title = {{K}olmogorov-{L}oveland randomness and stochasticity},
  journal = {Annals of Pure and Applied Logic},
  year = {2006},
  volume = {138},
  pages = {183--210},
  number = {1-3},
  date-added = {2009-04-09 16:14:17 +0200},
  date-modified = {2009-04-09 16:14:17 +0200},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{MerkleMNRS2006,
  author = {Wolfgang Merkle and Joseph S. Miller and Andr{\'e} Nies and Jan Reimann
	and Frank Stephan},
  title = {{K}olmogorov-{L}oveland randomness and stochasticity},
  journal = {Annals of Pure and Applied Logic},
  year = {2006},
  volume = {138},
  pages = {183--210},
  number = {1-3},
  date-added = {2009-04-09 16:14:17 +0200},
  date-modified = {2009-04-09 16:14:17 +0200},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Miller89,
  author = {Miller, Arnold W.},
  title = {Infinite combinatorics and definability},
  journal = {Ann. Pure Appl. Logic},
  year = {1989},
  volume = {41},
  pages = {179--203},
  number = {2},
  coden = {APALD7},
  fjournal = {Annals of Pure and Applied Logic},
  issn = {0168-0072},
  mrclass = {03E15 (03E05)},
  mrnumber = {MR983001 (90b:03070)},
  mrreviewer = {A. L{\'e}vy},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Miller89,
  author = {Miller, Arnold W.},
  title = {Infinite combinatorics and definability},
  journal = {Ann. Pure Appl. Logic},
  year = {1989},
  volume = {41},
  pages = {179--203},
  number = {2},
  coden = {APALD7},
  fjournal = {Annals of Pure and Applied Logic},
  issn = {0168-0072},
  mrclass = {03E15 (03E05)},
  mrnumber = {MR983001 (90b:03070)},
  mrreviewer = {A. L{\'e}vy},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{MillerN2006,
  author = {Joseph Miller and Andr{\'e} Nies},
  title = {Randomness and computability: open questions},
  journal = {Bulletin of Symbolic Logic},
  year = {2006},
  volume = {12},
  pages = {390--410},
  number = {3},
  date-added = {2009-04-30 06:50:33 +0200},
  date-modified = {2009-04-30 06:50:33 +0200},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{MillerN2006,
  author = {Joseph Miller and Andr{\'e} Nies},
  title = {Randomness and computability: open questions},
  journal = {Bulletin of Symbolic Logic},
  year = {2006},
  volume = {12},
  pages = {390--410},
  number = {3},
  date-added = {2009-04-30 06:50:33 +0200},
  date-modified = {2009-04-30 06:50:33 +0200},
  owner = {Rupert},
  timestamp = {2010.04.20}
}

@ARTICLE{MillerN2006,
  author = {Joseph Miller and Andr{\'e} Nies},
  title = {Randomness and computability: open questions},
  journal = {Bulleti. o.\ Symbolic Logic},
  year = {2006},
  volume = {12},
  pages = {390--410},
  number = {3},
  date-added = {2009-04-30 06:50:33 +0200},
  date-modified = {2009-04-30 06:50:33 +0200}
}

@ARTICLE{MillerN2006,
  author = {Joseph Miller and Andr{\'e} Nies},
  title = {Randomness and computability: open questions},
  journal = {Bulleti. o.\ Symbolic Logic},
  year = {2006},
  volume = {12},
  pages = {390--410},
  number = {3},
  date-added = {2009-04-30 06:50:33 +0200},
  date-modified = {2009-04-30 06:50:33 +0200},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{MillerN2006,
  author = {Joseph Miller and Andr{\'e} Nies},
  title = {Randomness and computability: open questions},
  journal = {Bulletin of Symbolic Logic},
  year = {2006},
  volume = {12},
  pages = {390--410},
  number = {3},
  date-added = {2009-04-30 06:50:33 +0200},
  date-modified = {2009-04-30 06:50:33 +0200},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{MillerN2006,
  author = {Joseph Miller and Andr{\'e} Nies},
  title = {Randomness and computability: open questions},
  journal = {Bulletin of Symbolic Logic},
  year = {2006},
  volume = {12},
  pages = {390--410},
  number = {3},
  date-added = {2009-04-30 06:50:33 +0200},
  date-modified = {2009-04-30 06:50:33 +0200},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{M,
  author = {Miller, Joseph S.},
  title = {The K-degrees, low for K-degrees and weakly low for K-degrees},
  journal = {Notre Dame Journal of Formal Logic},
  year = {2010},
  volume = {50(4)},
  pages = {381--391},
  number = {4},
  bdsk-url-1 = {http://www.math.wisc.edu/~jmiller/Papers/WLK.pdf},
  citeulike-article-id = {4207314},
  citeulike-linkout-0 = {http://www.math.wisc.edu/~jmiller/Papers/WLK.pdf},
  keywords = {randomness},
  owner = {Rupert},
  posted-at = {2009-03-22 14:56:05},
  priority = {2},
  timestamp = {2010.01.14},
  url = {http://www.math.wisc.edu/~jmiller/Papers/WLK.pdf}
}

@ARTICLE{Mil04,
  author = {Miller, Joseph S.},
  title = {Every 2-random real is {K}olmogorov random},
  journal = {J. Symbolic Logic},
  year = {2004},
  volume = {69},
  number = {3},
  fjournal = {The Journal of Symbolic Logic},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Mil04,
  author = {Miller, Joseph S.},
  title = {Every 2-random real is {K}olmogorov random},
  journal = {J. Symbolic Logic},
  year = {2004},
  volume = {69},
  number = {3},
  fjournal = {The Journal of Symbolic Logic},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@UNPUBLISHED{MYa,
  author = {Miller, Joseph S. and Yu, Liang},
  title = {On initial segment complexity and degrees of randomness},
  note = {To appear},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@UNPUBLISHED{MYa,
  author = {Miller, Joseph S. and Yu, Liang},
  title = {On initial segment complexity and degrees of randomness},
  note = {To appear},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@UNPUBLISHED{MYb,
  author = {Miller, Joseph S. and Yu, Liang},
  title = {Oscillation in the initial segment complexity of random reals},
  note = {In preparation},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@UNPUBLISHED{MYb,
  author = {Miller, Joseph S. and Yu, Liang},
  title = {Oscillation in the initial segment complexity of random reals},
  note = {In preparation},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Mon05,
  author = {Montalb{\'a}n, Antonio},
  title = {Up to equimorphism, hyperarithmetic is recursive},
  journal = {J. Symbolic Logic},
  year = {2005},
  volume = {70},
  pages = {360--378},
  number = {2},
  coden = {JSYLA6},
  fjournal = {The Journal of Symbolic Logic},
  issn = {0022-4812},
  mrclass = {03D45},
  mrnumber = {MR2140035 (2006a:03063)},
  mrreviewer = {Rodney G. Downey},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Mon05,
  author = {Montalb{\'a}n, Antonio},
  title = {Up to equimorphism, hyperarithmetic is recursive},
  journal = {J. Symbolic Logic},
  year = {2005},
  volume = {70},
  pages = {360--378},
  number = {2},
  coden = {JSYLA6},
  fjournal = {The Journal of Symbolic Logic},
  issn = {0022-4812},
  mrclass = {03D45},
  mrnumber = {MR2140035 (2006a:03063)},
  mrreviewer = {Rodney G. Downey},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@BOOK{Mosch1980,
  title = {Descriptive set theory},
  publisher = {North-Holland Publishing Co.},
  year = {1980},
  author = {Moschovakis, Yiannis N.},
  volume = {100},
  pages = {xii+637},
  series = {Studies in Logic and the Foundations of Mathematics},
  address = {Amsterdam},
  isbn = {0-444-85305-7},
  mrclass = {03-02 (03D55 03E15 04A15 28A05 54H05)},
  mrnumber = {MR561709 (82e:03002)},
  mrreviewer = {Peter G. Hinman},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@BOOK{Mosch1980,
  title = {Descriptive set theory},
  publisher = {North-Holland Publishing Co.},
  year = {1980},
  author = {Moschovakis, Yiannis N.},
  volume = {100},
  pages = {xii+637},
  series = {Studies in Logic and the Foundations of Mathematics},
  address = {Amsterdam},
  isbn = {0-444-85305-7},
  mrclass = {03-02 (03D55 03E15 04A15 28A05 54H05)},
  mrnumber = {MR561709 (82e:03002)},
  mrreviewer = {Peter G. Hinman},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Mostowski49,
  author = {Mostowski, Andrzej},
  title = {An undecidable arithmetical statement},
  journal = {Fund. Math.},
  year = {1949},
  volume = {36},
  pages = {143--164},
  fjournal = {Polska Akademia Nauk. Fundamenta Mathematicae},
  issn = {0016-2736},
  mrclass = {02.0X},
  mrnumber = {MR0035721 (12,2d)},
  mrreviewer = {A. Heyting},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{MuchnikSU1998,
  author = {Andrei A. Muchnik and Alexei Semenov and Vladimir Uspensky},
  title = {Mathematical Metaphysics of Randomness},
  journal = {Theoretical Computer Science},
  year = {1998},
  volume = {207},
  pages = {263--317},
  number = {2},
  date-added = {2009-04-09 16:13:21 +0200},
  date-modified = {2009-04-09 16:13:21 +0200}
}

@ARTICLE{MuchnikSU1998,
  author = {Andrei A. Muchnik and Alexei Semenov and Vladimir Uspensky},
  title = {Mathematical Metaphysics of Randomness},
  journal = {Theoretical Computer Science},
  year = {1998},
  volume = {207},
  pages = {263--317},
  number = {2},
  date-added = {2009-04-09 16:13:21 +0200},
  date-modified = {2009-04-09 16:13:21 +0200},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{MuchnikSU1998,
  author = {Andrei A. Muchnik and Alexei Semenov and Vladimir Uspensky},
  title = {Mathematical Metaphysics of Randomness},
  journal = {Theoretical Computer Science},
  year = {1998},
  volume = {207},
  pages = {263--317},
  number = {2},
  date-added = {2009-04-09 16:13:21 +0200},
  date-modified = {2009-04-09 16:13:21 +0200},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{MuchnikSU1998,
  author = {Andrei A. Muchnik and Alexei Semenov and Vladimir Uspensky},
  title = {Mathematical Metaphysics of Randomness},
  journal = {Theoretical Computer Science},
  year = {1998},
  volume = {207},
  pages = {263--317},
  number = {2},
  date-added = {2009-04-09 16:13:21 +0200},
  date-modified = {2009-04-09 16:13:21 +0200},
  owner = {Rupert},
  timestamp = {2010.04.20}
}

@ARTICLE{Muchnik56,
  author = {Mu{\v{c}}nik, A. A.},
  title = {On the unsolvability of the problem of reducibility in the theory
	of algorithms},
  journal = {Dokl. Akad. Nauk SSSR (N.S.)},
  year = {1956},
  volume = {108},
  pages = {194--197},
  fjournal = {Doklady Akademii Nauk SSSR},
  issn = {0002-3264},
  mrclass = {02.0X},
  mrnumber = {MR0081859 (18,457a)},
  mrreviewer = {E. J. Cogan},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Muchnik56,
  author = {Mu{\v{c}}nik, A. A.},
  title = {On the unsolvability of the problem of reducibility in the theory
	of algorithms},
  journal = {Dokl. Akad. Nauk SSSR (N.S.)},
  year = {1956},
  volume = {108},
  pages = {194--197},
  fjournal = {Doklady Akademii Nauk SSSR},
  issn = {0002-3264},
  mrclass = {02.0X},
  mrnumber = {MR0081859 (18,457a)},
  mrreviewer = {E. J. Cogan},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Nies,
  author = {Nies, Andr{\'e}},
  title = {Lowness properties and randomness},
  journal = {Adv. Math.},
  note = {To appear},
  fjournal = {Advances in Mathematics},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Nies,
  author = {Nies, Andr{\'e}},
  title = {Lowness properties and randomness},
  journal = {Adv. Math.},
  note = {To appear},
  fjournal = {Advances in Mathematics},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@BOOK{Niebook,
  title = {Computability and Randomness},
  publisher = {Oxford University Press},
  year = {2009},
  author = {Nies, Andr{\'e}},
  volume = {51},
  pages = {xvi+433},
  series = {Oxford Logic Guides},
  address = {Oxford},
  isbn = {978-0-19-923076-1},
  mrclass = {03-02 (03D25 03D28 03D32 03D55 91A60)},
  mrnumber = {MR2548883},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@BOOK{Niebook,
  title = {Computability and Randomness},
  publisher = {Oxford University Press},
  year = {2009},
  author = {Nies, Andr{\'e}},
  volume = {51},
  pages = {xvi+433},
  series = {Oxford Logic Guides},
  address = {Oxford},
  isbn = {978-0-19-923076-1},
  mrclass = {03-02 (03D25 03D28 03D32 03D55 91A60)},
  mrnumber = {MR2548883},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Nies97,
  author = {Nies, Andr{\'e}},
  title = {Intervals of the lattice of computably enumerable sets and effective
	{B}oolean algebras},
  journal = {Bull. London Math. Soc.},
  year = {1997},
  volume = {29},
  pages = {683--692},
  number = {6},
  coden = {LMSBBT},
  fjournal = {The Bulletin of the London Mathematical Society},
  issn = {0024-6093},
  mrclass = {03D25 (03C57 03D35)},
  mrnumber = {MR1468055 (98j:03057)},
  mrreviewer = {Marat M. Arslanov},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Nies97,
  author = {Nies, Andr{\'e}},
  title = {Intervals of the lattice of computably enumerable sets and effective
	{B}oolean algebras},
  journal = {Bull. London Math. Soc.},
  year = {1997},
  volume = {29},
  pages = {683--692},
  number = {6},
  coden = {LMSBBT},
  fjournal = {The Bulletin of the London Mathematical Society},
  issn = {0024-6093},
  mrclass = {03D25 (03C57 03D35)},
  mrnumber = {MR1468055 (98j:03057)},
  mrreviewer = {Marat M. Arslanov},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{NST,
  author = {Nies, Andr{\'e} and Stephan, Frank and Terwijn, Sebastiaan A.},
  title = {Randomness, relativization and {T}uring degrees},
  journal = {J. Symbolic Logic},
  year = {2005},
  volume = {70},
  pages = {515--535},
  number = {2},
  coden = {JSYLA6},
  fjournal = {The Journal of Symbolic Logic},
  issn = {0022-4812},
  mrclass = {68Q30 (03D15 03D28 03D80 28E15)},
  mrnumber = {MR2140044},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{NST,
  author = {Nies, Andr{\'e} and Stephan, Frank and Terwijn, Sebastiaan A.},
  title = {Randomness, relativization and {T}uring degrees},
  journal = {J. Symbolic Logic},
  year = {2005},
  volume = {70},
  pages = {515--535},
  number = {2},
  coden = {JSYLA6},
  fjournal = {The Journal of Symbolic Logic},
  issn = {0022-4812},
  mrclass = {68Q30 (03D15 03D28 03D80 28E15)},
  mrnumber = {MR2140044},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@BOOK{Oxt80,
  title = {Measure and category},
  publisher = {Springer-Verlag},
  year = {1980},
  author = {Oxtoby, John C.},
  volume = {2},
  pages = {x+106},
  series = {Graduate Texts in Mathematics},
  address = {New York},
  edition = {Second},
  note = {A survey of the analogies between topological and measure spaces},
  isbn = {0-387-90508-1},
  mrclass = {28-02 (54H99)},
  mrnumber = {81j:28003},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@BOOK{Oxt80,
  title = {Measure and category},
  publisher = {Springer-Verlag},
  year = {1980},
  author = {Oxtoby, John C.},
  volume = {2},
  pages = {x+106},
  series = {Graduate Texts in Mathematics},
  address = {New York},
  edition = {Second},
  note = {A survey of the analogies between topological and measure spaces},
  isbn = {0-387-90508-1},
  mrclass = {28-02 (54H99)},
  mrnumber = {81j:28003},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@BOOK{Rogers67,
  title = {Theory of recursive functions and effective computability},
  publisher = {McGraw-Hill Book Co.},
  year = {1967},
  author = {Rogers, Jr., Hartley},
  pages = {xx+482},
  address = {New York},
  mrclass = {02.70},
  mrnumber = {MR0224462 (37 \#61)},
  mrreviewer = {R. L. Goodstein},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@BOOK{Rogers67,
  title = {Theory of recursive functions and effective computability},
  publisher = {McGraw-Hill Book Co.},
  year = {1967},
  author = {Rogers, Jr., Hartley},
  pages = {xx+482},
  address = {New York},
  mrclass = {02.70},
  mrnumber = {MR0224462 (37 \#61)},
  mrreviewer = {R. L. Goodstein},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@BOOK{Sacks90,
  title = {Higher recursion theory},
  publisher = {Springer-Verlag},
  year = {1990},
  author = {Sacks, Gerald E.},
  pages = {xvi+344},
  series = {Perspectives in Mathematical Logic},
  address = {Berlin},
  isbn = {3-540-19305-7},
  mrclass = {03D60 (03-02 03D65)},
  mrnumber = {MR1080970 (92a:03062)},
  mrreviewer = {Dag Normann},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@BOOK{Sacks90,
  title = {Higher recursion theory},
  publisher = {Springer-Verlag},
  year = {1990},
  author = {Sacks, Gerald E.},
  pages = {xvi+344},
  series = {Perspectives in Mathematical Logic},
  address = {Berlin},
  isbn = {3-540-19305-7},
  mrclass = {03D60 (03-02 03D65)},
  mrnumber = {MR1080970 (92a:03062)},
  mrreviewer = {Dag Normann},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Sa76,
  author = {Sacks, Gerald E.},
  title = {Countable admissible ordinals and hyperdegrees},
  journal = {Advances in Math.},
  year = {1976},
  volume = {20},
  pages = {213--262},
  number = {2},
  fjournal = {Advances in Mathematics},
  issn = {0001-8708},
  mrclass = {02F27},
  mrnumber = {MR0429523 (55 \#2536)},
  mrreviewer = {Stephen G. Simpson},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Sa76,
  author = {Sacks, Gerald E.},
  title = {Countable admissible ordinals and hyperdegrees},
  journal = {Advances in Math.},
  year = {1976},
  volume = {20},
  pages = {213--262},
  number = {2},
  fjournal = {Advances in Mathematics},
  issn = {0001-8708},
  mrclass = {02F27},
  mrnumber = {MR0429523 (55 \#2536)},
  mrreviewer = {Stephen G. Simpson},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Sack69,
  author = {Sacks, Gerald E.},
  title = {Measure-theoretic uniformity in recursion theory and set theory},
  journal = {Trans. Amer. Math. Soc.},
  year = {1969},
  volume = {142},
  pages = {381--420},
  fjournal = {Transactions of the American Mathematical Society},
  issn = {0002-9947},
  mrclass = {02.68},
  mrnumber = {MR0253895 (40 \#7108)},
  mrreviewer = {S. Feferman},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Sack69,
  author = {Sacks, Gerald E.},
  title = {Measure-theoretic uniformity in recursion theory and set theory},
  journal = {Trans. Amer. Math. Soc.},
  year = {1969},
  volume = {142},
  pages = {381--420},
  fjournal = {Transactions of the American Mathematical Society},
  issn = {0002-9947},
  mrclass = {02.68},
  mrnumber = {MR0253895 (40 \#7108)},
  mrreviewer = {S. Feferman},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@BOOK{Sacks63,
  title = {Degrees of unsolvability},
  publisher = {Princeton University Press},
  year = {1963},
  author = {Sacks, Gerald E.},
  pages = {ix+174},
  address = {Princeton, N.J.},
  mrclass = {02.70},
  mrnumber = {32 \#4013},
  mrreviewer = {K. Appel},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@BOOK{Sacks63,
  title = {Degrees of unsolvability},
  publisher = {Princeton University Press},
  year = {1963},
  author = {Sacks, Gerald E.},
  pages = {ix+174},
  address = {Princeton, N.J.},
  mrclass = {02.70},
  mrnumber = {32 \#4013},
  mrreviewer = {K. Appel},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@BOOK{Schnorr1971,
  title = {Zuf{\"a}lligkeit und {W}ahrscheinlichkeit},
  publisher = {Springer-Verlag, Berlin-Heidelberg-New York},
  year = {1971},
  author = {Claus Schnorr},
  volume = {218},
  series = {Lecture Notes in Mathematics},
  date-added = {2009-04-09 16:13:29 +0200},
  date-modified = {2009-04-09 16:13:29 +0200}
}

@BOOK{Schnorr1971,
  title = {Zuf{\"a}lligkeit und {W}ahrscheinlichkeit},
  publisher = {Springer-Verlag, Berlin-Heidelberg-New York},
  year = {1971},
  author = {Claus Schnorr},
  volume = {218},
  series = {Lecture Notes in Mathematics},
  date-added = {2009-04-09 16:13:29 +0200},
  date-modified = {2009-04-09 16:13:29 +0200},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@BOOK{Schnorr1971,
  title = {Zuf{\"a}lligkeit und {W}ahrscheinlichkeit},
  publisher = {Springer-Verlag, Berlin-Heidelberg-New York},
  year = {1971},
  author = {Claus Schnorr},
  volume = {218},
  series = {Lecture Notes in Mathematics},
  date-added = {2009-04-09 16:13:29 +0200},
  date-modified = {2009-04-09 16:13:29 +0200},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@BOOK{Schnorr1971,
  title = {Zuf{\"a}lligkeit und {W}ahrscheinlichkeit},
  publisher = {Springer-Verlag, Berlin-Heidelberg-New York},
  year = {1971},
  author = {Claus Schnorr},
  volume = {218},
  series = {Lecture Notes in Mathematics},
  date-added = {2009-04-09 16:13:29 +0200},
  date-modified = {2009-04-09 16:13:29 +0200},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@BOOK{Schnorr1971,
  title = {Zuf{\"a}lligkeit und {W}ahrscheinlichkeit},
  publisher = {Springer-Verlag, Berlin-Heidelberg-New York},
  year = {1971},
  author = {Claus Schnorr},
  volume = {218},
  series = {Lecture Notes in Mathematics},
  date-added = {2009-04-09 16:13:29 +0200},
  date-modified = {2009-04-09 16:13:29 +0200},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@BOOK{Schnorr1971,
  title = {Zuf{\"a}lligkeit und {W}ahrscheinlichkeit},
  publisher = {Springer-Verlag, Berlin-Heidelberg-New York},
  year = {1971},
  author = {Claus Schnorr},
  volume = {218},
  series = {Lecture Notes in Mathematics},
  date-added = {2009-04-09 16:13:29 +0200},
  date-modified = {2009-04-09 16:13:29 +0200},
  owner = {Rupert},
  timestamp = {2010.04.20}
}

@ARTICLE{Sch71,
  author = {Schnorr, C.-P.},
  title = {A unified approach to the definition of random sequences},
  journal = {Math. Systems Theory},
  year = {1971},
  volume = {5},
  pages = {246--258},
  fjournal = {Mathematical Systems Theory. An International Journal on Mathematical
	Computing Theory},
  issn = {0025-5661},
  mrclass = {02E15 (60A05)},
  mrnumber = {MR0354328 (50 \#6808)},
  mrreviewer = {G. O. H. Katona},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Sch71,
  author = {Schnorr, C.-P.},
  title = {A unified approach to the definition of random sequences},
  journal = {Math. Systems Theory},
  year = {1971},
  volume = {5},
  pages = {246--258},
  fjournal = {Mathematical Systems Theory. An International Journal on Mathematical
	Computing Theory},
  issn = {0025-5661},
  mrclass = {02E15 (60A05)},
  mrnumber = {MR0354328 (50 \#6808)},
  mrreviewer = {G. O. H. Katona},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Seli88,
  author = {Selivanov, V. L.},
  title = {Ershov's hierarchy and {$\rm {T}$}-jumps},
  journal = {Algebra i Logika},
  year = {1988},
  volume = {27},
  pages = {464--478, 498--499},
  number = {4},
  fjournal = {Akademiya Nauk SSSR. Sibirskoe Otdelenie. Institut Matematiki. Algebra
	i Logika},
  issn = {0373-9252},
  mrclass = {03D20 (03D55)},
  mrnumber = {MR997746 (90d:03082)},
  mrreviewer = {Roman Murawski},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Seli88,
  author = {Selivanov, V. L.},
  title = {Ershov's hierarchy and {$\rm {T}$}-jumps},
  journal = {Algebra i Logika},
  year = {1988},
  volume = {27},
  pages = {464--478, 498--499},
  number = {4},
  fjournal = {Akademiya Nauk SSSR. Sibirskoe Otdelenie. Institut Matematiki. Algebra
	i Logika},
  issn = {0373-9252},
  mrclass = {03D20 (03D55)},
  mrnumber = {MR997746 (90d:03082)},
  mrreviewer = {Roman Murawski},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@INCOLLECTION{Shoen61,
  author = {Shoenfield, J. R.},
  title = {The problem of predicativity},
  booktitle = {Essays on the foundations of mathematics},
  publisher = {Magnes Press},
  year = {1961},
  pages = {132--139},
  address = {Hebrew Univ., Jerusalem},
  mrclass = {02.70},
  mrnumber = {MR0164886 (29 \#2177)},
  mrreviewer = {A. Mostowski},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@INCOLLECTION{Shoen61,
  author = {Shoenfield, J. R.},
  title = {The problem of predicativity},
  booktitle = {Essays on the foundations of mathematics},
  publisher = {Magnes Press},
  year = {1961},
  pages = {132--139},
  address = {Hebrew Univ., Jerusalem},
  mrclass = {02.70},
  mrnumber = {MR0164886 (29 \#2177)},
  mrreviewer = {A. Mostowski},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Silver80,
  author = {Silver, Jack H.},
  title = {Counting the number of equivalence classes of {B}orel and coanalytic
	equivalence relations},
  journal = {Ann. Math. Logic},
  year = {1980},
  volume = {18},
  pages = {1--28},
  number = {1},
  coden = {AMLOAD},
  fjournal = {Annals of Mathematical Logic},
  issn = {0003-4843},
  mrclass = {03E15},
  mrnumber = {MR568914 (81d:03051)},
  mrreviewer = {Keith Devlin},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Silver80,
  author = {Silver, Jack H.},
  title = {Counting the number of equivalence classes of {B}orel and coanalytic
	equivalence relations},
  journal = {Ann. Math. Logic},
  year = {1980},
  volume = {18},
  pages = {1--28},
  number = {1},
  coden = {AMLOAD},
  fjournal = {Annals of Mathematical Logic},
  issn = {0003-4843},
  mrclass = {03E15},
  mrnumber = {MR568914 (81d:03051)},
  mrreviewer = {Keith Devlin},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@TECHREPORT{simon,
  author = {Simon, Janos},
  title = {On Some Central Problems in Computational Complexity},
  year = {1975},
  address = {Ithaca, NY, USA},
  owner = {Rupert},
  publisher = {Cornell University},
  source = {http://www.ncstrl.org:8900/ncstrl/servlet/search?formname=detail\&id=oai%3Ancstrlh%3Acornellcs%3ACORNELLCS%3ATR75-224},
  timestamp = {2010.01.14}
}

@TECHREPORT{simon,
  author = {Simon, Janos},
  title = {On Some Central Problems in Computational Complexity},
  year = {1975},
  address = {Ithaca, NY, USA},
  owner = {Rupert},
  publisher = {Cornell University},
  source = {http://www.ncstrl.org:8900/ncstrl/servlet/search?formname=detail\&id=oai%3Ancstrlh%3Acornellcs%3ACORNELLCS%3ATR75-224},
  timestamp = {2010.01.14}
}

@ARTICLE{Simp75,
  author = {Simpson, Stephen G.},
  title = {Minimal covers and hyperdegrees},
  journal = {Trans. Amer. Math. Soc.},
  year = {1975},
  volume = {209},
  pages = {45--64},
  fjournal = {Transactions of the American Mathematical Society},
  issn = {0002-9947},
  mrclass = {02F30},
  mrnumber = {MR0392534 (52 \#13351)},
  mrreviewer = {C. G. Jockusch, Jr.},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Simp75,
  author = {Simpson, Stephen G.},
  title = {Minimal covers and hyperdegrees},
  journal = {Trans. Amer. Math. Soc.},
  year = {1975},
  volume = {209},
  pages = {45--64},
  fjournal = {Transactions of the American Mathematical Society},
  issn = {0002-9947},
  mrclass = {02F30},
  mrnumber = {MR0392534 (52 \#13351)},
  mrreviewer = {C. G. Jockusch, Jr.},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@INPROCEEDINGS{sipser,
  author = {Sipser, Michael},
  title = {A complexity theoretic approach to randomness},
  booktitle = {STOC '83: Proceedings of the fifteenth annual ACM symposium on Theory
	of computing},
  year = {1983},
  pages = {330--335},
  address = {New York, NY, USA},
  publisher = {ACM},
  bdsk-url-1 = {http://doi.acm.org/10.1145/800061.808762},
  doi = {http://doi.acm.org/10.1145/800061.808762},
  isbn = {0-89791-099-0},
  owner = {Rupert},
  timestamp = {2010.01.14}
}

@INPROCEEDINGS{sipser,
  author = {Sipser, Michael},
  title = {A complexity theoretic approach to randomness},
  booktitle = {STOC '83: Proceedings of the fifteenth annual ACM symposium on Theory
	of computing},
  year = {1983},
  pages = {330--335},
  address = {New York, NY, USA},
  publisher = {ACM},
  doi = {http://doi.acm.org/10.1145/800061.808762},
  isbn = {0-89791-099-0},
  owner = {Rupert},
  timestamp = {2010.01.14}
}

@INCOLLECTION{SS88,
  author = {Slaman, Theodore A. and Steel, John R.},
  title = {Definable functions on degrees},
  booktitle = {Cabal Seminar 81--85},
  publisher = {Springer},
  year = {1988},
  volume = {1333},
  series = {Lecture Notes in Math.},
  pages = {37--55},
  address = {Berlin},
  mrclass = {03D30 (03E60)},
  mrnumber = {MR960895 (89m:03033)},
  mrreviewer = {Peter G. Hinman},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@INCOLLECTION{SS88,
  author = {Slaman, Theodore A. and Steel, John R.},
  title = {Definable functions on degrees},
  booktitle = {Cabal Seminar 81--85},
  publisher = {Springer},
  year = {1988},
  volume = {1333},
  series = {Lecture Notes in Math.},
  pages = {37--55},
  address = {Berlin},
  mrclass = {03D30 (03E60)},
  mrnumber = {MR960895 (89m:03033)},
  mrreviewer = {Peter G. Hinman},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@BOOK{Soare87,
  title = {Recursively enumerable sets and degrees},
  publisher = {Springer-Verlag},
  year = {1987},
  author = {Soare, Robert I.},
  pages = {xviii+437},
  address = {Berlin},
  isbn = {3-540-15299-7},
  mrclass = {03-02 (03D20 03D25 03D30)},
  mrnumber = {88m:03003},
  mrreviewer = {Peter G. Hinman},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@BOOK{Soare87,
  title = {Recursively enumerable sets and degrees},
  publisher = {Springer-Verlag},
  year = {1987},
  author = {Soare, Robert I.},
  pages = {xviii+437},
  address = {Berlin},
  isbn = {3-540-15299-7},
  mrclass = {03-02 (03D20 03D25 03D30)},
  mrnumber = {88m:03003},
  mrreviewer = {Peter G. Hinman},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Sol64,
  author = {Solomonoff, R. J.},
  title = {A formal theory of inductive inference},
  journal = {Information and Control},
  year = {1964},
  volume = {7},
  pages = {1--22, 224--254},
  fjournal = {Information and Computation},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Sol64,
  author = {Solomonoff, R. J.},
  title = {A formal theory of inductive inference},
  journal = {Information and Control},
  year = {1964},
  volume = {7},
  pages = {1--22, 224--254},
  fjournal = {Information and Computation},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Sol78,
  author = {Solovay, Robert M.},
  title = {Hyperarithmetically encodable sets},
  journal = {Trans. Amer. Math. Soc.},
  year = {1978},
  volume = {239},
  pages = {99--122},
  fjournal = {Transactions of the American Mathematical Society},
  issn = {0002-9947},
  mrclass = {02F35 (02F27 02F30 02K99)},
  mrnumber = {MR0491103 (58 \#10375)},
  mrreviewer = {C. G. Jockusch, Jr.},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Sol78,
  author = {Solovay, Robert M.},
  title = {Hyperarithmetically encodable sets},
  journal = {Trans. Amer. Math. Soc.},
  year = {1978},
  volume = {239},
  pages = {99--122},
  fjournal = {Transactions of the American Mathematical Society},
  issn = {0002-9947},
  mrclass = {02F35 (02F27 02F30 02K99)},
  mrnumber = {MR0491103 (58 \#10375)},
  mrreviewer = {C. G. Jockusch, Jr.},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Sol75,
  author = {Solovay, Robert M.},
  title = {Draft of paper (or series of papers) on {C}haitin's work},
  year = {1975},
  note = {Unpublished notes},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{So70,
  author = {Solovay, Robert M.},
  title = {A model of set-theory in which every set of reals is {L}ebesgue measurable},
  journal = {Ann. of Math. (2)},
  year = {1970},
  volume = {92},
  pages = {1--56},
  fjournal = {Annals of Mathematics. Second Series},
  issn = {0003-486X},
  mrclass = {02.68},
  mrnumber = {MR0265151 (42 \#64)},
  mrreviewer = {A. L{\'e}vy},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{So70,
  author = {Solovay, Robert M.},
  title = {A model of set-theory in which every set of reals is {L}ebesgue measurable},
  journal = {Ann. of Math. (2)},
  year = {1970},
  volume = {92},
  pages = {1--56},
  fjournal = {Annals of Mathematics. Second Series},
  issn = {0003-486X},
  mrclass = {02.68},
  mrnumber = {MR0265151 (42 \#64)},
  mrreviewer = {A. L{\'e}vy},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@INCOLLECTION{So69,
  author = {Solovay, Robert M.},
  title = {On the cardinality of {$\Sigma \sb{2}\sp{1}$} sets of reals},
  booktitle = {Foundations of Mathematics (Symposium Commemorating Kurt G\"odel,
	Columbus, Ohio, 1966)},
  publisher = {Springer},
  year = {1969},
  pages = {58--73},
  address = {New York},
  mrclass = {02.68},
  mrnumber = {MR0277382 (43 \#3115)},
  mrreviewer = {Y. N. Moschovakis},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@INCOLLECTION{So69,
  author = {Solovay, Robert M.},
  title = {On the cardinality of {$\Sigma \sb{2}\sp{1}$} sets of reals},
  booktitle = {Foundations of Mathematics (Symposium Commemorating Kurt G\"odel,
	Columbus, Ohio, 1966)},
  publisher = {Springer},
  year = {1969},
  pages = {58--73},
  address = {New York},
  mrclass = {02.68},
  mrnumber = {MR0277382 (43 \#3115)},
  mrreviewer = {Y. N. Moschovakis},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Spector59,
  author = {Spector, C.},
  title = {Hyperarithmetical quantifiers},
  journal = {Fund. Math.},
  year = {1959/1960},
  volume = {48},
  pages = {313--320},
  fjournal = {Polska Akademia Nauk. Fundamenta Mathematicae},
  issn = {0016-2736},
  mrclass = {02.00},
  mrnumber = {MR0120147 (22 \#10904)},
  mrreviewer = {E. J. Cogan},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Spector59,
  author = {Spector, C.},
  title = {Hyperarithmetical quantifiers},
  journal = {Fund. Math.},
  year = {1959/1960},
  volume = {48},
  pages = {313--320},
  fjournal = {Polska Akademia Nauk. Fundamenta Mathematicae},
  issn = {0016-2736},
  mrclass = {02.00},
  mrnumber = {MR0120147 (22 \#10904)},
  mrreviewer = {E. J. Cogan},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Spector55,
  author = {Spector, Clifford},
  title = {Recursive well-orderings},
  journal = {J. Symb. Logic},
  year = {1955},
  volume = {20},
  pages = {151--163},
  fjournal = {The Journal of Symbolic Logic},
  issn = {0022-4812},
  mrclass = {02.0X},
  mrnumber = {MR0074347 (17,570b)},
  mrreviewer = {G. Kreisel},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Spector55,
  author = {Spector, Clifford},
  title = {Recursive well-orderings},
  journal = {J. Symb. Logic},
  year = {1955},
  volume = {20},
  pages = {151--163},
  fjournal = {The Journal of Symbolic Logic},
  issn = {0022-4812},
  mrclass = {02.0X},
  mrnumber = {MR0074347 (17,570b)},
  mrreviewer = {G. Kreisel},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Steel78,
  author = {Steel, John R.},
  title = {Forcing with tagged trees},
  journal = {Ann. Math. Logic},
  year = {1978},
  volume = {15},
  pages = {55--74},
  number = {1},
  coden = {AMLOAD},
  fjournal = {Annals of Mathematical Logic},
  issn = {0003-4843},
  mrclass = {03E40 (03D55 03D60)},
  mrnumber = {MR511943 (81c:03044)},
  mrreviewer = {Douglas Cenzer},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Steel78,
  author = {Steel, John R.},
  title = {Forcing with tagged trees},
  journal = {Ann. Math. Logic},
  year = {1978},
  volume = {15},
  pages = {55--74},
  number = {1},
  coden = {AMLOAD},
  fjournal = {Annals of Mathematical Logic},
  issn = {0003-4843},
  mrclass = {03E40 (03D55 03D60)},
  mrnumber = {MR511943 (81c:03044)},
  mrreviewer = {Douglas Cenzer},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Stephanemail,
  author = {Stephan, Frank},
  journal = {Email commnications},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Stephanemail,
  author = {Stephan, Frank},
  journal = {Email commnications},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@UNPUBLISHED{StephanPrivateComm,
  author = {Frank Stephan},
  title = {Private communication},
  year = {April 2010},
  owner = {Rupert},
  timestamp = {2010.05.04}
}

@ARTICLE{Suslin1917,
  author = {Suslin, M.},
  title = {Sur une definition des ensembles measurables B sans nombres transinis},
  journal = {Compts rendus Acad. Science},
  year = {1917},
  volume = {164},
  pages = {88--91},
  fjournal = {Compts rendus Acad. Science},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Suslin1917,
  author = {Suslin, M.},
  title = {Sur une definition des ensembles measurables B sans nombres transinis},
  journal = {Compts rendus Acad. Science},
  year = {1917},
  volume = {164},
  pages = {88--91},
  fjournal = {Compts rendus Acad. Science},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@INPROCEEDINGS{Ts,
  author = {Ta-Shma, Amnon},
  title = {On extracting randomness from weak random sources (extended abstract)},
  booktitle = {Proceedings of the {T}wenty-eighth {A}nnual {ACM} {S}ymposium on
	the {T}heory of {C}omputing ({P}hiladelphia, {PA}, 1996)},
  year = {1996},
  pages = {276--285},
  address = {New York},
  publisher = {ACM},
  doi = {10.1145/237814.237877},
  mrclass = {68Q20 (68Q10)},
  mrnumber = {MR1427523},
  owner = {Rupert},
  timestamp = {2010.03.05},
  url = {http://dx.doi.org/10.1145/237814.237877}
}

@ARTICLE{Tanaka68,
  author = {Tanaka, Hisao},
  title = {A basis result for {$\Pi \sb{1}{}\sp{1}$}-sets of postive measure},
  journal = {Comment. Math. Univ. St. Paul.},
  year = {1967/1968},
  volume = {16},
  pages = {115--127},
  fjournal = {Commentarii Mathematici Universitatis Sancti Pauli},
  issn = {0010-258X},
  mrclass = {02.77 (04.00)},
  mrnumber = {MR0236017 (38 \#4315)},
  mrreviewer = {G. Kreisel},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Tanaka68,
  author = {Tanaka, Hisao},
  title = {A basis result for {$\Pi \sb{1}{}\sp{1}$}-sets of postive measure},
  journal = {Comment. Math. Univ. St. Paul.},
  year = {1967/1968},
  volume = {16},
  pages = {115--127},
  fjournal = {Commentarii Mathematici Universitatis Sancti Pauli},
  issn = {0010-258X},
  mrclass = {02.77 (04.00)},
  mrnumber = {MR0236017 (38 \#4315)},
  mrreviewer = {G. Kreisel},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{TZ,
  author = {Terwijn, Sebastiaan A. and Zambella, Domenico},
  title = {Computational Randomness and Lowness},
  journal = {The Journal of Symbolic Logic},
  year = {2001},
  volume = {66},
  pages = {1199--1205},
  number = {3},
  abstract = {We prove that there are uncountably many sets that are low for the
	class of Schnorr random reals. We give a purely recursion theoretic
	characterization of these sets and show that they all have Turing
	degree incomparable to 0'. This contrasts with a result of Ku{\v
	c}era and Terwijn [5] on sets that are low for the class of Martin-L{\"o}f
	random reals.},
  bdsk-url-1 = {http://www.jstor.org/stable/2695101},
  copyright = {Copyright {\copyright} 2001 Association for Symbolic Logic},
  issn = {00224812},
  jstor_articletype = {primary_article},
  jstor_formatteddate = {Sep., 2001},
  owner = {Rupert},
  publisher = {Association for Symbolic Logic},
  timestamp = {2010.01.14},
  url = {http://www.jstor.org/stable/2695101}
}

@ARTICLE{TZ,
  author = {Terwijn, Sebastiaan A. and Zambella, Domenico},
  title = {Computational Randomness and Lowness},
  journal = {The Journal of Symbolic Logic},
  year = {2001},
  volume = {66},
  pages = {1199--1205},
  number = {3},
  abstract = {We prove that there are uncountably many sets that are low for the
	class of Schnorr random reals. We give a purely recursion theoretic
	characterization of these sets and show that they all have Turing
	degree incomparable to 0'. This contrasts with a result of Ku{\v
	c}era and Terwijn [5] on sets that are low for the class of Martin-L{\"o}f
	random reals.},
  bdsk-url-1 = {http://www.jstor.org/stable/2695101},
  copyright = {Copyright {\copyright} 2001 Association for Symbolic Logic},
  issn = {00224812},
  jstor_articletype = {primary_article},
  jstor_formatteddate = {Sep., 2001},
  owner = {Rupert},
  publisher = {Association for Symbolic Logic},
  timestamp = {2010.01.14},
  url = {http://www.jstor.org/stable/2695101}
}

@PHDTHESIS{Wang1996,
  author = {Yongge Wang},
  title = {Randomness and Complexity},
  school = {University of Heidelberg},
  year = {1996},
  type = {Ph{D} dissertation},
  date-added = {2009-04-09 16:13:40 +0200},
  date-modified = {2009-04-09 16:13:40 +0200},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@PHDTHESIS{Wang1996,
  author = {Yongge Wang},
  title = {Randomness and Complexity},
  school = {University of Heidelberg},
  year = {1996},
  type = {Ph{D} dissertation},
  date-added = {2009-04-09 16:13:40 +0200},
  date-modified = {2009-04-09 16:13:40 +0200},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@PHDTHESIS{Wang1996,
  author = {Yongge Wang},
  title = {Randomness and Complexity},
  school = {University of Heidelberg},
  year = {1996},
  type = {Ph{D} dissertation},
  date-added = {2009-04-09 16:13:40 +0200},
  date-modified = {2009-04-09 16:13:40 +0200},
  owner = {Rupert},
  timestamp = {2010.04.20}
}

@PHDTHESIS{Wang1996,
  author = {Yongge Wang},
  title = {Randomness and Complexity},
  school = {University of Heidelberg},
  year = {1996},
  type = {Ph{D} dissertation},
  date-added = {2009-04-09 16:13:40 +0200},
  date-modified = {2009-04-09 16:13:40 +0200}
}

@PHDTHESIS{Wang1996,
  author = {Yongge Wang},
  title = {Randomness and Complexity},
  school = {University of Heidelberg},
  year = {1996},
  type = {Ph{D} dissertation},
  date-added = {2009-04-09 16:13:40 +0200},
  date-modified = {2009-04-09 16:13:40 +0200},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@PHDTHESIS{Wang1996,
  author = {Yongge Wang},
  title = {Randomness and Complexity},
  school = {University of Heidelberg},
  year = {1996},
  type = {Ph{D} dissertation},
  date-added = {2009-04-09 16:13:40 +0200},
  date-modified = {2009-04-09 16:13:40 +0200},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Yu06,
  author = {Yu, Liang},
  title = {Measure theory aspects of locally countable orderings},
  journal = {J. Symbolic Logic},
  year = {2006},
  volume = {71},
  pages = {958--968},
  number = {3},
  coden = {JSYLA6},
  fjournal = {The Journal of Symbolic Logic},
  issn = {0022-4812},
  mrclass = {03D30 (03D28 03E15 03E35 28A20 68Q30)},
  mrnumber = {MR2251548},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{Yu06,
  author = {Yu, Liang},
  title = {Measure theory aspects of locally countable orderings},
  journal = {J. Symbolic Logic},
  year = {2006},
  volume = {71},
  pages = {958--968},
  number = {3},
  coden = {JSYLA6},
  fjournal = {The Journal of Symbolic Logic},
  issn = {0022-4812},
  mrclass = {03D30 (03D28 03E15 03E35 28A20 68Q30)},
  mrnumber = {MR2251548},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{YD04,
  author = {Yu, Liang and Ding, Decheng},
  title = {There are {$2\sp {\aleph\sb 0}$} many {$H$}-degrees in the random
	reals},
  journal = {Proc. Amer. Math. Soc.},
  year = {2004},
  volume = {132},
  pages = {2461--2464 (electronic)},
  number = {8},
  coden = {PAMYAR},
  fjournal = {Proceedings of the American Mathematical Society},
  issn = {0002-9939},
  mrclass = {68Q30 (03F60)},
  mrnumber = {MR2052426 (2004m:68109)},
  mrreviewer = {Steffen Lempp},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{YD04,
  author = {Yu, Liang and Ding, Decheng},
  title = {There are {$2\sp {\aleph\sb 0}$} many {$H$}-degrees in the random
	reals},
  journal = {Proc. Amer. Math. Soc.},
  year = {2004},
  volume = {132},
  pages = {2461--2464 (electronic)},
  number = {8},
  coden = {PAMYAR},
  fjournal = {Proceedings of the American Mathematical Society},
  issn = {0002-9939},
  mrclass = {68Q30 (03F60)},
  mrnumber = {MR2052426 (2004m:68109)},
  mrreviewer = {Steffen Lempp},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{YDD04,
  author = {Yu, Liang and Ding, Decheng and Downey, Rodney},
  title = {The {K}olmogorov complexity of random reals},
  journal = {Ann. Pure Appl. Logic},
  year = {2004},
  volume = {129},
  pages = {163--180},
  number = {1-3},
  coden = {APALD7},
  fjournal = {Annals of Pure and Applied Logic},
  issn = {0168-0072},
  mrclass = {68Q30 (03D80)},
  mrnumber = {MR2078364 (2005e:68109)},
  mrreviewer = {A. Ku{\v{c}}era},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{YDD04,
  author = {Yu, Liang and Ding, Decheng and Downey, Rodney},
  title = {The {K}olmogorov complexity of random reals},
  journal = {Ann. Pure Appl. Logic},
  year = {2004},
  volume = {129},
  pages = {163--180},
  number = {1-3},
  coden = {APALD7},
  fjournal = {Annals of Pure and Applied Logic},
  issn = {0168-0072},
  mrclass = {68Q30 (03D80)},
  mrnumber = {MR2078364 (2005e:68109)},
  mrreviewer = {A. Ku{\v{c}}era},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{ZvLev70,
  author = {Zvonkin, A. K. and Levin, L. A.},
  title = {The complexity of finite objects and the development of the concepts
	of information and randomness by means of the theory of algorithms},
  journal = {Russian Math. Surveys},
  year = {1970},
  volume = {25},
  pages = {83--124},
  number = {6},
  fjournal = {Russian Mathematical Surveys},
  owner = {Rupert},
  timestamp = {2009.12.17}
}

@ARTICLE{ZvLev70,
  author = {Zvonkin, A. K. and Levin, L. A.},
  title = {The complexity of finite objects and the development of the concepts
	of information and randomness by means of the theory of algorithms},
  journal = {Russian Math. Surveys},
  year = {1970},
  volume = {25},
  pages = {83--124},
  number = {6},
  fjournal = {Russian Mathematical Surveys},
  owner = {Rupert},
  timestamp = {2009.12.17}
}