05838cam a2200853 a 4500 ocn774024206 OCoLC 20171115105520.0 m o d cr ||||||||||| 120125s2012 nju ob 001 0 eng 2012003569 9781118315354 (epub) 1118315359 (epub) 9781118315330 (pdf) 1118315332 (pdf) 9781118315347 (emobi) 1118315340 (emobi) 9781118315361 1118315367 128059246X 9781280592461 9781118014783 (hardback) 1118014782 (hardback) 9786613622297 EB00595499 Recorded Books AU@ 000048528601 AU@ 000052005881 CHNEW 000602249 DEBBG BV041431014 DEBSZ 37273913X DEBSZ 397224400 DEBSZ 398268347 DEBSZ 422916323 DKDLA 820120-katalog:000599638 NZ1 14554645 (OCoLC)774024206 (OCoLC)795914179 (OCoLC)802330607 (OCoLC)817082387 (OCoLC)852165539 (OCoLC)852166392 (OCoLC)904962547 (OCoLC)927507831 (OCoLC)961501436 (OCoLC)962591608 (OCoLC)966499270 10.1002/9781118315361 Wiley InterScience http://www3.interscience.wiley.com DLC eng pn DLC EBLCP MERUC YDXCP N$T CUS DG1 E7B CDX IUL DEBSZ IDEBK COO UMI OCLCF RECBK OCLCQ AZK DG1 pcc MAIN QA9.59 COM 037000 bisacsh 511.3/52 23 MAT008000 bisacsh Tourlakis, George J. Theory of computation / George Tourlakis. [electronic resource] Hoboken, N.J. : Wiley, 2012. 1 online resource. text txt rdacontent computer c rdamedia online resource cr rdacarrier data file rda Bibliography 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 -- Computational complexity. "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. Print version record and CIP data provided by publisher. Computable functions. Functional programming languages. Computable functions. Functional programming languages. MATHEMATICS Discrete Mathematics. bisacsh Computable functions. fast (OCoLC)fst00871985 Functional programming languages. fast (OCoLC)fst00936087 Computable functions. local Functional programming languages. local Electronic books. Electronic books. local Print version: Tourlakis, George J. Theory of computation. Hoboken, N.J. : Wiley, 2012 9781118014783 (DLC) 2011051088 http://onlinelibrary.wiley.com/book/10.1002/9781118315361 Wiley Online Library ddc BK 205532 205532