ALGORITHMIC RANDOMNESS AND COMPLEXITY
CONTENTS I BACKGROUND PRELIMINARIES NOTATION AND CONVENTIONS BASICS FROM MEASURE THEORY COMPUTABILITY THEORY COMPUTABLE FUNCTIONS AND THE HALTING PROBLEM COMPUTABLE ENUMERABILITY AND RICE’S THEOREM THE RECURSION THEOREM REDUCTIONS ORACLE MACHINES AND TURING REDUCIBILITY STRONG REDUCIBILITIES THE ARITHMETIC HIERARCHY THE LIMIT LEMMA AND POST’S THEOREM A NOTE ON REDUCTIONS THE ?NITE EXTENSION METHOD FINITE INJURY ARGUMENTS OF UNBOUNDED TYPE 5 10 1 SACKS’ SPLITTING THEOREM 5 10 2 THE PSEUDO-JUMP THEOREM THE IN?NITE INJURY METHOD 5 11 1 PRIORITY TREES AND GUESSING 5 11 2 THE MINIMAL PAIR METHOD 5 11 3 HIGH COMPUTABLY ENUMERABLE DEGREES 5 11 4 THE THICKNESS LEMMA THE DENSITY THEOREM JUMP THEOREMS HYPERIMMUNE-FREE DEGREES MINIMAL DEGREES 1 CLASSES 5 16 1 BASICS N CLASSES 5 16 3 BASIS THEOREMS 5 16 4 GENERALIZING THE LOW BASIS THEOREM STRONG REDUCIBILITIES AND POST’S PROGRAM PA DEGREES FIXED-POINT FREE AND DIAGONALLY NONCOMPUTABLE FUNCTIONS DIRECT CODING INTO DNC DEGREES ARRAY NONCOMPUTABILITY AND TRACEABILITY KOLMOGOROV COMPLEXITY OF FINITE STRINGS PLAIN KOLMOGOROV COMPLEXITY CONDITIONAL COMPLEXITY SYMMETRY OF INFORMATION INFORMATION-THEORETIC CHARACTERIZATIONS OF COMPUTABILITY PRE?X-FREE MACHINES AND COMPLEXITY THE KC THEOREM BASIC PROPERTIES OF PRE?X-FREE COMPLEXITY COMPUTABLE BOUNDS FOR K(X) THE CODING THEOREM AND DISCRETE SEMIMEASURES PRE?X-FREE SYMMETRY OF INFORMATION DE?NING PRE?X-FREE RANDOMNESS SOME BASIC ?NITE SETS THE CONDITIONAL COMPLEXITY OF ??GIVEN ? SOME THEOREMS RELATING K AND C LEVIN’S THEOREM SOLOVAY’S THEOREMS RELATING K AND C STRONG K-RANDOMNESS AND C-RANDOMNESS POSITIVE RESULTS COUNTEREXAMPLES MUCHNIK’S THEOREM E?ECTIVE REALS REPRESENTING REALS COMPUTABLY ENUMERABLE REALS AND RANDOMNESS DEGREE-THEORETICAL ASPECTS OF REPRESENTATIONS DEGREES OF REPRESENTATIONS PRESENTATIONS OF REALS IDEALS AND PRESENTATIONS PROMPTLY SIMPLE PRESENTATIONS OF REALS OTHER CLASSES OF REALS D C E REALS RETTINGER’S THEOREM AND D C E RANDOM REALS THE ?ELD OF D C E REALS D C E REALS AND THE ERSHOV HIERARCHY 2 DEGREE CONTAINING NO D C E REALS II RANDOMNESS OF REALS COMPLEXITY OF REALS INTRODUCTION THE COMPUTATIONAL PARADIGM C-OSCILLATIONS K WORKS THE MEASURE-THEORETICAL PARADIGM VILLE’S THEOREM MARTIN-L¨OF : A NEW START THEOREMS OF MILLER AND YU LEVIN’S AND SCHNORR’S CHARACTERIZATION KOLMOGOROV RANDOM VS LEVIN-CHAITIN RANDOM KOLMOGOROV COMPLEXITY AND ?NITE STRINGS KOLMOGOROV RANDOMNESS ARITHMETICAL RANDOMNESS AND STRONG RANDOMNESS APPROXIMATIONS AND OPEN SETS IN?NITELY OFTEN MAXIMALLY COMPLEX REALS NOTES ON 2-RANDOMNESS PLAIN COMPLEXITY AND RANDOMNESS LEVIN’S THEOREM, MEASURES AND DEGREES NON-LEBESGUE MEASURES ATOMIC MEASURES MAKING REALS RANDOM MAKING REALS RANDOM : CONTINUOUS MEASURES DEMUTH’S THEOREM 10 UNPREDICTABILITY AND SCHNORR’S CRITIQUE THE UNPREDICTABILITY PARADIGM 10 1 1 MARTINGALES AND SUPERMARTINGALES 10 1 2 SUPERMARTINGALES AND CONTINUOUS SEMIMEASURES 10 1 3 MARTINGALES VS SUPERMARTINGALES AND OPTIMALITY SCHNORR’S CRITIQUE SCHNORR RANDOMNESS 10 3 1 A MACHINE CHARACTERIZATION 10 3 2 MISCELLANEOUS RESULTS ON COMPUTABLE MACHINES COMPUTABLE RANDOMNESS 10 4 1 SCHNORR RANDOMNESS VIA COMPUTABLE RANDOMNESS 10 4 2 HIGH DEGREES AND SEPARATING NOTIONS OF RANDOMNESS 10 4 3 COMPUTABLE RANDOMNESS AND TESTS 10 4 4 A MACHINE CHARACTERIZATION KURTZ RANDOMNESS 10 5 1 BASICS 10 5 2 A MACHINE CHARACTERIZATION OF KURTZ RANDOMNESS 10 5 3 OTHER CHARACTERIZATIONS OF KURTZ RANDOMNESS 10 5 4 SCHNORR RANDOMNESS VIA KURTZ RANDOMNESS 10 5 5 COMPUTABLY ENUMERABLE KURTZ RANDOM REALS 10 5 6 KURTZ RANDOMNESS AND HYPERIMMUNITY DECIDABLE MACHINES : A UNIFYING CLASS 11 RANDOMNESS AND TURING REDUCIBILITY 1 CLASSES OF RANDOM SETS COMPUTABLY ENUMERABLE DEGREES THE KU?CERA-G´ACS THEOREM KU?CERA CODING 11 4 1 A PROOF OF THE REIMANN-SLAMAN THEOREM RANDOMNESS AND PA DEGREES INDEPENDENCE RESULTS MEASURE THEORY AND TURING REDUCIBILITY STILLWELL’S THEOREM E?ECTIVE 0-1 LAWS 11 10 N-RANDOMNESS AND KURTZ N-RANDOMNESS 11 11 DNC DEGREES AND AUTOCOMPLEX REALS 11 12 N-RANDOM REALS COMPUTE N-FPF FUNCTIONS 11 13 JUMP INVERSION 11 14 PSUEDO-JUMP INVERSION 11 15 RANDOMNESS AND GENERICITY 11 15 1 GENERICITY AND WEAK GENERICITY 11 16 WEAKLY N-GENERIC AND N-GENERIC 11 16 1 N-GENERIC VS N-RANDOM 11 16 2 BELOW ALMOST ALL DEGREES 11 17 EVERY 2-RANDOM IS CEA 11 18 WHERE 1-GENERIC DEGREES ARE DOWNWARD DENSE 11 19 SOLOVAY GENERICITY AND RANDOMNESS 12 VON MISES STRIKES BACK-SELECTION REVISITED MONOTONE SELECTION PARTIAL COMPUTABLE MARTINGALES AND MERKLE’S GAP STOCHASTICITY AND MARTINGALES NOMONOTONIC RANDOMNESS 12 4 1 NONMONOTONIC BETTING STRATEGIES 12 4 2 VAN LAMBALGEN’S THEOREM REVISITED III RELATIVE RANDOMNESS 13 MEASURES OF RELATIVE RANDOMNESS SOLOVAY REDUCIBILITY THE KU?CERA-SLAMAN THEOREM THE STRUCTURE OF THE SOLOVAY DEGREES SW-REDUCIBILITY THE BITS OF ?AND THE YU-DING THEOREM RELATIVE K-REDUCIBILITY A MINIMAL RK-DEGREE ?K AND ?C 13 10 K-DEGREES, C-DEGREES, AND TURING DEGREES 13 11 A MINIMAL C-DEGREE 13 12 DENSITY AND SPLITTINGS 13 13 SCHNORR REDUCIBILITY 13 13 1 DEGREES OF SCHNORR RANDOM LEFT-C E REALS 14 THE QUANTITY OF K- AND OTHER DEGREES, K(?) AND K(?(N)) UNCOUNTABLY CONES OF K- AND C-DEGREES ON K(?) AND OTHER 1-RANDOMS 14 3 1 K(? ?N) VS K(N) FOR ? RANDOM 14 3 2 THE GROWTH RATE OF K(?) AND THE ? FUNCTION 14 3 3 K(?) VS K(??) VAN LAMBALGEN REDUCIBILITY, ?LR, ?C, AND ?K 14 4 1 BASIC PROPERTIES OF THE VAN LAMBALGEN DEGREES 14 4 2 BELOW A Z-RANDOM AND ?T 14 4 3 ?VL, ?K AND ? 14 4 4 ON THE STRUCTURE OF THE MONOTONE AND PROCESS DEGREES 14 4 5 CONTRASTING THE K-DEGREES AND VL-DEGREES RANDOM K-DEGREES ARE COUNTABLE 15 TRIVIALITY AND LOWNESS FOR K K-TRIVIAL AND K-LOW REALS 15 1 1 THE BASIC TRIVIALITY CONSTRUCTION : THE TAILSUM GAME 15 1 2 THE REQUIREMENT-FREE VERSION 15 1 3 THERE ARE FEW K-TRIVIAL REALS 15 1 4 THE G FUNCTION 15 1 5 LOWNESS 15 1 6 K-TRIVIALS SOLVE POST’S PROBLEM 15 1 7 THE DECANTER METHOD 15 1 8 THE ?RST APPROXIMATION, WTT-INCOMPLETENESS 15 1 9 THE SECOND APPROXIMATION: IMPOSSIBLE CONSTANTS 15 1 10 THE LESS IMPOSSIBLE CASE 15 1 11 K-TRIVIALS FORM IS A ROBUST CLASS 15 1 12 MORE CHARACTERIZATIONS OF THE K-TRIVIALS 15 1 13 BASES OF CONES OF 1-RANDOMNESS 15 1 14 LOWNESS FOR KURTZ 2-RANDOMNESS 15 1 15 K-TRIVIALS ARE CLOSED UNDER + LISTING THE K-TRIVIALS MARTIN-L¨OF CUPPING, AND OTHER VARIATIONS NIES LOW2 TOP THEOREM 15 4 1 THE PRIORITY TREE 15 4 2 THE CONSTRUCTION 15 4 3 THE VERI?CATION STRONG JUMP TRACEABILITY 15 5 1 BASICS 15 5 2 THE C E CASE: DISTINCTNESS 15 5 3 THE FORMAL CONSTRUCTION AND PROOF 15 5 4 AN IDEAL 15 5 5 THE FORMAL CONSTRUCTION AND PROOF 15 5 6 STRONGLY JUMP-TRACEABLE C E SETS ARE K-TRIVIAL 15 5 7 THE FORMAL CONSTRUCTION AND PROOF 15 5 8 THE GENERAL CASE ON THE LOW FOR ?REALS WEAKLY LOW FOR K AND STRONG CHAITIN RANDOMNESS 15 7 1 WEAK LOWNESS AND ? 15 7 2 STRONG CHAITIN RANDOMNESS ?A FOR K-TRIVIAL A THE CSIMA-MONTALB´AN FUNCTION 15 10 PRESENTATIONS OF K-TRIVIAL REALS 16 LOWNESS FOR OTHER RANDOMNESS NOTIONS SCHNORR LOWNESS 16 1 1 LOWNESS FOR SCHNORR NULL SETS 16 1 2 LOWNESS FOR SCHNORR RANDOMNESS LOWNESS FOR COMPUTABLE MACHINES SCHNORR TRIVIALS 16 3 1 MORE ON THE DEGREES OF SCHNORR TRIVIALS 16 3 2 SCHNORR TRIVIALITY AND STRONG REDUCIBILITIES KURTZ LOWNESS LOWNESS FOR COMPUTABLE RANDOMNESS 17 E?ECTIVE HAUSDOR?DIMENSION CLASSICAL HAUSDOR?DIMENSION ORDERS E?ECTIVIZING THINGS S-RANDOMNESS HAUSDOR?DIMENSION, PARTIAL RANDOMNESS AND DEGREES OTHER NOTIONS OF DIMENSION 17 6 1 BOX COUNTING DIMENSION 17 6 2 E?ECTIVE BOX COUNTING DIMENSION 17 6 3 PACKING MEASURES AND PACKING DIMENSION 17 6 4 E?ECTIVE PACKING DIMENSION DIMENSIONS IN OTHER CLASSES SCHNORR NULL SETS AND SCHNORR DIMENSION 17 8 1 BASICS 17 8 2 SCHNORR DIMENSION 17 8 3 SCHNORR DIMENSION AND MARTINGALES EXAMPLES OF SCHNORR DIMENSION 17 10 A MACHINE CHARACTERIZATION OF SCHNORR DIMENSION 17 10 1 SCHNORR DIMENSION AND COMPUTABLE ENUMERABILITY 17 11 THE DIMENSIONS OF INDIVIDUAL STRINGS IV FURTHER TOPICS 18 ?AS AN OPERATOR OMEGA OPERATORS ON A-RANDOM A-C E REALS REALS IN THE RANGE OF SOME OMEGA OPERATOR WHEN ?A IS A C E REAL ANALYTIC BEHAVIOR OF OMEGA OPERATORS 19 COMPLEXITY OF C E SETS BARZDINS’ LEMMA AND KUMMER COMPLEX SETS ON THE ENTROPY OF COMPUTABLY ENUMERABLE SETS DIMENSION FOR COMPUTABLY ENUMERABLE SETS THE COLLECTION OF NON-RANDOM STRINGS 19 4 1 THE PLAIN COMPLEXITY CASE 19 4 2 THE PRE?X-FREE CASE 19 4 3 THE CONDITIONAL CASE REFERENCES