Downey R.G. Algorithmic randomness and complexity (New York, 2010). - ОГЛАВЛЕНИЕ / CONTENTS
Навигация

Архив выставки новых поступлений | Отечественные поступления | Иностранные поступления | Сиглы
ОбложкаDowney R.G. Algorithmic randomness and complexity / R.G.Downey, D.R.Hirschfeldt. - New York: Springer, 2010. - xxviii, 855 p. - (Theory and applications of computability). - Ref.: p.767-795. - Ind.: p.797-855. - ISBN 978-0-387-68441-3; ISSN 2190-619X
 

Место хранения: 013 | Институт математики СО РАН | Новосибирск | Библиотека

Оглавление / Contents
 
Preface ........................................................ xi
Acknowledgments ............................................... xiv
Introduction ................................................. xvii

I  Background ................................................... 1

1  Preliminaries ................................................ 2
   1.1  Notation and conventions ................................ 2
   1.2  Basics from measure theory .............................. 4
2  Computability Theory ......................................... 7
   2.1  Computable functions, coding, and the halting problem ... 7
   2.2  Computable enumerability and Rice's Theorem ............ 11
   2.3  The Recursion Theorem .................................. 13
   2.4  Reductions ............................................. 15
        2.4.1  Oracle machines and Turing reducibility ......... 16
        2.4.2  The jump operator and jump classes .............. 18
        2.4.3  Strong reducibilities ........................... 19
        2.4.4  Myhill's Theorem ................................ 21
   2.5  The arithmetic hierarchy ............................... 23
   2.6  The Limit Lemma and Post's Theorem ..................... 24
   2.5  The difference hierarchy ............................... 27
   2.8  Primitive recursive functions .......................... 28
   2.9  A note on reductions ................................... 29
   2.10 The finite extension method ............................ 31
   2.11 Post's Problem and the finite injury priority method ... 34
   2.12 Finite injury arguments of unbounded type .............. 39
        2.12.1 The Sacks Splitting Theorem ..................... 39
        2.12.2 The Pseudo-Jump Theorem ......................... 41
   2.13 Coding and permitting .................................. 42
   2.14 The infinite injury priority method .................... 44
        2.14.1 Priority trees and guessing ..................... 44
        2.14.2 The minimal pair method ......................... 47
        2.14.3 High computably enumerable degrees .............. 53
        2.14.4 The Thickness Lemma ............................. 56
   2.15 The Density Theorem .................................... 58
   2.16 Jump theorems .......................................... 64
   2.17 Hyperimmune-free degrees ............................... 67
   2.18 Minimal degrees ........................................ 70
   2.19 П01 and ∑01 classes .................................... 72
        2.19.1 Basics .......................................... 72
        2.19.2 П0n and ∑0n classes ............................. 75
        2.19.3 Basis theorems .................................. 77
        2.19.4 Generalizing the low basis theorem .............. 81
   2.20 Strong reducibilities and Post's Program ............... 82
   2.21 PA degrees ............................................. 84
   2.22 Fixed-point free and diagonally noncomputable
        functions .............................................. 87
   2.23 Array noncomputability and traceability ................ 93
   2.24 Genericity and weak genericity ........................ 100
3  Kolmogorov Complexity of Finite Strings .................... 110
   3.1  Plain Kolmogorov complexity ........................... 110
   3.2  Conditional complexity ................................ 114
   3.3  Symmetry of information ............................... 116
   3.4  Information-theoretic characterizations of
        computability ......................................... 117
   3.5  Prefix-free machines and complexity ................... 121
   3.6  The КС Theorem ........................................ 125
   3.7  Basic properties of prefix-free complexity ............ 128
   3.8  Prefix-free randomness of strings ..................... 132
   3.9  The Coding Theorem and discrete semimeasures .......... 133
   3.10 Prefix-free symmetry of information ................... 134
   3.11 Initial segment complexity of sets .................... 136
   3.12 Computable bounds for prefix-free complexity .......... 137
   3.13 Universal machines and halting probabilities .......... 139
   3.14 The conditional complexity of σ* given σ ............. 143
   3.15 Monotone and process complexity ....................... 145
   3.16 Continuous semimeasures and KM-complexity ............. 150
4  Relating Complexities ...................................... 154
   4.1  Levin's Theorem relating С and К ...................... 154
   4.2  Solovay's Theorems relating С and К ................... 155
   4.3  Strong fC-randomness and C-randomness ................. 161
        4.3.1  Positive results ............................... 161
        4.3.2  Counterexamples ................................ 162
   4.4  Muchnik's Theorem on С and К .......................... 168
   4.5  Monotone complexity and KM-complexity ................. 169
5  Effective Reals ............................................ 197
   5.1  Computable and left-c.e. reals ........................ 197
   5.2  Real-valued functions ................................. 202
   5.3  Representing left-c.e. reals .......................... 203
        5.3.1  Degrees of representations ..................... 203
        5.3.2  Presentations of left-c.e. reals ............... 206
        5.3.3  Presentations and ideals ....................... 208
        5.3.4  Promptly simple sets and presentations ......... 215
   5.4  Left-d.c.e. reals ..................................... 217
        5.4.1  Basics ......................................... 217
        5.4.2  The field of left-d.c.e. reals ................. 219

II   Notions of Randomness .................................... 225

6  Martin-Löf Randomness ...................................... 226
   6.1  The computational paradigm ............................ 227
   6.2  The measure-theoretic paradigm ........................ 229
   6.3  The unpredictability paradigm ......................... 234
        6.3.1  Martingales and supermartingales ............... 234
        6.3.2  Supermartingales and continuous semimeasures ... 238
        6.3.3  Martingales and optimality ..................... 239
        6.3.4  Martingale processes ........................... 241
   6.4  Relativizing randomness ............................... 245
   6.5  Ville's Theorem ....................................... 246
   6.6  The Ample Excess Lemma ................................ 250
   6.7  Plain complexity and randomness ....................... 252
   6.8  n-randomness .......................................... 254
   6.9  Van Lambalgen's Theorem ............................... 257
   6.10 Effective 0-1 laws .................................... 259
   6.11 Infinitely often maximally complex sets ............... 260
   6.12 Randomness for other measures and degree-invariance ... 263
        6.12.1 Generalizing randomness to other measures ...... 263
        6.12.2 Computable measures and representing reals ..... 265
7  Other Notions of Algorithmic Randomness .................... 269
   7.1  Computable randomness and Schnorr randomness .......... 270
        7.1.1  Basics ......................................... 270
        7.1.2  Limitations .................................... 275
        7.1.3  Computable measure machines .................... 277
        7.1.4  Computable randomness and tests ................ 279
        7.1.5  Bounded machines and computable randomness ..... 281
        7.1.6  Process complexity and computable randomness ... 282
   7.2  Weak n-randomness ..................................... 285
        7.2.1  Basics ......................................... 285
        7.2.2  Characterizations of weak 1-randomness ......... 290
        7.2.3  Schnorr randomness via Kurtz null tests ........ 293
        7.2.4  Weakly 1-random left-c.e. reals ................ 295
        7.2.5  Solovay genericity and randomness .............. 296
   7.3  Decidable machines .................................... 298
   7.4  Selection revisited ................................... 301
        7.4.1  Stochasticity .................................. 301
        7.4.2  Partial computable martingales and
               stochasticity .................................. 303
        7.4.3  A martingale characterization of
               stochasticity .................................. 308
   7.5  Nonmonotonic randomness ............................... 309
        7.5.1  Nonmonotonic betting strategies ................ 309
        7.5.2  Van Lambalgen's Theorem revisited .............. 313
   7.6  Demuth randomness ..................................... 315
   7.7  Difference randomness ................................. 316
   7.8  Finite randomness ..................................... 318
   7.9  Infective and permutation randomness .................. 319
8  Algorithmic Randomness and Turing Reducibility ............. 323
   8.1  П01 classes of 1-random sets .......................... 324
   8.2  Computably enumerable degrees ......................... 324
   8.3  The Kucera-Gдcs Theorem ............................... 325
   8.4  A "no gap" theorem for 1-randomness ................... 327
   8.5  Kucera coding ......................................... 330
   8.6  Demuth's Theorem ...................................... 333
   8.7  Randomness relative to other measures ................. 334
   8.8  Randomness and PA degrees ............................. 336
   8.9  Mass problems ......................................... 344
   8.10 DNC degrees and subsets of random sets ................ 347
   8.11 High degrees and separating notions of randomness ..... 349
        8.11.1 High degrees and computable randomness ......... 349
        8.11.2 Separating notions of randomness ............... 350
        8.11.3 When van Lambalgen's Theorem fails ............. 357
   8.12 Measure theory and Turing reducibility ................ 358
   8.13 n-randomness and weak n-randomness .................... 360
   8.14 Every 2-random set is GL1 ............................. 363
   8.15 Stillwell's Theorem ................................... 364
   8.16 DNC degrees and autocomplexity ........................ 366
   8.17 Randomness and n-fixed-point freeness ................. 370
   8.18 Jump inversion ........................................ 373
   8.19 Pseudo-jump inversion ................................. 376
   8.20 Randomness and genericity ............................. 378
        8.20.1 Similarities between randomness and
               genericity ..................................... 378
        8.20.2 n-genericity versus n-randomness ............... 379
   8.21 Properties of almost all degrees ...................... 381
        8.21.1 Hyperimmunity .................................. 381
        8.21.2 Bounding 1-generics ............................ 383
        8.21.3 Every 2-random set is CEA ...................... 386
        8.21.4 Where 1-generic degrees are downward dense ..... 394

III  Relative Randomness ...................................... 403

9  Measures of Relative Randomness ............................ 404
   9.1  Solovay reducibility .................................. 405
   9.2  The Kucera-Slaman Theorem ............................. 408
   9.3  Presentations of left-c.e. reals and complexity ....... 411
   9.4  Solovay functions and 1-randomness .................... 412
   9.5  Solovay degrees of left-c.e. reals .................... 413
   9.6  cl-reducibility and rK-reducibility ................... 419
   9.7  K-reducibility and C-reducibility ..................... 425
   9.8  Density and splittings ................................ 427
   9.9  Monotone degrees and density .......................... 432
   9.10 Further relationships between reducibilities .......... 433
   9.11 A minimal rK-degree ................................... 437
   9.12 Complexity and completeness for left-c.e. reals ....... 439
   9.13 cl-reducibility and the Kucera-Gács Theorem ........... 441
   9.14 Further properties of cl-reducibility ................. 442
        9.14.1 cl-reducibility and joins ...................... 442
        9.14.2 Array noncomputability and joins ............... 444
        9.14.3 Left-c.e. reals cl-reducible to versions of
               Ω .............................................. 447
        9.14.4 cl-degrees of versions of Ω .................... 454
   9.15 K-degrees, C-degrees, and Turing degrees .............. 456
   9.16 The structure of the monotone degrees ................. 459
   9.17 Schnorr reducibility .................................. 462
10 Complexity and Relative Randomness for 1-Randoms Sets ...... 464
   10.1 Uncountable lower cones in and ≤ K and ≤ C ............ 464
   10.2 The K-complexity of Ω and other 1-random sets ......... 466
        10.2.1 К (A / n) versus K(n) for 1-random sets A ...... 466
        10.2.2 The rate of convergence of Ω and the
               α function ..................................... 467
        10.2.3 Comparing complexities of 1-random sets ........ 468
        10.2.4 Limit complexities and relativized
               complexities ................................... 471
   10.3 Van Lambalgen reducibility ............................ 473
        10.3.1 Basic properties of the van Lambalgen
               degrees ........................................ 474
        10.3.2 Relativized randomness and Turing
               reducibility ................................... 475
        10.3.3 vL-reducibility, K-reducibility, and joins ..... 476
        10.3.4 vL-reducibility and C-reducibility ............. 478
        10.3.5 Contrasting vL-reducibility and
               X-reducibility ................................. 479
   10.4 Upward oscillations and ≤K-comparable 1-random sets ... 481
   10.5 LR-reducibility ....................................... 489
   10.6 Almost everywhere domination .......................... 495
11 Randomness-Theoretic Weakness .............................. 500
   11.1 K-triviality .......................................... 500
        11.1.1 The basic K-triviality construction ............ 501
        11.1.2 The requirement-free version ................... 502
        11.1.3 Solovay functions and K-triviality ............. 504
        11.1.4 Counting the K-trivial sets .................... 505
   11.2 Lowness ............................................... 507
   11.3 Degrees of К-trivial sets ............................. 511
        11.3.1 A first approximation: wtt-incompleteness ...... 511
        11.3.2 A second approximation: impossible constants ... 512
        11.3.3 The less impossible case ....................... 514
   11.4 K-triviality and lowness .............................. 518
   11.5 Cost functions ........................................ 526
   11.6 The ideal of К-trivial degrees ........................ 529
   11.7 Bases for 1-randomness ................................ 531
   11.8 ML-covering, ML-cupping, and related notions .......... 534
   11.9 Lowness for weak 2-randomness ......................... 536
   11.10 Listing the K-trivial sets ........................... 538
   11.11 Upper bounds for the К-trivial sets .................. 541
   11.12 A gap phenomenon for K-triviality .................... 550
12 Lowness and Triviality for Other Randomness Notions ........ 554
   12.1 Schnorr lowness ....................................... 554
        12.1.1 Lowness for Schnorr tests ...................... 554
        12.1.2 Lowness for Schnorr randomness ................. 559
        12.1.3 Lowness for computable measure machines ........ 561
   12.2 Schnorr triviality .................................... 564
        12.2.1 Degrees of Schnorr trivial sets ................ 564
        12.2.2 Schnorr triviality and strong reducibilities ... 568
        12.2.3 Characterizing Schnorr triviality .............. 569
   12.3 Tracing weak truth table degrees ...................... 576
        12.3.1 Basics ......................................... 576
        12.3.2 Reducibilities with tiny uses .................. 576
        12.3.3 Anti-complex sets and tiny uses ................ 578
        12.3.4 Anti-complex sets and Schnorr triviality ....... 580
   12.4 Lowness for weak genericity and randomness ............ 581
   12.5 Lowness for computable randomness ..................... 586
   12.6 Lowness for pairs of randomness notions ............... 590
13 Algorithmic Dimension ...................................... 592
   13.1 Classical Hausdorff dimension ......................... 592
   13.2 Hausdorff dimension via gales ......................... 594
   13.3 Effective Hausdorff dimension ......................... 596
   13.4 Shift complex sets .................................... 601
   13.5 Partial randomness .................................... 602
   13.6 A correspondence principle for effective dimension .... 607
   13.7 Hausdorff dimension and complexity extraction ......... 608
   13.8 A Turing degree of nonintegral Hausdorff dimension .... 611
   13.9 DNC functions and effective Hausdorff dimension ....... 618
        13.9.1 Dimension in h-spaces .......................... 619
        13.9.2 Slow-growing DNC functions and dimension ....... 623
   13.10 C-independence and Zimand's Theorem .................. 627
   13.11 Other notions of dimension ........................... 635
        13.11.1 Box counting dimension ........................ 635
        13.11.2 Effective box counting dimension .............. 636
        13.11.3 Packing dimension ............................. 638
        13.11.4 Effective packing dimension ................... 641
   13.12 Packing dimension and complexity extraction .......... 642
   13.13 Clumpy trees and minimal degrees ..................... 645
   13.14 Building sets of high packing dimension .............. 648
   13.15 Computable dimension and Schnorr dimension ........... 654
        13.15.1 Basics ........................................ 654
        13.15.2 Examples of Schnorr dimension ................. 657
        13.15.3 A machine characterization of Schnorr
                dimension ..................................... 658
        13.15.4 Schnorr dimension and computable
                enumerability ................................. 659
   13.16 The dimensions of individual strings ................. 662

IV Further Topics ............................................. 667

14 Strong Jump Traceability ................................... 668
   14.1 Basics ................................................ 668
   14.2 The ideal of strongly jump traceable c.e. sets ........ 672
   14.3 Strong jump traceability and K-triviality: the
        c.e. case ............................................. 680
   14.4 Strong jump traceability and diamond classes .......... 689
   14.5 Strong jump traceability and K-triviality: the
        general case .......................................... 700
15 Ω as an Operator ........................................... 705
   15.1 Introduction .......................................... 705
   15.2 Omega operators ....................................... 707
   15.3 A-1-random A-left-c.e. reals .......................... 709
   15.4 Reals in the range of some Omega operator ............. 711
   15.5 Lowness for Ω ......................................... 712
   15.6 Weak lowness for К .................................... 713
        15.6.1 Weak lowness for К and lowness for Ω ........... 714
        15.6.2 Infinitely often strongly K-random sets ........ 715
   15.7 When ΩA is a left-c.e. real ........................... 716
   15.8 ΩA for K-trivial A .................................... 719
   15.9 K-triviality and left-d.c.e. reals .................... 722
   15.10 Analytic behavior of Omega operators ................. 722
16 Complexity of Computably Enumerable Sets ................... 728
   16.1 Barzdins' Lemma and Kummer complex sets ............... 728
   16.2 The entropy of computably enumerable sets ............. 731
   16.3 The collection of nonrandom strings ................... 738
        16.3.1 The plain and conditional cases ................ 738
        16.3.2 The prefix-free case ........................... 743
        16.3.3 The overgraphs of universal monotone
               machines ....................................... 752
        16.3.4 The strict process complexity case ............. 761

References .................................................... 767
Index ......................................................... 797


Архив выставки новых поступлений | Отечественные поступления | Иностранные поступления | Сиглы
 

[О библиотеке | Академгородок | Новости | Выставки | Ресурсы | Библиография | Партнеры | ИнфоЛоция | Поиск]
  Пожелания и письма: branch@gpntbsib.ru
© 1997-2024 Отделение ГПНТБ СО РАН (Новосибирск)
Статистика доступов: архив | текущая статистика
 

Документ изменен: Wed Feb 27 14:23:50 2019. Размер: 25,019 bytes.
Посещение N 1229 c 04.09.2012