Index 201 omega, 130 K, 78, see also halting set K(σ), 159 K-trivial, 169 KC Theorem, 161 Kolmogorov complexity plain, 167 prefix-free, 159 Kraft inequality, 160, 166 lambda calculus, 69 language, 103, 170 lattice, 146 complemented, 146 distributive, 146 embedding, 150 nondistributive, 152 least upper bound, 28 left-c.e. set, 125, 166 limit lemma, 139 limit, discrete, 41, 140 linear order, 27, 176 low basis theorem, 183 low for random, 169 low set, 130, 140 noncomputable, 142 lower bound, 28 maximal set, 154 measure, 158 meet, 128, 146 model, 103, 170, 180 modular arithmetic, 26 modulus, 140 lemma, 140 μ, 55 negation, 10, 15 nondeterministic Turing machine, 68 nonstandard model, 104, 174, 175 nonuniformity, see uniformity not, 10 Ω, 165 or, logical, 10 oracle, 109 finite, 111 notation, 111 oracle Turing machine, 109 orbit, 147 overspill, 175 padding lemma, 60 pairing function, 57 parameter, 180 parametrization, 79 partial computable functions, 65 partial function, 42 argument for allowing, 55, 62 partial order, 27 partition, 26 Peano arithmetic, 173, 175 in reverse math, 183 permutation, 30 ϕe, 60 Π1 1 comprehension axiom, 184 pigeonhole principle, 186 plain Kolmogorov complexity, 167 poset, 27 Post correspondence system, 91 Post’s problem, 115, 120 Post’s theorem, 134 power set, 16, 192 predicate, 13 prefix-free Kolmogorov complexity, 159 Turing machine, 158 primitive recursion, 51 priority, 116, 117, 121 product, Cartesian, 16 production, 87 normal, 88 semi-Thue, 88 projection, 51 quantifiers, 13 alternation of, 131 collapsing like, 133 quotient structure, 25, see also Turing degree, E∗ randomness, 155, 159 and Turing degree, 165 for finite strings, 159 relative, 168 range, 29
Previous Page Next Page