LEADER 06729nam 2200721Ia 450 001 9910824075303321 005 20240516104925.0 010 $a1-280-59246-X 010 $a9786613622297 010 $a1-118-31535-9 010 $a1-118-31536-7 010 $a1-118-31533-2 035 $a(CKB)2670000000177419 035 $a(EBL)837606 035 $a(SSID)ssj0000641999 035 $a(PQKBManifestationID)11393687 035 $a(PQKBTitleCode)TC0000641999 035 $a(PQKBWorkID)10646909 035 $a(PQKB)11599116 035 $a(PQKBManifestationID)16033612 035 $a(PQKB)21357800 035 $a(DLC) 2012003569 035 $a(Au-PeEL)EBL837606 035 $a(CaPaEBR)ebr10560654 035 $a(CaONFJC)MIL362229 035 $a(CaSebORM)9781118014783 035 $a(MiAaPQ)EBC837606 035 $a(OCoLC)795914179 035 $a(PPN)196870054 035 $a(EXLCZ)992670000000177419 100 $a20120125d2012 uy 0 101 0 $aeng 135 $aurcn||||||||| 181 $ctxt 182 $cc 183 $acr 200 10$aTheory of computation /$fGeorge Tourlakis 205 $a1st ed. 210 $aHoboken, N.J. $cWiley$d2012 215 $a1 online resource (410 p.) 300 $aDescription based upon print version of record. 311 $a1-118-01478-2 320 $aIncludes bibliographical references and index. 327 $aTheory of Computation; CONTENTS; Preface; 1 Mathematical Foundations; 1.1 Sets and Logic; Nai?vely; 1.1.1 A Detour via Logic; 1.1.2 Sets and their Operations; 1.1.3 Alphabets, Strings and Languages; 1.2 Relations and Functions; 1.3 Big and Small Infinite Sets; Diagonalization; 1.4 Induction from a User's Perspective; 1.4.1 Complete, or Course-of-Values, Induction; 1.4.2 Simple Induction; 1.4.3 The Least Principle; 1.4.4 The Equivalence of Induction and the Least Principle; 1.5 Why Induction Ticks; 1.6 Inductively Defined Sets; 1.7 Recursive Definitions of Functions; 1.8 Additional Exercises 327 $a2 Algorithms, Computable Functions and Computations 2.1 A Theory of Computability; 2.1.1 A Programming Framework for Computable Functions; 2.1.2 Primitive Recursive Functions; 2.1.3 Simultaneous Primitive Recursion; 2.1.4 Pairing Functions; 2.1.5 Iteration; 2.2 A Programming Formalism for the Primitive Recursive Functions; 2.2.1 PR vs. L; 2.2.2 Incompleteness of PR; 2.3 URM Computations and their Arithmetization; 2.4 A Double Recursion that Leads Outside the Primitive Recursive Function Class; 2.4.1 The Ackermann Function; 2.4.2 Properties of the Ackermann Function 327 $a2.4.3 The Ackermann Function Majorizes All the Functions of PR 2.4.4 The Graph of the Ackermann Function is in PR*; 2.5 Semi-computable Relations; Unsolvability; 2.6 The Iteration Theorem of Kleene; 2.7 Diagonalization Revisited; Unsolvability via Reductions; 2.7.1 More Diagonalization; 2.7.2 Reducibility via the S-m-n Theorem; 2.7.3 More Dovetailing; 2.7.4 Recursive Enumerations; 2.8 Productive and Creative Sets; 2.9 The Recursion Theorem; 2.9.1 Applications of the Recursion Theorem; 2.10 Completeness; 2.11 Unprovability from Unsolvability 327 $a3.5 Additional Exercises 4 Adding a Stack to a NFA: Pushdown Automata; 4.1 The PDA; 4.2 PDA Computations; 4.2.1 ES vs AS vs ES+AS; 4.3 The PDA-acceptable Languages are the Context Free Languages; 4.4 Non Context Free Languages; Another Pumping Lemma; 4.5 Additional Exercises; 5 Computational Complexity; 5.1 Adding a Second Stack; Turing Machines; 5.1.1 Turing Machines; 5.1.2 N P-Completeness; 5.1.3 Cook's Theorem; 5.2 Axt, Loop Program, and Grzegorczyk Hierarchies; 5.3 Additional Exercises; Bibliography; Index 330 $a"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 immediately 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 meta-theory 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. 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"--$cProvided by publisher. 330 $a"The book develops the meta-theory 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"--$cProvided by publisher. 606 $aComputable functions 606 $aFunctional programming languages 615 0$aComputable functions. 615 0$aFunctional programming languages. 676 $a511.3/52 686 $aMAT008000$2bisacsh 700 $aTourlakis$b George J$0149747 801 0$bMiAaPQ 801 1$bMiAaPQ 801 2$bMiAaPQ 906 $aBOOK 912 $a9910824075303321 996 $aTheory of computation$94114090 997 $aUNINA