Algorithmic Randomness and Complexity
Intuitively, a sequence such as 101010101010101010… does not seem random, whereas 101101011101010100…, obtained using coin tosses, does. How can we reconcile this intuition with the fact that both are statistically equally likely? What does it mean to say
- PDF / 8,655,327 Bytes
- 882 Pages / 439.37 x 666.142 pts Page_size
- 25 Downloads / 204 Views
Series Editors Prof. P. Bonizzoni Università Degli Studi di Milano-Bicocca Dipartimento di Informatica Sistemistica e Comunicazione (DISCo) 20126 Milan Italy [email protected] Prof. V. Brattka University of Cape Town Department of Mathematics and Applied Mathematics Rondebosch 7701 South Africa [email protected] Prof. S.B. Cooper University of Leeds Department of Pure Mathematics Leeds LS2 9JT UK [email protected] Prof. E. Mayordomo Universidad de Zaragoza Departamento de Informática e Ingeniería de Sistemas E-50018 Zaragoza Spain [email protected]
For further volumes, go to www.springer.com/series/8819
Books published in this series will be of interest to the research community and graduate students, with a unique focus on issues of computability. The perspective of the series is multidisciplinary, recapturing the spirit of Turing by linking theoretical and real-world concerns from computer science, mathematics, biology, physics, and the philosophy of science. The series includes research monographs, advanced and graduate texts, and books that offer an original and informative view of computability and computational paradigms. Series Advisory Board Samson Abramsky, University of Oxford Eric Allender, Rutgers, The State University of New Jersey Klaus Ambos-Spies, Universität Heidelberg Giorgio Ausiello, Università di Roma, “La Sapienza” Jeremy Avigad, Carnegie Mellon University Samuel R. Buss, University of California, San Diego Rodney G. Downey, Victoria University of Wellington Sergei S. Goncharov, Novosibirsk State University Peter Jeavons, University of Oxford Nataša Jonoska, University of South Florida, Tampa Ulrich Kohlenbach, Technische Universität Darmstadt Ming Li, University of Waterloo Wolfgang Maass, Technische Universität Graz Prakash Panangaden, McGill University Grzegorz Rozenberg, Leiden University and University of Colorado, Boulder Alan Selman, University at Buffalo, The State University of New York Wilfried Sieg, Carnegie Mellon University Jan van Leeuwen, Universiteit Utrecht Klaus Weihrauch, FernUniversität Hagen Philip Welch, University of Bristol
E
Rodney G. Downey • Denis R. Hirschfeldt
Algorithmic Randomness E Complexity and V
Rodney G. Downey Victoria University of Wellington School of Mathematics, Statistics and Operations Research Wellington, New Zealand [email protected]
Denis R. Hirschfeldt University of Chicago Department of Mathematics Chicago, IL 60637 USA [email protected]
e-ISSN 2190-6203 ISSN 2190-619X ISBN 978-0-387-95567-4 e-ISBN 978-0-387-68441-3 DOI 10.1007/978-0-387-68441-3 Springer New York Dordrecht Heidelberg London Mathematics Subject Classification (2010): Primary: 03D32, Secondary: 03D25, 03D27, 03D30, 03D80, 68Q30 ACM Computing Classification (1998): F.1, F.2, F.4, G.3, H.1 © Springer Science+Business Media, LLC 2010 All rights reserved. This work may not be translated or copied in whole or in part without the written permission of the publisher (Springer Science+Business Media, LLC, 233 Spring Street, New York, NY 10013, USA),
Data Loading...
