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

Thomas C. O'Connell

College Publications


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 {0n1n: 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