Index A Acceptable proof and axiomatic theory, 118 and effective calculability, 11 Acceptance procedure and feasible computability, 145 recursively enumerable relations, 81­82 and semidecidability, 9 ADD, register machines, 23 Addition binary arithmetic, 76­77 definability in arithmetic, 111 primitive recursive function, 30­32 P-time computability, 144 register machines, 24, 54 Alphabet decadic notation definitions, 159 loop and while programs, 21 program definition, 61 register machines, 23 register machines over words, 72­73 equivalence relations, 127­130 formal language definability, 25 halting relation example, 8 preordering relations, 130 primitive recursive functions, 35 and P-time computability, 146­147 recursively enumerable relations, 83, 85 universal program, 67 Bounded search, definition and proof, 40­41 Busy beaver problem, and Turing machines, 16 C Calculable functions decidability and semidecidability, 5­6 effectively calculable partial functions, 4­5 halting relation, 8­9 instruction encoding, 7­8 partial functions, 3, 6 total function example, 6