A recursive introduction to the theory of computation Book

	Preface
	Introduction	1
1	Models of Computation	3
1.1	Random Access Machines	4
1.2	Partial Recursive Functions	7
1.3	Pairing and Coding	16
1.4	Simulating an Execution of a RAM Program	20
1.5	Turing Machines	22
1.6	Some Other Models	26
1.7	A Representation for Programs	28
2	Basic Recursive Function Theory	31
2.1	Acceptable Programming Systems	31
2.2	Recursion Theorems	36
2.3	Alternative Characterizations	48
2.4	The Isomorphism Theorem	52
2.5	Algorithmically Unsolvable Problems	54
2.6	Recursively Enumerable Sets	58
3	Abstract Complexity Theory	68
3.1	RAM Pseudospace Measure	69
3.2	Abstract Complexity Measures	70
3.3	Fundamental Results	74
3.4	Complexity Gaps	77
3.5	Complexity Compression	79
3.6	Speed-up	80
3.7	Measures of Program Size	84
3.8	Restricted Programming Systems	88
4	Complete Problems	91
4.1	Reducibilities	91
4.2	Polynomial Computability	94
4.3	The Deterministic Time Hierarchy	95
4.4	Nondeterminism	103
4.5	An NP-Complete Problem	109
4.6	More NP-Complete Problems	116
	Solutions to Selected Exercises	125
	List of Symbols	142
	Index	144