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
Shipping box This item qualifies for FREE shipping.
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!


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…    
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.20" wide x 9.30" long x 1.20" tall
Weight: 1.496
Language: English

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
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
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
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
Cook's Theorem
Axt, Loop Program, and Grzegorczyk Hierarchies
Additional Exercises