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

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2012 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.