Coverart for item
The Resource Algorithmic randomness and complexity, Rod Downey, Denis Hirschfeldt

Algorithmic randomness and complexity, Rod Downey, Denis Hirschfeldt

Label
Algorithmic randomness and complexity
Title
Algorithmic randomness and complexity
Statement of responsibility
Rod Downey, Denis Hirschfeldt
Creator
Contributor
Subject
Language
eng
Summary
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 that an individual mathematical object such as a real number is random, or to say that one real is more random than another? And what is the relationship between randomness and computational power. The theory of algorithmic randomness uses tools from computability theory and algorithmic information theory to address questions such as these. Much of this theory can be seen as exploring the relationships between three fundamental concepts: relative computability, as measured by notions such as Turing reducibility; information content, as measured by notions such as Kolmogorov complexity; and randomness of individual objects, as first successfully defined by Martin-Löf. Although algorithmic randomness has been studied for several decades, a dramatic upsurge of interest in the area, starting in the late 1990s, has led to significant advances. This is the first comprehensive treatment of this important field, designed to be both a reference tool for experts and a guide for newcomers. It surveys a broad section of work in the area, and presents most of its major results and techniques in depth. Its organization is designed to guide the reader through this large body of work, providing context for its many concepts and theorems, discussing their significance, and highlighting their interactions. It includes a discussion of effective dimension, which allows us to assign concepts like Hausdorff dimension to individual reals, and a focused but detailed introduction to computability theory. It will be of interest to researchers and students in computability theory, algorithmic information theory, and theoretical computer science
Cataloging source
GW5XE
http://library.link/vocab/creatorName
Downey, R. G.
Dewey number
511.3
Illustrations
illustrations
Index
index present
LC call number
QA267.7
LC item number
.D69 2008
Literary form
non fiction
Nature of contents
  • dictionaries
  • bibliography
http://library.link/vocab/relatedWorkOrContributorName
Hirschfeldt, Denis Roman
http://library.link/vocab/subjectName
  • Computational complexity
  • Computable functions
  • Computational complexity
  • Computable functions
  • Computable functions
  • Computational complexity
Label
Algorithmic randomness and complexity, Rod Downey, Denis Hirschfeldt
Instantiates
Publication
Bibliography note
Includes bibliographical references (pages 767-795) and index
Carrier category
online resource
Carrier category code
  • cr
Carrier MARC source
rdacarrier
Color
multicolored
Content category
text
Content type code
  • txt
Content type MARC source
rdacontent
Contents
Background -- Preliminaries -- Computability Theory -- Kolmogorov Complexity of Finite Strings -- Relating Complexities -- Effective Reals -- Notions of Randomness -- Martin-Löf Randomness -- Other Notions of Algorithmic Randomness -- Algorithmic Randomness and Turing Reducibility -- Relative Randomness -- Measures of Relative Randomness -- Complexity and Relative Randomness for 1-Random Sets -- Randomness-Theoretic Weakness -- Lowness and Triviality for Other Randomness Notions -- Algorithmic Dimension -- Further Topics -- Strong Jump Traceability -- ? as an Operator -- Complexity of Computably Enumerable Sets
Control code
681900553
Dimensions
unknown
Extent
1 online resource (xxviii, 855 pages)
Form of item
online
Isbn
9780387684413
Media category
computer
Media MARC source
rdamedia
Media type code
  • c
Other physical details
illustrations
http://library.link/vocab/ext/overdrive/overdriveId
978-0-387-95567-4
Specific material designation
remote
System control number
(OCoLC)681900553
Label
Algorithmic randomness and complexity, Rod Downey, Denis Hirschfeldt
Publication
Bibliography note
Includes bibliographical references (pages 767-795) and index
Carrier category
online resource
Carrier category code
  • cr
Carrier MARC source
rdacarrier
Color
multicolored
Content category
text
Content type code
  • txt
Content type MARC source
rdacontent
Contents
Background -- Preliminaries -- Computability Theory -- Kolmogorov Complexity of Finite Strings -- Relating Complexities -- Effective Reals -- Notions of Randomness -- Martin-Löf Randomness -- Other Notions of Algorithmic Randomness -- Algorithmic Randomness and Turing Reducibility -- Relative Randomness -- Measures of Relative Randomness -- Complexity and Relative Randomness for 1-Random Sets -- Randomness-Theoretic Weakness -- Lowness and Triviality for Other Randomness Notions -- Algorithmic Dimension -- Further Topics -- Strong Jump Traceability -- ? as an Operator -- Complexity of Computably Enumerable Sets
Control code
681900553
Dimensions
unknown
Extent
1 online resource (xxviii, 855 pages)
Form of item
online
Isbn
9780387684413
Media category
computer
Media MARC source
rdamedia
Media type code
  • c
Other physical details
illustrations
http://library.link/vocab/ext/overdrive/overdriveId
978-0-387-95567-4
Specific material designation
remote
System control number
(OCoLC)681900553

Library Locations

    • Ellis LibraryBorrow it
      1020 Lowry Street, Columbia, MO, 65201, US
      38.944491 -92.326012
Processing Feedback ...