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 K¨ onig’s lemma, 181, 182

weak weak K¨ onig’s lemma, 185

without loss of generality, 39

witness, 118

word, 87

word problem

for groups, 90

for semi-Thue systems, 89