Algorithmic Randomness and Complexity

Softcover Nachdruck of the original 1. Auflage 2010
ISBN: 978-1-4939-3820-9
Verlag: Springer

Buch, Englisch, 855 Seiten, Previously published in hardcover, Format (B × H): 155 mm x 235 mm, Gewicht: 1311 g

Reihe: Theory and Applications of Computability

Computability and complexity theory are two central areas of research in theoretical computer science. This book provides a systematic, technical development of "algorithmic randomness" and complexity for scientists from diverse fields.

Zielgruppe

Graduate

Autoren/Hrsg.

Downey, Rodney G.

Hirschfeldt, Denis R.

Fachgebiete

• Mathematik | Informatik EDV | Informatik Informatik Logik, formale Sprachen, Automaten
• Mathematik | Informatik EDV | Informatik Informatik Theoretische Informatik
• Mathematik | Informatik EDV | Informatik Programmierung | Softwareentwicklung Algorithmen & Datenstrukturen

Inhaltsverzeichnis

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.