Algorithmic Randomness and Complexity

Inbunden, Engelska, 2010

AvRodney G. Downey,Denis R. Hirschfeldt,Rodney G Downey,Denis R Hirschfeldt

1 949 kr

Beställningsvara. Skickas inom 10-15 vardagar. Fri frakt för medlemmar vid köp för minst 249 kr.

Finns i fler format (1)

Häftad

1 409 kr

Skickas inom 10-15 vardagar

This book is concerned with the theory of computability and complexity over the real numbers. This theory was initiated by Turing, Grzegorczyk, Lacombe, Banach, and Mazur and has seen rapid growth in recent years. Computability and complexity theory are two central areas of research in theoretical computer science. Until recently, most work in these areas concentrated on problems over discrete structures, but there has been enormous growth of computability theory and complexity theory over the real numbers and other continuous structures, especially incorporating concepts of "randomness". One reason for this growth is that more and more computation problems over the real numbers are being dealt with by computer scientists - in computational geometry and in the modeling of dynamical and hybrid systems. Scientists working on these questions come from such diverse fields as theoretical computer science, domain theory, logic, constructive mathematics, computer arithmetic, numerical mathematics, and analysis. An essential resource for all researchers in theoretical computer science, logic, computability theory and complexity.

Produktinformation

Utgivningsdatum2010-11-05
Mått155 x 235 x 58 mm
Vikt1 350 g
FormatInbunden
SpråkEngelska
SerieTheory and Applications of Computability
Antal sidor855
FörlagSpringer-Verlag New York Inc.
ISBN9780387955674

Tillhör följande kategorier

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

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.

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." (Bjorn 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)

Mer från samma författare

Parameterized Complexity

Rodney G. Downey, M.R. Fellows, M. R. Fellows

Inbunden

3 369 kr

Fundamentals of Parameterized Complexity

Rodney G. Downey, Michael R. Fellows

Inbunden

1 779 kr

Fundamentals of Parameterized Complexity

Rodney G. Downey, Michael R. Fellows

Häftad

1 229 kr

Parameterized Complexity

Rodney G. Downey, M.R. Fellows, M. R. Fellows

Häftad

3 369 kr

Computable Structure Theory

Rodney G. Downey, Alexander Melnikov

Inbunden

1 779 kr

Mathematical Logic In Asia - Proceedings Of The 9th Asian Logic Conference

DOWNEY R, Sergey S Goncharov, Hiroakira Ono, Rodney G Downey, Russia) Goncharov, Sergei S (Russian Academy Of Sci, Japan) Ono, Hiroakira (Japan Advanced Inst Of Sci & Tech, New Zealand) Downey, Rodney G (Victoria Univ Of Wellington, Sergey S. Goncharov

Inbunden

2 679 kr

Proceedings Of The 12th Asian Logic Conference

Downey Rod, DOWNEY ROD, Rodney G Downey, Jorg Brendle, Robert Goldblatt, Byunghan Kim, New Zealand) Downey, Rodney G (Victoria Univ Of Wellington, Japan) Brendle, Jorg (Kobe University, New Zealand) Goldblatt, Robert (Victoria Univ Of Wellington, South Korea) Kim, Byunghan (Yonsei Univ

Inbunden

2 259 kr