What Is A Computer and What Can It Do?

What Is A Computer and What Can It Do?
An Algorithms-Oriented Introduction to the Theory of Computation

Table of Contents


	Preface		ix

1	Introduction		1
	1.1	A simple question	1
	1.2	Decision problems	2
	1.3	What is a computer?	8
	1.4	Recap	12

2	Finite State Machines		15
	2.1	Introduction	15
	2.2	Focus on the states	17
	2.3	Deciding {0ⁿ1ⁿ: n ≥ 0} using a finite number of states... or not	21

3	Turing Machines		23
	3.1	Introduction	23
	3.2	Turing machines can count!	31
	3.3	The Church-Turing Thesis	35
	3.4	So what exactly is a computer anyway?	37

4	Unsolvable Problems		39
	4.1	Introduction	39
	4.2	Reductions	43
	4.3	Rice's Theorem	49
	4.4	Exercises	50

5	Nondeterminism		53
	5.1	Introduction	53
	5.2	Nondeterminstic search algorithms	55
	5.3	Nondeterministic finite automata	60
	5.4	Free will is useless	66

6	Computational Complexity		73
	6.1	Introduction	73
	6.2	Time	76
	6.3	Combinatorial explosions	79
	6.4	Polynomial time reductions	86
	6.5	NP-complete problems.	91
	6.6	Proof of the Cook-Levin Theorem	93

7	Reduce, Reuse, Recycle!		101
	7.1	Introduction	101
	7.2	Three is a crowd.	102
	7.3	First grade math.	107
	7.4	HAMILTONIAN CYCLE is NP-complete	117

8	Is it Better to Be a Pig? Approximation Algorithms		123
	8.1	Introduction	123
	8.2	Optimization problems	129
	8.3	Approximately optimal solutions to hard problems	130
	8.4	Fully polynomial time approximation schemes	135
	8.5	Finding good enough solutions is not always easy.	145

9	Is It Better To Be an Ant? Heuristics For Hard Problems		149
	9.1	Introduction	149
	9.2	Local Search	150
	9.3	SAT Solvers	152

10	Space		163
	10.1	Introduction	163
	10.2	Hierarchy Theorems	171
	10.3	Relating Space, Time, and Everything Else	175

11	Conclusion		181

	Solutions to Exercises		183
		Solutions for Chapter 1: Introduction	183
		Solutions for Chapter 2: Finite Automata	185
		Solutions for Chapter 3: Turing Machines	189
		Solutions for Chapter 4: Unsolvable Problems	213
		Solutions for Chapter 5: Nondeterminism	221
		Solutions for Chapter 6: Computational Complexity	223
		Solutions for Chapter 7: Reduce, Reuse, Recycle	231
		Solutions for Chapter 8: Approximation Algorithms	251
		Solutions for Chapter 9: Heuristics	265
		Solutions for Chapter 10: Space	269

	Chapter Notes		279
		Notes on Chapter 1: Introduction	279
		Notes on Chapter 2: Finite Automata	279
		Notes on Chapter 3: Turing Machines	279
		Notes on Chapter 4: Unsolvable Problems	280
		Notes on Chapter 5: Nondeterminism	280
		Notes on Chapter 6: Computational Complexity	280
		Notes on Chapter 7: Reduce, Reuse, Recycle	281
		Notes on Chapter 8: Approximation Algorithms	281
		Notes on Chapter 9: Heuristics	281
		Notes on Chapter 10: Space	282

	Stuff you need to know		283
		Miscellaneous	283
		Algorithms	283

	Acknowledgements		289

	Bibliography		291

	Index		295