|
|
|
1 | (73) |
|
|
|
3 | (5) |
|
Partial computable functions |
|
|
3 | (3) |
|
Computably enumerable sets |
|
|
6 | (1) |
|
Indices and approximations |
|
|
7 | (1) |
|
Relative computational complexity of sets |
|
|
8 | (8) |
|
|
|
8 | (1) |
|
|
|
9 | (1) |
|
Relativization and the jump operator |
|
|
10 | (2) |
|
|
|
12 | (1) |
|
Approximating the functionals φe, and the use principle |
|
|
13 | (1) |
|
Weak truth-table reducibility and truth-table reducibility |
|
|
14 | (2) |
|
|
|
16 | (1) |
|
|
|
16 | (2) |
|
Descriptive complexity of sets |
|
|
18 | (6) |
|
Δ02 sets and the Shoenfield Limit Lemma |
|
|
18 | (1) |
|
Sets and functions that are n-c.e. or w-c.e. |
|
|
19 | (1) |
|
Degree structures on particular classes |
|
|
20 | (1) |
|
The arithmetical hierarchy |
|
|
21 | (3) |
|
Absolute computational complexity of sets |
|
|
24 | (5) |
|
|
|
26 | (1) |
|
Computably dominated sets |
|
|
27 | (1) |
|
|
|
28 | (1) |
|
|
|
29 | (8) |
|
Turing incomparable Δ02-sets |
|
|
30 | (1) |
|
|
|
31 | (1) |
|
A c.e. set that is neither computable nor Turing complete |
|
|
32 | (2) |
|
Is there a natural solution to Post's problem? |
|
|
34 | (1) |
|
Turing incomparable c.e. sets |
|
|
35 | (2) |
|
|
|
37 | (8) |
|
Each incomputable c.e. wtt-degree contains a simple set |
|
|
38 | (1) |
|
|
|
39 | (1) |
|
|
|
40 | (1) |
|
Minimal pairs and promptly simple sets |
|
|
41 | (2) |
|
|
|
43 | (2) |
|
|
|
45 | (23) |
|
|
|
47 | (1) |
|
Binary trees and closed sets |
|
|
47 | (1) |
|
|
|
48 | (1) |
|
Compactness and clopen sets |
|
|
48 | (1) |
|
The correspondence between subsets of N and real numbers |
|
|
49 | (1) |
|
Effectivity notions for real numbers |
|
|
50 | (2) |
|
Effectivity notions for classes of sets |
|
|
52 | (3) |
|
|
|
55 | (1) |
|
Isolated points and perfect sets |
|
|
56 | (1) |
|
|
|
56 | (3) |
|
The basis theorem for computably dominated sets |
|
|
59 | (2) |
|
|
|
61 | (2) |
|
|
|
63 | (1) |
|
The arithmetical hierarchy of classes |
|
|
64 | (3) |
|
Comparing Cantor space with Baire space |
|
|
67 | (1) |
|
|
|
68 | (6) |
|
|
|
68 | (1) |
|
|
|
69 | (1) |
|
Uniform measure and null classes |
|
|
70 | (1) |
|
Uniform measure of arithmetical classes |
|
|
71 | (2) |
|
|
|
73 | (1) |
|
The descriptive complexity of strings |
|
|
74 | (28) |
|
Comparing the growth rate of functions |
|
|
75 | (1) |
|
The plain descriptive complexity C |
|
|
75 | (7) |
|
Machines and descriptions |
|
|
75 | (2) |
|
The counting condition, and incompressible strings |
|
|
77 | (2) |
|
Invariance, continuity, and growth of C |
|
|
79 | (2) |
|
Algorithmic properties of C |
|
|
81 | (1) |
|
The prefix-free complexity K |
|
|
82 | (10) |
|
|
|
83 | (1) |
|
|
|
83 | (3) |
|
The Machine Existence Theorem and a characterization of K |
|
|
86 | (5) |
|
|
|
91 | (1) |
|
Conditional descriptive complexity |
|
|
92 | (2) |
|
|
|
92 | (1) |
|
An expression for K (x, y) |
|
|
93 | (1) |
|
|
|
94 | (3) |
|
|
|
94 | (1) |
|
|
|
95 | (2) |
|
Incompressibility and randomness for strings |
|
|
97 | (5) |
|
Comparing incompressibility notions |
|
|
98 | (1) |
|
Randomness properties of strings |
|
|
99 | (3) |
|
Martin-Lof randomness and its variants |
|
|
102 | (42) |
|
A mathematical definition of randomness for sets |
|
|
102 | (4) |
|
Martin-Lof tests and their variants |
|
|
104 | (1) |
|
Schnorr's Theorem and universal Martin-Lof tests |
|
|
105 | (1) |
|
The initial segment approach |
|
|
105 | (1) |
|
|
|
106 | (11) |
|
|
|
106 | (1) |
|
A universal Martin-Lof test |
|
|
107 | (1) |
|
Characterization of MLR via the initial segment complexity |
|
|
107 | (1) |
|
Examples of Martin-Lof random sets |
|
|
108 | (1) |
|
Facts about ML-random sets |
|
|
109 | (4) |
|
Left-c.e. ML-random reals and Solovay reducibility |
|
|
113 | (2) |
|
Randomness on reals, and randomness for bases other than 2 |
|
|
115 | (1) |
|
A nonempty II01 subclass of MLR has ML-random measure |
|
|
116 | (1) |
|
Martin-Lof randomness and reduction procedures |
|
|
117 | (3) |
|
Each set is weak truth-table reducible to a ML-random set |
|
|
117 | (2) |
|
Autoreducibility and indifferent sets |
|
|
119 | (1) |
|
Martin-Lof randomness relative to an oracle |
|
|
120 | (7) |
|
|
|
121 | (1) |
|
Basics of relative ML-randomness |
|
|
122 | (1) |
|
Symmetry of relative Martin-Lof randomness |
|
|
122 | (2) |
|
Computational complexity, and relative randomness |
|
|
124 | (1) |
|
The halting probability Ω relative to an oracle |
|
|
125 | (2) |
|
Notions weaker than ML-randomness |
|
|
127 | (6) |
|
|
|
128 | (1) |
|
|
|
129 | (2) |
|
Computable measure machines |
|
|
131 | (2) |
|
Notions stronger than ML-randomness |
|
|
133 | (11) |
|
|
|
134 | (2) |
|
2-randomness and initial segment complexity |
|
|
136 | (4) |
|
2-randomness and being low for Ω |
|
|
140 | (1) |
|
|
|
141 | (3) |
|
Diagonally noncomputable functions |
|
|
144 | (19) |
|
D.n.c. functions and sets of d.n.c. degree |
|
|
145 | (5) |
|
Basics on d.n.c. functions and fixed point freeness |
|
|
145 | (2) |
|
The initial segment complexity of sets of d.n.c. degree |
|
|
147 | (1) |
|
A completeness criterion for c.e. sets |
|
|
148 | (2) |
|
Injury-free constructions of c.e. sets |
|
|
150 | (5) |
|
Each Δ02 set of d.n.c. degree bounds a promptly simple set |
|
|
151 | (1) |
|
Variants of Kucera's Theorem |
|
|
152 | (2) |
|
An injury-free proof of the Friedberg-Muchnik Theorem |
|
|
154 | (1) |
|
Strengthening the notion of a d.n.c. function |
|
|
155 | (8) |
|
|
|
156 | (1) |
|
Martin-Lof random sets of PA degree |
|
|
157 | (2) |
|
Turing degrees of Martin-Lof random sets |
|
|
159 | (1) |
|
Relating n-randomness and higher fixed point freeness |
|
|
160 | (3) |
|
Lowness properties and K-triviality |
|
|
163 | (75) |
|
Equivalent lowness properties |
|
|
165 | (11) |
|
|
|
165 | (2) |
|
Lowness for ML-randomness |
|
|
167 | (1) |
|
When many oracles compute a set |
|
|
168 | (2) |
|
|
|
170 | (4) |
|
Lowness for weak 2-randomness |
|
|
174 | (2) |
|
|
|
176 | (8) |
|
|
|
176 | (1) |
|
|
|
177 | (2) |
|
The number of sets that are K-trivial for a constant b |
|
|
179 | (2) |
|
|
|
181 | (1) |
|
|
|
182 | (1) |
|
Replacing the constant by a slowly growing function |
|
|
183 | (1) |
|
|
|
184 | (16) |
|
The basics of cost functions |
|
|
186 | (2) |
|
A cost function criterion for K-triviality |
|
|
188 | (1) |
|
Cost functions and injury-free solutions to Post's problem |
|
|
189 | (1) |
|
Construction of a promptly simple Turing lower bound |
|
|
190 | (2) |
|
K-trivial sets and σ-induction |
|
|
192 | (1) |
|
A voiding to be Turing reducible to a given low c.e. set |
|
|
193 | (2) |
|
Necessity of the cost function method for c.e. K-trivial sets |
|
|
195 | (1) |
|
Listing the (w-c.e.) K-trivial sets with constants |
|
|
196 | (2) |
|
|
|
198 | (2) |
|
Each K-trivial set is low for K |
|
|
200 | (15) |
|
Introduction to the proof |
|
|
201 | (9) |
|
The formal proof of Theorem 5.4.1 |
|
|
210 | (5) |
|
Properties of the class of K-trivial sets |
|
|
215 | (9) |
|
A Main Lemma derived from the golden run method |
|
|
215 | (2) |
|
The standard cost function characterizes the K-trivial sets |
|
|
217 | (2) |
|
|
|
219 | (2) |
|
|
|
221 | (2) |
|
Each K-trivial set is low for weak 2-randomness |
|
|
223 | (1) |
|
The weak reducibility associated with Low(MLR) |
|
|
224 | (14) |
|
Preorderings coinciding with LR-reducibility |
|
|
226 | (2) |
|
A stronger result under the extra hypothesis that A ≤t B' |
|
|
228 | (2) |
|
The size of lower and upper cones for ≤lr |
|
|
230 | (1) |
|
Operators obtained by relativizing classes |
|
|
231 | (1) |
|
Studying ≤lr by applying the operator K |
|
|
232 | (1) |
|
Comparing the operators Slr and K |
|
|
233 | (1) |
|
Uniformly almost everywhere dominating sets |
|
|
234 | (1) |
|
^≤LR C if and only if C is uniformly a.e. dominating |
|
|
235 | (3) |
|
Some advanced computability theory |
|
|
238 | (21) |
|
Enumerating Turing functionals |
|
|
239 | (3) |
|
Basics and a first example |
|
|
239 | (1) |
|
C.e. oracles, markers, and a further example |
|
|
240 | (2) |
|
Promptly simple degrees and low cuppability |
|
|
242 | (5) |
|
C.e. sets of promptly simple degree |
|
|
243 | (1) |
|
A c.e. degree is promptly simple iff it is low cuppable |
|
|
244 | (3) |
|
C.e. operators and highness properties |
|
|
247 | (12) |
|
The basics of c.e. operators |
|
|
247 | (2) |
|
|
|
249 | (2) |
|
Applications of pseudojump inversion |
|
|
251 | (2) |
|
Inversion of a c.e. operator via a ML-random set |
|
|
253 | (3) |
|
Separation of highness properties |
|
|
256 | (2) |
|
Minimal pairs and highness properties |
|
|
258 | (1) |
|
Randomness and betting strategies |
|
|
259 | (42) |
|
|
|
260 | (4) |
|
Formalizing the concept of a betting strategy |
|
|
260 | (1) |
|
|
|
261 | (1) |
|
Some basics on supermartingales |
|
|
262 | (1) |
|
Sets on which a supermartingale fails |
|
|
263 | (1) |
|
Characterizing null classes by martingales |
|
|
264 | (1) |
|
C.e. supermartingales and ML-randomness |
|
|
264 | (4) |
|
Computably enumerable supermartingales |
|
|
265 | (1) |
|
Characterizing ML-randomness via c.e. supermartingales |
|
|
265 | (1) |
|
Universal c.e. supermartingales |
|
|
266 | (1) |
|
The degree of nonrandomness in ML-random sets |
|
|
266 | (2) |
|
Computable supermartingales |
|
|
268 | (3) |
|
Schnorr randomness and martingales |
|
|
268 | (2) |
|
Preliminaries on computable martingales |
|
|
270 | (1) |
|
How to build a computably random set |
|
|
271 | (8) |
|
Three preliminary Theorems: outline |
|
|
272 | (1) |
|
Partial computable martingales |
|
|
273 | (1) |
|
A template for building a computably random set |
|
|
274 | (1) |
|
Computably random sets and initial segment complexity |
|
|
275 | (2) |
|
The case of a partial computably random set |
|
|
277 | (2) |
|
Each high degree contains a computably random set |
|
|
279 | (9) |
|
Martingales that dominate |
|
|
279 | (1) |
|
Each high c.e. degree contains a computably random left-c.e. set |
|
|
280 | (1) |
|
A computably random set that is not partial computably random |
|
|
281 | (2) |
|
A strictly computably random set in each high degree |
|
|
283 | (2) |
|
A strictly Schnorr random set in each high degree |
|
|
285 | (3) |
|
Varying the concept of a betting strategy |
|
|
288 | (13) |
|
Basics of selection rules |
|
|
288 | (1) |
|
|
|
288 | (1) |
|
Stochasticity and initial segment complexity |
|
|
289 | (5) |
|
Nonmonotonic betting strategies |
|
|
294 | (1) |
|
Muchnik's splitting technique |
|
|
295 | (2) |
|
Kolmogorov-Loveland randomness |
|
|
297 | (4) |
|
Classes of computational complexity |
|
|
301 | (64) |
|
|
|
303 | (9) |
|
|
|
303 | (2) |
|
|
|
305 | (3) |
|
2-randomness and strong incompressibility k |
|
|
308 | (1) |
|
Each computably dominated set in Low(δ) is computable |
|
|
309 | (2) |
|
A related result on computably dominated sets in GL1 |
|
|
311 | (1) |
|
|
|
312 | (9) |
|
C.e. traceable sets and array computable sets |
|
|
313 | (3) |
|
Computably traceable sets |
|
|
316 | (2) |
|
Lowness for computable measure machines |
|
|
318 | (1) |
|
Facile sets as an analog of the K-trivial sets |
|
|
319 | (2) |
|
Lowness for randomness notions |
|
|
321 | (15) |
|
Lowness for C-null classes |
|
|
322 | (1) |
|
|
|
323 | (3) |
|
Classes that coincide with Low(SR) |
|
|
326 | (2) |
|
Low(MLR, CR) coincides with being low for K |
|
|
328 | (8) |
|
|
|
336 | (12) |
|
Basics of jump traceability, and existence theorems |
|
|
336 | (2) |
|
Jump traceability and descriptive string complexity |
|
|
338 | (1) |
|
The weak reducibility associated with jump traceability |
|
|
339 | (2) |
|
Jump traceability and superlowness are equivalent for c.e. sets |
|
|
341 | (2) |
|
More on weak reducibilities |
|
|
343 | (1) |
|
|
|
343 | (3) |
|
|
|
346 | (2) |
|
Subclasses of the K-trivial sets |
|
|
348 | (13) |
|
Some K-trivial c.e. set is not strongly jump traceable |
|
|
348 | (3) |
|
Strongly jump traceable c.e. sets and benign cost functions |
|
|
351 | (5) |
|
|
|
356 | (5) |
|
|
|
361 | (4) |
|
A diagram of downward closed properties |
|
|
361 | (2) |
|
Computational complexity versus randomness |
|
|
363 | (1) |
|
|
|
364 | (1) |
|
Higher computability and randomness |
|
|
365 | (20) |
|
Preliminaries on higher computability theory |
|
|
366 | (6) |
|
|
|
366 | (1) |
|
Well-orders and computable ordinals |
|
|
367 | (1) |
|
Representing II11 relations by well-orders |
|
|
367 | (2) |
|
II11 classes and the uniform measure |
|
|
369 | (1) |
|
|
|
370 | (1) |
|
|
|
371 | (1) |
|
Analogs of Martin-Lof randomness and K-triviality |
|
|
372 | (6) |
|
II11 Machines and prefix-free complexity |
|
|
373 | (3) |
|
A version of Martin-Lof randomness based on II sets |
|
|
376 | (1) |
|
An analog of K-triviality |
|
|
376 | (1) |
|
Lowness for II-ML-randomness |
|
|
377 | (1) |
|
Δ11-randomness and II-randomness |
|
|
378 | (3) |
|
Notions that coincide with δ-randomness |
|
|
379 | (1) |
|
|
|
380 | (1) |
|
Lowness properties in higher computability theory |
|
|
381 | (4) |
|
|
|
381 | (1) |
|
|
|
382 | (3) |
|
Solutions to the exercises |
|
|
385 | (25) |
|
|
|
385 | (4) |
|
|
|
389 | (2) |
|
|
|
391 | (2) |
|
|
|
393 | (2) |
|
|
|
395 | (4) |
|
|
|
399 | (1) |
|
|
|
400 | (2) |
|
|
|
402 | (6) |
|
|
|
408 | (2) |
| References |
|
410 | (8) |
| Notation Index |
|
418 | (5) |
| Index |
|
423 | |
