Skip to content

Theory of Computation

Spend $50 to get a free DVD!

ISBN-10: 1118014782

ISBN-13: 9781118014783

Edition: 2012

Authors: George Tourlakis

List price: $158.00
Blue ribbon 30 day, 100% satisfaction guarantee!
what's this?
Rush Rewards U
Members Receive:
Carrot Coin icon
XP icon
You have reached 400 XP and carrot coins. That is the daily max!

Description:

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.
Customers also bought

Book details

List price: $158.00
Copyright year: 2012
Publisher: John Wiley & Sons Canada, Limited
Publication date: 4/17/2012
Binding: Hardcover
Pages: 416
Size: 6.50" wide x 9.50" long x 1.25" tall
Weight: 1.496
Language: English

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) &#8593; 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