Computability and randomness

Contents......Page 10
1 The complexity of sets......Page 18
Partial computable functions......Page 20
Computably enumerable sets......Page 23
Indices and approximations......Page 24
Many-one reducibility......Page 25
Turing reducibility......Page 26
Relativization and the jump operator......Page 27
Strings over {0, 1}......Page 29
Approximating the functionals Φ[sub(e)], and the use principle......Page 30
Weak truth-table reducibility and truth-table reducibility......Page 31
1.3 Sets of natural numbers......Page 33
Δ[sup(0)][sub(2)]sets and the Shoenfield Limit Lemma......Page 35
Sets and functions that are n-c.e. or Ρ-c.e.......Page 36
Degree structures on particular classes *......Page 37
The arithmetical hierarchy......Page 38
1.5 Absolute computational complexity of sets......Page 41
Sets that are low[sub(n)]......Page 43
Computably dominated sets......Page 44
Sets that are high[sub(n)]......Page 45
1.6 Post’s problem......Page 46
Turing incomparable Δ[sup(0)][sub(2)]-sets......Page 47
Simple sets......Page 48
A c.e. set that is neither computable nor Turing complete......Page 49
Is there a natural solution to Post’s problem?......Page 51
Turing incomparable c.e. sets......Page 52
1.7 Properties of c.e. sets......Page 54
Each incomputable c.e. wtt-degree contains a simple set......Page 55
Hypersimple sets......Page 56
Promptly simple sets......Page 57
Minimal pairs and promptly simple sets......Page 58
Creative sets *......Page 60
1.8 Cantor space......Page 62
Binary trees and closed sets......Page 64
Compactness and clopen sets......Page 65
The correspondence between subsets of N and real numbers......Page 66
Effectivity notions for real numbers......Page 67
Effectivity notions for classes of sets......Page 69
Examples of II[sup(0)][sub(1)] classes......Page 72
The Low Basis Theorem......Page 73
The basis theorem for computably dominated sets......Page 76
Weakly 1-generic sets......Page 78
1-generic sets......Page 80
The arithmetical hierarchy of classes......Page 81
Comparing Cantor space with Baire space......Page 84
Outer measures......Page 85
Measures......Page 86
Uniform measure and null classes......Page 87
Uniform measure of arithmetical classes......Page 88
Probability theory......Page 90
2 The descriptive complexity of strings......Page 91
Machines and descriptions......Page 92
The counting condition, and incompressible strings......Page 94
Invariance, continuity, and growth of C......Page 96
Algorithmic properties of C......Page 98
2.2 The prefix-free complexity K......Page 99
Prefix-free machines......Page 100
The Machine Existence Theorem and a characterization of K......Page 103
The Coding Theorem......Page 108
Basics......Page 109
An expression for K (x,y) *......Page 110
Basic interactions......Page 111
Solovay’s equations *......Page 112
2.5 Incompressibility and randomness for strings......Page 114
Comparing incompressibility notions......Page 115
Randomness properties of strings......Page 116
3.1 A mathematical definition of randomness for sets......Page 119
Martin-Löf tests and their variants......Page 121
The initial segment approach......Page 122
The test concept......Page 123
Characterization of MLR via the initial segment complexity......Page 124
Examples of Martin-Löf random sets......Page 125
Facts about ML-random sets......Page 126
Left-c.e. ML-random reals and Solovay reducibility......Page 130
Randomness on reals, and randomness for bases other than 2......Page 132
A nonempty II[sup(0)][sub(1)] subclass of MLR has ML-random measure *......Page 133
Each set is weak truth-table reducible to a ML-random set......Page 134
Autoreducibility and indifferent sets *......Page 136
3.4 Martin-Löf randomness relative to an oracle......Page 137
Relativizing C and K......Page 138
Symmetry of relative Martin-Löf randomness......Page 139
Computational complexity, and relative randomness......Page 141
The halting probability Ω relative to an oracle *......Page 142
3.5 Notions weaker than ML-randomness......Page 144
Weak randomness......Page 145
Schnorr randomness......Page 146
Computable measure machines......Page 148
3.6 Notions stronger than ML-randomness......Page 150
Weak 2-randomness......Page 151
2-randomness and initial segment complexity......Page 153
2-randomness and being low for Ω......Page 157
Demuth randomness *......Page 158
4 Diagonally noncomputable functions......Page 161
Basics on d.n.c. functions and fixed point freeness......Page 162
The initial segment complexity of sets of d.n.c. degree......Page 164
A completeness criterion for c.e. sets......Page 165
4.2 Injury-free constructions of c.e. sets......Page 167
Each Δ[sup(0)][sub(2)] set of d.n.c. degree bounds a promptly simple set......Page 168
Variants of Kučera’s Theorem......Page 169
An injury-free proof of the Friedberg–Muchnik Theorem *......Page 171
4.3 Strengthening the notion of a d.n.c. function......Page 172
Sets of PA degree......Page 173
Martin-Löf random sets of PA degree......Page 174
Turing degrees of Martin-Löf random sets *......Page 176
Relating n-randomness and higher fixed point freeness......Page 177
5 Lowness properties and K-triviality......Page 180
Being low for K......Page 182
Lowness for ML-randomness......Page 184
When many oracles compute a set......Page 185
Bases for ML-randomness......Page 187
Lowness for weak 2-randomness......Page 191
Basics on K-trivial sets......Page 193
K-trivial sets are Δ[sup(0)][sub(2)]......Page 194
The number of sets that are K-trivial for a constant b *......Page 196
Closure properties of K......Page 198
C-trivial sets......Page 199
Replacing the constant by a slowly growing function *......Page 200
5.3 The cost function method......Page 201
The basics of cost functions......Page 203
A cost function criterion for K-triviality......Page 205
Cost functions and injury-free solutions to Post’s problem......Page 206
Construction of a promptly simple Turing lower bound......Page 207
K-trivial sets and Σ[sub(1)]-induction *......Page 209
Avoiding to be Turing reducible to a given low c.e. set......Page 210
Necessity of the cost function method for c.e. K-trivial sets......Page 212
Listing the (ω-c.e.) K-trivial sets with constants......Page 213
Adaptive cost functions......Page 215
5.4 Each K-trivial set is low for K......Page 217
Introduction to the proof......Page 218
The formal proof of Theorem 5.4.1......Page 227
A Main Lemma derived from the golden run method......Page 232
The standard cost function characterizes the K-trivial sets......Page 234
The number of changes *......Page 236
Ω[sup(A)] for K-trivial A......Page 238
Each K-trivial set is low for weak 2-randomness......Page 240
5.6 The weak reducibility associated with Low(MLR)......Page 241
Preorderings coinciding with LR-reducibility......Page 243
A stronger result under the extra hypothesis that A ≤[sub(T)] B'......Page 245
The size of lower and upper cones for ≤[sub(LR)] *......Page 247
Operators obtained by relativizing classes......Page 248
Studying ≤[sub(LR)] by applying the operator K......Page 249
Comparing the operators S[sub(LR)] and K *......Page 250
Uniformly almost everywhere dominating sets......Page 251
Ø' ≤[sub(LR)] C if and only if C is uniformly a.e. dominating......Page 252
6 Some advanced computability theory......Page 255
Basics and a first example......Page 256
C.e. oracles, markers, and a further example......Page 257
6.2 Promptly simple degrees and low cuppability......Page 259
C.e. sets of promptly simple degree......Page 260
A c.e. degree is promptly simple iff it is low cuppable......Page 261
The basics of c.e. operators......Page 264
Pseudojump inversion......Page 266
Applications of pseudojump inversion......Page 268
Inversion of a c.e. operator via a ML-random set......Page 270
Separation of highness properties......Page 273
Minimal pairs and highness properties *......Page 275
7 Randomness and betting strategies......Page 276
Formalizing the concept of a betting strategy......Page 277
Supermartingales......Page 278
Some basics on supermartingales......Page 279
Sets on which a supermartingale fails......Page 280
7.2 C.e. supermartingales and ML-randomness......Page 281
Characterizing ML-randomness via c.e. supermartingales......Page 282
The degree of nonrandomness in ML-random sets *......Page 283
Schnorr randomness and martingales......Page 285
Preliminaries on computable martingales......Page 287
7.4 How to build a computably random set......Page 288
Three preliminary Theorems: outline......Page 289
Partial computable martingales......Page 290
A template for building a computably random set......Page 291
Computably random sets and initial segment complexity......Page 292
The case of a partial computably random set......Page 294
Martingales that dominate......Page 296
Each high c.e. degree contains a computably random......Page 297
A computably random set that is not partial computably random......Page 298
A strictly computably random set in each high degree......Page 300
A strictly Schnorr random set in each high degree......Page 302
Stochasticity......Page 305
Stochasticity and initial segment complexity......Page 306
Nonmonotonic betting strategies......Page 311
Muchnik’s splitting technique......Page 312
Kolmogorov–Loveland randomness......Page 314
8 Classes of computational complexity......Page 318
The Low(Ω) basis theorem......Page 320
Being weakly low for K......Page 322
2-randomness and strong incompressibility K......Page 325
Each computably dominated set in Low(Ω) is computable......Page 326
A related result on computably dominated sets in GL[sub(1)]......Page 328
8.2 Traceability......Page 329
C.e. traceable sets and array computable sets......Page 330
Computably traceable sets......Page 333
Lowness for computable measure machines......Page 335
Facile sets as an analog of the K-trivial sets *......Page 336
8.3 Lowness for randomness notions......Page 338
Lowness for C-null classes......Page 339
The class Low(MLR, SR)......Page 340
Classes that coincide with Low(SR)......Page 343
Low(MLR, CR) coincides with being low for K......Page 345
Basics of jump traceability, and existence theorems......Page 353
Jump traceability and descriptive string complexity......Page 355
The weak reducibility associated with jump traceability......Page 356
Jump traceability and superlowness are equivalent for c.e. sets......Page 358
Strong jump traceability......Page 360
Strong superlowness*......Page 363
Some K-trivial c.e. set is not strongly jump traceable......Page 365
Strongly jump traceable c.e. sets and benign cost functions......Page 368
The diamond operator......Page 373
A diagram of downward closed properties......Page 378
Computational complexity versus randomness......Page 380
Some updates......Page 381
9 Higher computability and randomness......Page 382
II[sup(1)[sub(1)] and other relations......Page 383
Representing II[sup(1)][sub(1)] relations by well-orders......Page 384
II[sup(1)][sub(1)] classes and the uniform measure......Page 386
Reducibilities......Page 387
A set theoretical view......Page 388
9.2 Analogs of Martin-Löf randomness and K-triviality......Page 389
II[sup(1)][sub(1)] Machines and prefix-free complexity......Page 390
An analog of K-triviality......Page 393
Lowness for II[sup(1)][sub(1)]-ML-randomness......Page 394
9.3 Δ[sup(1)][sub(1)]-randomness and II[sup(1)][sub(1)]-randomness......Page 395
Notions that coincide with Δ[sup(1)][sub(1)]-randomness......Page 396
More on II[sup(1)][sub(1)]-randomness......Page 397
Hyp-dominated sets......Page 398
Traceability......Page 399
Solutions to Chapter 1......Page 402
Solutions to Chapter 2......Page 406
Solutions to Chapter 3......Page 408
Solutions to Chapter 4......Page 410
Solutions to Chapter 5......Page 412
Solutions to Chapter 6......Page 416
Solutions to Chapter 7......Page 417
Solutions to Chapter 8......Page 419
Solutions to Chapter 9......Page 425
References......Page 427
Notation Index......Page 435
B......Page 440
C......Page 441
D......Page 442
H......Page 443
K......Page 444
M......Page 445
O......Page 446
R......Page 447
S......Page 448
T......Page 449
Z......Page 450