Algorithmic Randomness and Complexity

AvRodney G. Downey,Denis R. Hirschfeldt

Häftad, Engelska, 2016

Del i serien Theory and Applications of Computability

1 218 kr

Beställningsvara. Skickas inom 10-15 vardagar. Fri frakt över 249 kr.

Fler format och utgåvor

Inbunden

1 659 kr

Beskrivning

The theory of algorithmic randomness uses tools from computability theory and algorithmic information theory to address questions such as these. It will be of interest to researchers and students in computability theory, algorithmic information theory, and theoretical computer science.

Produktinformation

Utgivningsdatum:2016-08-23
Mått:155 x 235 x 48 mm
Vikt:1 311 g
Format:Häftad
Språk:Engelska
Serie:Theory and Applications of Computability
Antal sidor:855
Förlag:Springer-Verlag New York Inc.
ISBN:9781493938209

Utforska kategorier

Systemvetenskap och AI inom Data och IT
Programmeringsböcker inom Data och IT

Recensioner i media

From the reviews:“Develops the prerequisites to algorithmic randomness: computability theory and Kolmogorov complexity. … Studying these … one should be able to proceed in the area with confidence. A draft of the book under review has been circulating for years and the reviewer found it to be the best source when attempting to conduct research in the area … . It is advantageous for the future of the area of algorithmic randomness that these two books were published at the cusp of a period of great activity.” (Bjørn Kjos-Hanssen, Mathematical Reviews, Issue 2012 g)“A thorough and systematic study of algorithmic randomness, this long-awaited work is an irreplaceable source of well-presented classic and new results for advanced undergraduate and graduate students, as well as researchers in the field and related areas. The book joins a select number of books in this category.” (Hector Zenil, ACM Computing Reviews, October, 2011)

Innehållsförteckning

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.