Models of Computation

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