Computability Theory

170 Index

Natural numbers (Continued)

loop and while programs, 21

primitive recursive functions, 95–97

primitive recursiveness, 20, 35, 40

r.e., 136

r.e. relations, 83, 91

register machines, 22, 53, 55

register machines over words, 72, 74

relative computability, 122, 125–126

search operation, 48

set definitions, 151–152

structure of degrees, 133–136

Noncomputable functions, countability, 158

Nondeterministic polynomial time (NP)

definition, 146–147

vs. P-time, 147–148

Nondeterministic Turing machine

basic concept, 14

and P-time computability, 146–147

Normal form theorem

and arithmetic hierarchy, 108–110

and r.e. relations, 82, 86

and register machine relative

computability ...