nalino
Full Member level 3
Algorithmic Randomness and Complexity
by Rod Downey and Denis Hirschfeldt
(to be published by Springer Verlag,18 June 2005 draft,478 pages so far)
In this book,the authors try to organize the material on algorithmic randomness
and computability theory into a coherent whole.
How random is a real? Given two reals, which is more random? How should we
even try to quantify these questions, and how do various choices of measurement
relate? Once we have a reasonable measuring device, and divide the reals into
equivalence classes of the same “degree of randomness” what do the resulting
structures look like? Once we measure the level of randomness how does the
level of randomness relate to classical measures of complexity Turing degrees of
unsolvability? Should it be the case that high levels of randomness mean high
levels of complexity in terms of computational power, or low levels of complexity?
Conversely should the structures of computability such as the degrees and
the computably enumerable sets have anything to say about randomness for
reals?
These were the kinds of questions motivating the research which is represented
in this book. While some fundamental questions remain open, nevertheless
we now have a reasonable insight into many of these questions, and
the resulting body of work is both beautiful and has a number of rather deep
theorems.
**broken link removed**
by Rod Downey and Denis Hirschfeldt
(to be published by Springer Verlag,18 June 2005 draft,478 pages so far)
In this book,the authors try to organize the material on algorithmic randomness
and computability theory into a coherent whole.
How random is a real? Given two reals, which is more random? How should we
even try to quantify these questions, and how do various choices of measurement
relate? Once we have a reasonable measuring device, and divide the reals into
equivalence classes of the same “degree of randomness” what do the resulting
structures look like? Once we measure the level of randomness how does the
level of randomness relate to classical measures of complexity Turing degrees of
unsolvability? Should it be the case that high levels of randomness mean high
levels of complexity in terms of computational power, or low levels of complexity?
Conversely should the structures of computability such as the degrees and
the computably enumerable sets have anything to say about randomness for
reals?
These were the kinds of questions motivating the research which is represented
in this book. While some fundamental questions remain open, nevertheless
we now have a reasonable insight into many of these questions, and
the resulting body of work is both beautiful and has a number of rather deep
theorems.
**broken link removed**