Includes bibliographical references and index.

1 Mathematical foundations -- 2. Algorithms, computable functions and computations -- 3. A subset of the URM language; FA and NFA -- 4. Adding a stack to a NFA: pushdown automata -- 5. Computational complexity.

1 Mathematical Foundations 1 -- 1.1 Sets and Logic; Naïvely 1 -- 1.1.1 A Detour via Logic 2 -- 1.1.2 Sets and their Operations 27 -- 1.1.3 Alphabets, Strings and Languages 39 -- 1.2 Relations and Functions 40 -- 1.3 Big and Small Infinite Sets; Diagonalization 51 -- 1.4 Induction from a User's Perspective 61 -- 1.4.1 Complete, or Course-of-Values, Induction 61 -- 1.4.2 Simple Induction 64 -- 1.4.3 The Least Principle 65 -- 1.4.4 The Equivalence of Induction and the Least Principle 65 -- 1.5 Why Induction Ticks 68 -- 1.6 Inductively Defined Sets 69 -- 1.7 Recursive Definitions of Functions 78 -- 1.8 Additional Exercises 85 -- 2 Algorithms, Computable Functions and Computations 91 -- 2.1 A Theory of Computability 91 -- 2.1.1 A Programming Framework for Computable Functions 92 -- 2.1.2 Primitive Recursive Functions 103 -- 2.1.3 Simultaneous Primitive Recursion 116 -- 2.1.4 Pairing Functions 118 -- 2.1.5 Iteration 123 -- 2.2 A Programming Formalism for the Primitive Recursive Functions 125 -- 2.2.1 PR vs. L 135 -- 2.2.2 Incompleteness of PR 139 -- 2.3 URM Computations and their Arithmetization 141 -- 2.4 A Double Recursion that Leads Outside the Primitive Recursive Function Class 147 -- 2.4.1 The Ackermann Function 148 -- 2.4.2 Properties of the Ackermann Function 149 -- 2.4.3 The Ackermann Function Majorizes All the Functions of PR 153 -- 2.4.4 The Graph of the Ackermann Function is in PR_* 155 -- 2.5 Semi-computable Relations; Unsolvability 158 -- 2.6 The Iteration Theorem of Kleene 172 -- 2.7 Diagonalization Revisited; Unsolvability via Reductions 175 -- 2.7.1 More Diagonalization 176 -- 2.7.2 Reducibility via the S-m-n Theorem 183 -- 2.7.3 More Dovetailing 196 -- 2.7.4 Recursive Enumerations 202 -- 2.8 Productive and Creative Sets 209 -- 2.9 The Recursion Theorem 212 -- 2.9.1 Applications of the Recursion Theorem 214 -- 2.10 Completeness 217 -- 2.11 Unprovability from Unsolvability 221 -- 2.11.1 Supplement: φ_x(x) ↑ is Expressible in the Language of Arithmetic 229 -- 2.12 Additional Exercises 234 -- 3 A Subset of the URM Language; FA and NFA 241 -- 3.1 Deterministic Finite Automata and their Languages 243 -- 3.1.1 The Flow-Diagram Model 243 -- 3.1.2 Some Closure Properties 251 -- 3.1.3 How to Prove that a Set is Not Acceptable by a FA; Pumping Lemma 253 -- 3.2 Nondeterministic Finite Automata 257 -- 3.2.1 From FA to NFA and Back 260 -- 3.3 Regular Expressions 266 -- 3.3.1 From a Regular Expression to NFA and Back 268 -- 3.4 Regular Grammars and Languages 277 -- 3.4.1 From a Regular Grammar to a NFA and Back 282 -- 3.4.2 Epilogue on Regular Languages 285 -- 3.5 Additional Exercises 287 -- 4 Adding a Stack to a NFA: Pushdown Automata 293 -- 4.1 The PDA 294 -- 4.2 PDA Computations 295 -- 4.2.1 ES vs AS vs ES+AS 300 -- 4.3 The PDA-acceptable Languages are the Context Free Languages 305 -- 4.4 Non Context Free Languages; Another Pumping Lemma 312 -- 4.5 Additional Exercises 322 -- 5 Computational Complexity 325 -- 5.1 Adding a Second Stack; Turing Machines 325 -- 5.1.1 Turing Machines 330 -- 5.1.2 NP-Completeness 338 -- 5.1.3 Cook's Theorem 342 -- 5.2 Axt, Loop Program, and Grzegorczyk Hierarchies 350 -- 5.3 Additional Exercises 370.

"In the (meta)theory of computing, the fundamental questions of the limitations of computing are addressed. These limitations, which are intrinsic rather than technology dependent, may immediatly rule out the existence of algorithmic solutions for some problems while for others they rule out efficient solutions. The author's approach is anchored on the concrete (and assumed) practical knowledge about general computer programming, attained readers in a first year programming course, as well as the knowledge of discrete mathematics at the same level. The book develops the metatheory of general computing and builds on the reader's prior computing experience. Metatheory via the programming formalism known as Shepherdson-Sturgis Unbounded Register Machines (URM)--a straightforward abstraction of modern highlevel programming languages--is developed. Restrictions of the URM programming language are also discussed. The author has chosen to focus on the highlevel language approach of URMs as opposed to the Turing Machine since URMs relate more directly to programming learned in prior experiences. The author presents the topics of automata and languages only after readers become familiar, to some extent, with the (general) computability theory including the special computability theory of more "practical" functions, the primitive recursive functions. Automata are presented as a very restricted programming formalism, and their limitations (in expressivity) and their associated languages are studied. In addition, this book contains tools that, in principle, can search a set of algorithms to see whether a problem is solvable, or more specifically, if it can be solved by an algorithm whose computations are efficient. Chapter coverage includes: Mathematical Background; Algorithms, Computable Functions, and Computations; A Subset of the URM Language: FA and NFA; and Adding a Stack to an NFA: Pushdown Automata"-- Provided by publisher."The book develops the metatheory of general computing and builds on the reader's prior computing experience. Metatheory via the programming formalism known as Shepherdson-Sturgis Unbounded Register Machines (URM)--a straightforward abstraction of modern high-level programming languages--is developed. Restrictions of the URM programming language are also discussed. The author has chosen to focus on the high-level language approach of URMs as opposed to the Turing Machine since URMs relate more directly to programming learned in prior experiences"-- Provided by publisher.