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'sapproach 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 bookdevelopsthe 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 thehighlevel language approach of URMs as opposed to theTuring Machine since URMs relate more directly to programminglearned in priorexperiences. The author presentsthe topics ofautomata and languagesonly afterreaders 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. INDICE: Preface xi1. Mathematical Foundations 11.1 Sets and Logic; Naïvely 11.2 Relations and Functions 401.3 Big and Small Infinite Sets; Diagonalization 521.4 Induction from a User’s Perspective 611.5 Why Induction Ticks 681.6 Inductively Defined Sets1.7 Recursive Definitions of Functions1.8 Additional Exercises 852. Algorithms, Computable Functions and Computations 912.1 A Theoryof Computability 912.2 A programming Formalism for the Primitive Recursive Functions Function Class 1472.3 URM Computations and their Arithmetization 1412.4 A double-recursion that leads outside the Primitive Recursive Function Class2.5 Semi-computable Relations: Unsolvability2.6 The Iteration Theorem of Kleene 1722.7 Diagonalization Revisited; Unsolvability via Reductions 1752.8 Productive and Creative Sets 2092.9 The Recursion Theorem 2142. 10 Completeness 2172.11 Unprovability from Unsolvability 2212.12 Additional Exercises 2343. A Subset of the URM Language; FA and NFA 2413.1 Deterministic Finite Automata and their Languages 2433.2 Nondeterministic Finite Automata3.3 Regular Expressions 2663.4 Regular Grammars and Languages 2773.5 Additional Exercises 2874. Adding a stack of a NFA: Pushdown Automata4.1 The PDA 2944.2 PDA Computations 2944.3 The PDA-acceptable Languages are the Context Free Languages 3054.4 Non-ContextFree Languages; Another Pumping Lemma 3124.5 Additional Exercise 3225. Computational Complexity 3255.1 Adding a second stack; Turning Machines 3255.2 Axt, loop program, and Grzegorczyk hierarchies5.3 Additional Exercised
- ISBN: 978-1-118-01478-3
- Editorial: John Wiley & Sons
- Encuadernacion: Cartoné
- Páginas: 416
- Fecha Publicación: 11/05/2012
- Nº Volúmenes: 1
- Idioma: Inglés