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