Index 203 universal, 62 Turing reduction, 112 unbounded search, 54 uncountable, 21 undecidable problem, see unsolvable problem uniformity, 3, 61, 80, 85, 86, 97, 101, 104, 108, 110, 112, 128, 130, 177 main discussion of, 3, 61, 86, 97, 108, 110 union, 16, 18 universal Turing machine, 62 universe, 16 of a model, 170 unlimited register machine, 73 unsolvable problem, 85 halting problem, 78, see also halting set in behavior of Turing machines, 77, 78, 86 index sets, 82, 87 solutions to Post correspondence systems, 92 word problem for groups, 90 word problem for semi-Thue systems, 89 word problem for Thue systems, 90 upper bound, 27 use, 111 of divergent computations, 111 We, 100 weak jump, 114, 143 relativized, 130 weak onig’s lemma, 181, 182 weak weak onig’s lemma, 185 without loss of generality, 39 witness, 118 word, 87 word problem for groups, 90 for semi-Thue systems, 89
Previous Page Next Page