Models of Computation

Description

Contents......Page 4 Strings......Page 5 2 Recursive Functions......Page 6 Induction on Strings......Page 7 More than 1 Path up the Mountain......Page 9 Indices, Substrings & Subsequences......Page 10 Exercises......Page 11 Languages......Page 22 Building Languages......Page 23 Regular Languages & Regular Expressions......Page 24 Regular Expression Trees......Page 26 Proofs about Regular Expressions......Page 27 Proofs about Regular Languages......Page 29 Exercises......Page 30 Intuition......Page 34 Formal Definitions......Page 35 Another Example......Page 37 Real-World Examples......Page 39 Brute-Force Design Example......Page 40 Combining DFAs - Product Construction......Page 42 Automatic Languages & Closure Properties......Page 44 Proving a Language is Not Regular......Page 46 The Myhill-Nerode Theorem......Page 50 Minimal Automata......Page 51 Exercises......Page 53 Nondeterministic State Machines......Page 58 Intuition......Page 59 ε-Transitions......Page 60 NFA to DFA - Subset Construction......Page 62 Regular Expression to NFA - Thompson Algorithm......Page 64 Another Example......Page 66 NFA to Regular Expression - Han & Wood Algorithm......Page 67 Regular Language Transformations......Page 70 Exercises......Page 72 Definitions......Page 79 Parse Trees......Page 81 From Grammar to Language......Page 82 More Examples......Page 85 Regular Languages are Context-free......Page 88 Not Every Language is Context-free......Page 89 Recursive Automata......Page 90 CNF Conversion Algorithm......Page 93 Exercises......Page 97 6 Turing Machines......Page 99 Why bother?......Page 100 Formal Definitions......Page 101 First Example......Page 102 Variations......Page 103 Computing Functions......Page 105 Variations on Tracks, Heads & Tapes......Page 108 Universal Turing Machines......Page 111 Exercises......Page 114 Acceptable vs Decidable......Page 119 Useful Properties......Page 120 Code is Data - Data is Code......Page 121 Self-Haters gonna self-hate......Page 123 Aside - Uncountable Barbers......Page 124 Nevertheless, Acceptable......Page 125 The Halting Problem via Reduction......Page 126 One Million Years Dungeon!......Page 127 Rice Theorem......Page 129 Rice-McNaughton-Myhill-Shapiro Theorem......Page 132 Turing Machine Behavior......Page 134 Exercises......Page 135 Universal Turing Machines......Page 139 Counter Machines......Page 142 Matrix Mortality......Page 143 Combinator Calculus......Page 144 Exercises......Page 145