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