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
|
