Mathematical Theory of Computation

ISBN-10: 0486432386

ISBN-13: 9780486432380

Edition: 2003

Authors: Zohar Manna

List price: $24.95 Buy it from $10.96
30 day, 100% satisfaction guarantee

If an item you ordered from TextbookRush does not meet your expectations due to an error on our part, simply fill out a return request and then return it by mail within 30 days of ordering it for a full refund of item cost.

Learn more about our returns policy

Description:

With the objective of making into a science the art of verifying computer programs (debugging), the author addresses both practical and theoretical aspects. Subjects include computability (with discussions of finite automata and Turing machines); predicate calculus; verification of programs (bloth flowchart and algol-like programs); flowchart schemas; and the fixpoint theory of programs. 1974 edition. 77 figures.
New Starting from $20.12
what's this?
Rush Rewards U
Members Receive:
coins
coins
You have reached 400 XP and carrot coins. That is the daily max!
Study Briefs

Limited time offer: Get the first one free! (?)

All the information you need in one place! Each Study Brief is a summary of one specific subject; facts, figures, and explanations to help you learn faster.

Add to cart
Study Briefs
Calculus 1 Online content $4.95 $1.99
Add to cart
Study Briefs
SQL Online content $4.95 $1.99
Add to cart
Study Briefs
MS Excel® 2010 Online content $4.95 $1.99
Add to cart
Study Briefs
MS Word® 2010 Online content $4.95 $1.99
Customers also bought
Loading
Loading
Loading
Loading
Loading
Loading
Loading
Loading
Loading
Loading

Book details

List price: $24.95
Copyright year: 2003
Publisher: Dover Publications, Incorporated
Publication date: 12/24/2003
Binding: Paperback
Pages: 480
Size: 5.25" wide x 8.25" long x 0.80" tall
Weight: 1.276
Language: English

Preface
Computability
Introduction
Finite Automata
Regular Expressions
Finite Automata
Transition Graphs
Kleene's Theorem
The Equivalence Theorem
Turing Machines
Turing Machines
Post Machines
Finite Machines with Pushdown Stores
Nondeterminism
Turing Machines as Acceptors
Recursively Enumerable Sets
Recursive Sets
Formal Languages
Turing Machines as Generators
Primitive Recursive Functions
Partial Recursive Functions
Turing Machines as Algorithms
Solvability of Classes of Yes/No Problems
The Halting Problem of Turing Machines
The Word Problem of Semi-Thue Systems
Post Correspondence Problem
Partial Solvability of Classes of Yes/No Problems
Bibliographic Remarks
References
Problems
Predicate Calculus
Introduction
Basic Notions
Syntax
Semantics (Interpretations)
Valid Wffs
Equivalence of Wffs
Normal Forms of Wffs
The Validity Problem
Natural Deduction
Rules for the Connectives
Rules for the Quantifiers
Rules for the Operators
The Resolution Method
Clause Form
Herbrand's Procedures
The Unification Algorithm
The Resolution Rule
Bibliographic Remarks
References
Problems
Verification of Programs
Introduction
Flowchart Programs
Partial Correctness
Termination
Flowchart Programs with Arrays
Partial Correctness
Termination
Algol-Like Programs
While Programs
Partial Correctness
Total Correctness
Bibliographic Remarks
References
Problems
Flowchart Schemas
Introduction
Basic Notions
Syntax
Semantics (Interpretations)
Basic Properties
Herbrand Interpretations
Decision Problems
Unsolvability of the Basic Properties
Free Schemas
Tree Schemas
Ianov Schemas
Formalization in Predicate Calculus
The Algorithm
Formalization of Properties of Flowchart Programs
Formalization of Properties of Flowchart Schemas
Translation Problems
Recursive Schemas
Flowchart Schemas versus Recursive Schemas
Bibliographic Remarks
References
Problems
The Fixpoint Theory of Programs
Introduction
Functions and Functionals
Monotonic Functions
Continuous Functionals
Fixpoints of Functionals
Recursive Programs
Computation Rules
Fixpoint Computation Rules
Systems of Recursive Defintions
Verification Methods
Stepwise Computational Induction
Complete Computational Induction
Fixpoint Induction
Structural Induction
Bibliographic Remarks
References
Problems
Indexes
Name Index
Subject Index
×
Free shipping on orders over $35*

*A minimum purchase of $35 is required. Shipping is provided via FedEx SmartPost® and FedEx Express Saver®. Average delivery time is 1 – 5 business days, but is not guaranteed in that timeframe. Also allow 1 - 2 days for processing. Free shipping is eligible only in the continental United States and excludes Hawaii, Alaska and Puerto Rico. FedEx service marks used by permission."Marketplace" orders are not eligible for free or discounted shipping.

Learn more about the TextbookRush Marketplace.

×