| |
| |
| Preface | |
| |
| |
| |
| Mathematical Foundations | |
| |
| |
| |
| Sets and Logic; Na�vely | |
| |
| |
| |
| A Detour via Logic | |
| |
| |
| |
| Sets and their Operations | |
| |
| |
| |
| Alphabets, Strings and Languages | |
| |
| |
| |
| Relations and Functions | |
| |
| |
| |
| Big and Small Infinite Sets; Diagonalization | |
| |
| |
| |
| Induction from a User's Perspective | |
| |
| |
| |
| Complete, or Course-of-Values, Induction | |
| |
| |
| |
| Simple Induction | |
| |
| |
| |
| The Least Principle | |
| |
| |
| |
| The Equivalence of Induction and the Least Principle | |
| |
| |
| |
| Why Induction Ticks | |
| |
| |
| |
| Inductively Defined Sets | |
| |
| |
| |
| Recursive Definitions of Functions | |
| |
| |
| |
| Additional Exercises | |
| |
| |
| |
| Algorithms, Computable Functions and Computations | |
| |
| |
| |
| A Theory of Computability | |
| |
| |
| |
| A Programming Framework for Computable Functions | |
| |
| |
| |
| Primitive Recursive Functions | |
| |
| |
| |
| Simultaneous Primitive Recursion | |
| |
| |
| |
| Pairing Functions | |
| |
| |
| |
| Iteration | |
| |
| |
| |
| A Programming Formalism for the Primitive Recursive Functions | |
| |
| |
| |
| PR vs. L | |
| |
| |
| |
| Incompleteness of PR | |
| |
| |
| |
| URM Computations and their Arithmetization | |
| |
| |
| |
| A Double Recursion that Leads Outside the Primitive Recursive Function Class | |
| |
| |
| |
| The Ackermann Function | |
| |
| |
| |
| Properties of the Ackermann Function | |
| |
| |
| |
| The Ackermann Function Majorizes All the Functions of PR | |
| |
| |
| |
| The Graph of the Ackermann Function is in PR<sub>*</sub> | |
| |
| |
| |
| Semi-computable Relations; Unsolvability | |
| |
| |
| |
| The Iteration Theorem of Kleene | |
| |
| |
| |
| Diagonalization Revisited; Unsolvability via Reductions | |
| |
| |
| |
| More Diagonalization | |
| |
| |
| |
| Reducibility via the S-m-n Theorem | |
| |
| |
| |
| More Dovetailing | |
| |
| |
| |
| Recursive Enumerations | |
| |
| |
| |
| Productive and Creative Sets | |
| |
| |
| |
| The Recursion Theorem | |
| |
| |
| |
| Applications of the Recursion Theorem | |
| |
| |
| |
| Completeness | |
| |
| |
| |
| Unprovability from Unsolvability | |
| |
| |
| |
| Supplement: �<sub>x</sub>(x) ↑ is Expressible in the Language of Arithmetic | |
| |
| |
| |
| Additional Exercises | |
| |
| |
| |
| A Subset of the URM Language; FA and NFA | |
| |
| |
| |
| Deterministic Finite Automata and their Languages | |
| |
| |
| |
| The Flow-Diagram Model | |
| |
| |
| |
| Some Closure Properties | |
| |
| |
| |
| How to Prove that a Set is Not Acceptable by a FA; Pumping Lemma | |
| |
| |
| |
| Nondeterministic Finite Automata | |
| |
| |
| |
| From FA to NFA and Back | |
| |
| |
| |
| Regular Expressions | |
| |
| |
| |
| From a Regular Expression to NFA and Back | |
| |
| |
| |
| Regular Grammars and Languages | |
| |
| |
| |
| From a Regular Grammar to a NFA and Back | |
| |
| |
| |
| Epilogue on Regular Languages | |
| |
| |
| |
| Additional Exercises | |
| |
| |
| |
| Adding a Stack to a NFA: Pushdown Automata | |
| |
| |
| |
| The PDA | |
| |
| |
| |
| PDA Computations | |
| |
| |
| |
| ES vs AS vs ES+AS | |
| |
| |
| |
| The PDA-acceptable Languages are the Context Free Languages | |
| |
| |
| |
| Non Context Free Languages; Another Pumping Lemma | |
| |
| |
| |
| Additional Exercises | |
| |
| |
| |
| Computational Complexity | |
| |
| |
| |
| Adding a Second Stack; Turing Machines | |
| |
| |
| |
| Turing Machines | |
| |
| |
| |
| NP-Completeness | |
| |
| |
| |
| Cook's Theorem | |
| |
| |
| |
| Axt, Loop Program, and Grzegorczyk Hierarchies | |
| |
| |
| |
| Additional Exercises | |
| |
| |
| Bibliography | |
| |
| |
| Index | |