Algorithmic Randomness and Complexity
Springer Science & Business Media, Oct 29, 2010 - Computers - 855 pages
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.
What people are saying - Write a review
We haven't found any reviews in the usual places.
Other editions - View all
1-generic 1-random set A-computable algorithmic randomness approximation assume bound c.e. degree c.e. set characterization coding computable martingale computable measure machine computable order computable sequence computably enumerable computably random construction Corollary define definition Downey effective Hausdorff dimension elements ensure extension fact finite following result function f given Greenberg Hausdorff dimension hence Hirschfeldt implies infinitely initial segment Jockusch jump traceable KC set Kolmogorov complexity Kurtz least left-c.e. reals Lemma Let G low basis theorem Martin-Löf test Merkle minimal minimal pair Nies node noncomputable nonempty Note notion O(log oracle machine packing dimension partial computable function prefix-free machine proof of Theorem Proposition prove recursion theorem reducibility relative relativized requirements satisfied Schnorr random Schnorr trivial Section semimeasure set of strings Solovay stage Stephan strategy strings of length superlow supermartingale Suppose Terwijn Turing degrees Turing reducibility