Algorithmic randomness and complexity

著者

• Downey, R. G. (Rod G.)
• Hirschfeldt, Denis R.

書誌事項

Algorithmic randomness and complexity

Rodney G. Downey, Denis R. Hirschfeldt

（Theory and applications of computability）

Springer Science+Business Media, c2010

• : pbk

注記

Includes bibliographical references (p. 767-795) and index

内容説明・目次

内容説明

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.

目次

Preface.- Acknowledgments.- Introduction.- I. Background.- Preliminaries.- Computability Theory.- Kolmogorov Complexity of Finite Strings.- Relating Plain and Prefix-Free Complexity.- Effective Reals.- II. Randomness of Sets.- Martin-Loef Randomness.- Other Notions of Effective Randomness.- Algorithmic Randomness and Turing Reducibility.- III. Relative Randomness.- Measures of Relative Randomness.- The Quantity of K- and Other Degrees.- Randomness-Theoretic Weakness.- Lowness for Other Randomness Notions.- Effective Hausdorff Dimension.- IV. Further Topics.- Omega as an Operator.- Complexity of C.E. Sets.- References.- Index.

「Nielsen BookData」 より

• NII書誌ID(NCID): BB04091348
• ISBN:
  • 9780387955674
  • 9781493938209
• 出版国コード: us
• タイトル言語コード: eng
• 本文言語コード: eng
• 出版地: New York
• ページ数/冊数: xxviii, 855 p.
• 大きさ: 25 cm
• 分類:
  • LCC : QA267.7
  • DC22 : 511.3
  • DC23 : 518.1
• 件名:
  • LCSH : Computational complexity
  • LCSH : Computable functions
• 親書誌ID:
  • BB04091064