202 Index
read/write head, 44
recursion theorem, 81
with parameters, 142
recursive, 96
recursive comprehension axiom,
179
recursive definition
of a function, 35
of a set, 33
reduction property, 100
reflexivity, 22
relation, 21
relative randomness, 168
relativization, 128
requirement, 106, 117
injury, 116
priority, 116
satisfaction, 107
restriction, 112, 157
reverse mathematics, 177
Rice’s theorem, 82
Robinson arithmetic, 104, 173
nonstandard model, 174
s-m-n theorem, 79, 82, 84
relativized, 128
satisfaction, 107
second-order arithmetic, 178
second-order theory, 173, 178
semantics, 103, 172
semi-Thue system, 88, 92
sentence, 13
sequence, 43, 157
set, 15
arithmetical, 131
bi-immune, 124
computable, 96
computably enumerable, 97
creative, 145
d.c.e., 125
high, 154
left-c.e., 125, 166
low, 130, 140
maximal, 154
productive, 145
simple, 106, see also simple set
simple set, 106, 117, 146, 164
effectively, 145
incomplete, 120, 142
nowhere, 153
promptly, 151
solvable, 85
soundness theorem, 103, 172
splitting theorem, 153
stage bounding
notation, 96, 100, 111
use of, 111, 118, 121, 136
standard model, 104, 173
string, 43, 157
structure, 170
computably categorical, 176
subset, 16
successor, 51
surjection, 30
symmetric difference, 114, 136, 144,
145
symmetry, 22
syntax, 103, 172
tape, 44
tautology, 10
theorem of a production system, 88
theory, 170
first-order, 173
second-order, 173, 178
total computable functions, 65
total order, 27
transitive closure, 27
transitivity, 22, 147
truth table, 12
tuple, 16
Turing completeness, 114
Turing degree, 127, 149
and randomness, 165
c.e., 128, 149
Turing equivalence, 112
Turing jump, 129
Turing machine, 44
busy beaver, 78
code of, 59
enumeration of, 60
index of, 60
nondeterministic, 68
nonstandard, 67
oracle, 109
prefix-free, 158
Previous Page Next Page