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