Theory of Computation

INDEX

1-1 correspondence, 46

1-completeness, 217

1-degree, 219

1-reducibility, 187

1-reducibility, 183

1-way infinite tape, 342

3S AT, 372

a-successor, 261

a.e., 151

acceptance by FA, 247

accepting ID, 333

accepting path, 248, 259

Ackermann, 110

function, 110

Ackermann function, 148

inner argument of, 149

subscript argument of, 149

Algol, 92

algorithm, 91

alphabet, 39

of URM, 93

ambiguity, 75

arithmetical relation, 229

arithmetization, 141

of a URM computation, 141

automata, 242

equivalent, 262

automaton, 242

deterministic, 244

finite, 244

deterministic, 244

nondeterministic, 258

pushdown, 295

state of, 242

axiom

logical, 19

nonlogical, 19

axiom of choice, 198

computable, 198

axiomatic system, 221

reasonable, 222

Backus-Naur Form, 277

basis

of induction, 63

basis function, 101

big-O notation, 339

f (n) = O(g(n)), 339

blank symbol, 331

BNF, 277

Boolean

operations, 109

variables, 15

Boolean variable, 277

bounded multiplication, 110

bounded primitive recursion, 356

bounded quantifiers, 29

bounded recursion

simultaneous, 361

bounded search, 110

alternative, 360

alternative symbol: (y)_<z, 360

symbol: (μy)_<z, 110

bounded summation, 110

restricted, 373

c.e., 167, 170

CA, 227

calculable function, 91

cancelling indices, 58

canonical index, 206

cardinality argument, 162

Cartesian product, 38

Cartesian projection, 87

CFG, 281

CFL, 281

chain in a tree, 316

characteristic function, 59,