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